คอมพิวเตอร์, การเขียนโปรแกรม
อัลกอริทึมของ Dijkstra และการดำเนินงานของ
มีพื้นที่ที่เรียกว่าแยกต่างหากทฤษฎีกราฟในวิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์เป็น ในฐานะที่เป็นส่วนหนึ่งของชุดและการแก้ปัญหาต่างๆเช่นการหาเส้นทางที่สั้นที่สุดระหว่างจุด หนึ่งในวิธีที่พบบ่อยในหมู่นักคณิตศาสตร์ในการแก้ปัญหานี้มีมานานแล้วอัลกอริทึมของ Dijkstra
เป็นที่เชื่อกันว่าแนวความคิดของกราฟที่ถูกนำไปใช้ในศตวรรษที่สิบแปด Leonardom Eylerom เขาเป็นคนที่มีการประกาศการกำหนดและการแก้ปัญหาของหนึ่งในปัญหาคลาสสิกของทฤษฎีนี้ - เจ็ดสะพานKönigsberg เพื่ออธิบายวัตถุของทฤษฎีนี้มักจะใช้การเปรียบเทียบนี้การเคลื่อนไหวระหว่างเมืองที่แตกต่างกัน จากนั้นกราฟบนเครื่องบินจะเป็นแผนภาพทั้งเส้นทางที่จุดกลายเป็นรายการที่เฉพาะเจาะจง (เช่นเมือง) และขอบ - เส้นทางจากที่หนึ่งไปยังอีกจุดสุดยอด (ถนนระหว่างเมืองอะนาล็อก) อัลกอริทึมของ Dijkstra นอกเหนือไปจากวิธีการอื่น ๆ สามารถให้วิธีการแก้ปัญหานี้
หนึ่งในงานทั่วไป ของทฤษฎีกราฟ เป็นหนึ่งในที่ที่คุณจำเป็นต้องตรวจสอบเส้นทางที่ค่าใช้จ่ายที่ดีที่สุดระหว่างสองจุด มันเป็นไปได้ที่จะลดเครื่องบินไปสู่การตัดสินใจของกราฟที่จุด - เมือง - เป็นซี่โครงที่เชื่อมต่อกันซึ่งเป็นถนนที่เป็นไปได้ แต่ละถนนมีความยาวของตัวเองดังนั้นการเดินทางบนก็จะมีการใช้จ่ายเงินบางส่วน เงินจำนวนนี้จะเทียบเท่ากับน้ำหนักของขอบในกราฟที่ แล้วปัญหาในทางปฏิบัติสามารถนำสูตรดังต่อไปนี้: วิธีการปูทางจากเมืองหนึ่งไปยังอีกที่จะใช้ในวิธีที่ถนนขั้นต่ำ
วิธีการที่จะแก้ปัญหา
เพื่อแก้ปัญหานี้เราได้รับการคิดค้นโดยขั้นตอนวิธีการบางอย่างที่ได้กลายเป็นที่รู้จักกันอย่างแพร่หลายในโลกวิทยาศาสตร์ ยกตัวอย่างเช่นอัลกอริทึมฟลอยด์ - Uorshella ฟอร์ด - ยาม วิธีที่คลาสสิกของการหาโซลูชั่นยังเป็นอัลกอริทึมของ Dijkstra มันสามารถใช้สำหรับการถ่วงน้ำหนัก (น้ำหนักที่รู้จักกันของแต่ละขอบ) ของกราฟและเพื่อเจือจาง เพื่อหาวิธีที่ดีที่สุดที่คุณต้องทำหลายขั้นตอน
อัลกอริทึมของ Dijkstra
จุดของวิธีการนี้อยู่ในความจริงที่ว่าทุกจุดของค่าใช้จ่ายเริ่มต้นด้วยการกำหนดประเด็นแต่ละแท็กมีการกำหนดค่าบางอย่าง แล้วผลจะรวมถึงจุดที่มีป้ายชื่อที่มีน้อย ด้านบนของขั้นตอนการเริ่มต้นครั้งแรกที่จะได้รับการติดแท็กด้วยค่าเป็น 0 แล้วทั้งหมดของยอดเขาดังต่อไปนี้ได้รับการพิจารณาว่าเป็นผู้ที่สามารถเข้าถึงได้จากแหล่งที่มา พวกเขาจะมีป้ายกำกับค่าซึ่งจะถูกกำหนดเป็นผลรวมของรหัสที่มาและน้ำหนักของเส้นทางที่ จากด้านบนของขั้นตอนต่อไปให้เลือกอย่างใดอย่างหนึ่งที่มีค่าที่สุดของฉลากและการศึกษาจุดทั้งหมดที่อยู่ในนั้นจากนั้นเราสามารถไปโดยไม่ต้องใช้โหนดกลาง ระบุป้ายชื่อใหม่เท่ากับท็อปส์ซูฉลาก - รหัสที่มาบวกกับน้ำหนักของวิธีการ หากมีค่าน้อยกว่าฉลากบนฉลากที่มีการเปลี่ยนแปลง มิฉะนั้นมันจะยังคงค่าเดิม ในขณะเดียวกันในอาร์เรย์แยกต่างหากที่มีมิติจะเท่ากับจำนวนของจุดที่จะเก็บผลของการเพิ่มประสิทธิภาพในการที่มุ่งมั่นและวิธีการ การใช้วิธีการดังกล่าวเป็นอัลกอริทึมของ Dijkstra ปาสกาลมีวิธีที่สะดวกมาก อัลกอริทึมมีความได้เปรียบที่ว่ามันสามารถเป็นพื้นฐานสำหรับโปรแกรมที่มีขนาดเล็ก ตัวอย่างของผลิตภัณฑ์ซอฟต์แวร์ดังกล่าวง่ายต่อการค้นหาบนอินเทอร์เน็ต
Similar articles
Trending Now