สารบัญ
11 ความสัมพันธ์: กราฟ (แบบชนิดข้อมูลนามธรรม)การค้นหาแบบเอสตาร์การค้นหาในแนวกว้างรายชื่อขั้นตอนวิธีขั้นตอนวิธีของฟลอยด์-วอร์แชลขั้นตอนวิธีของจอห์นสันขั้นตอนวิธีของครูสกาลขั้นตอนวิธีของเบลแมน-ฟอร์ดต้นไม้วิถีสั้นสุดปัญหาวิถียาวสุดปัญหาวิถีสั้นสุด
กราฟ (แบบชนิดข้อมูลนามธรรม)
กราฟที่มี 6 จุดยอด และ 7 เส้นเชื่อม ในสาขาวิชาวิทยาการคอมพิวเตอร์ กราฟเป็นโครงสร้างข้อมูลที่นำแนวคิดของกราฟทางคณิตศาสตร์และไฮเปอร์กราฟมาทำให้เกิดผล โครงสร้างข้อมูลแบบกราฟประกอบด้วยเซตสองชุด คือ เซตของจุดยอด (หรือปม) และ เส้นเชื่อม เช่นเดียวกันกับทางคณิตศาสตร์ เส้นเชื่อม(x,y) มีหมายความว่า เส้นเชื่อมจากจุดยอด x ไปยังจุดยอด y โครงสร้างข้อมูลแบบกราฟอาจให้ค่ากับเส้นเชื่อมโดยอาจจะให้ความหมายได้หลายอย่าง เช่น มูลค่า ความจุ ความยาว น้ำหนัก ฯลฯ.
ดู ขั้นตอนวิธีของไดก์สตราและกราฟ (แบบชนิดข้อมูลนามธรรม)
การค้นหาแบบเอสตาร์
ในวิทยาการคอมพิวเตอร์ ขั้นตอนวิธีเอสตาร์ (A* algorithm) เป็นขั้นตอนวิธีที่ใช้ในการหาเส้นทางและการท่องในกราฟซึ่งเป็นกระบวนการในการหาเส้นทางระหว่างจุด (เรียกจุดดังกล่าวว่า "โนด" (node)) ขั้นตอนวิธีนี้มีประสิทธิภาพและความแม่นยำสูงจึงมีการนำไปใช้งานอย่างแพร่หลาย ผู้นิยามขั้นตอนวิธีนี้คือ ปีเตอร์ ฮาท์, นิล นีลสัน และเบิร์ดแรม เรฟเซด ซึ่งนิยามไว้ในปี ค.ศ.
ดู ขั้นตอนวิธีของไดก์สตราและการค้นหาแบบเอสตาร์
การค้นหาในแนวกว้าง
right ในทฤษฎีกราฟ การค้นหาตามแนวกว้าง (breadth-first search หรือย่อว่า BFS) คือขั้นตอนวิธีในการท่องกราฟอย่างหนึ่ง โดยในขณะที่กำลังท่องกราฟมายังจุดยอดหนึ่ง ๆ นั้น จะมีการกระทำสองอย่างคือ: (ก) เข้าเยี่ยมและตรวจสอบจุดยอดดังกล่าว (ข) เข้าถึงจุดยอดข้างเคียงของจุดยอดดังกลาว การท่องกราฟจะเริ่มต้นที่จุดยอดรากที่กำหนดและไปยังจุดยอดอื่น ๆ จนเกิดเป็นต้นไม้แบบทอดข้าม การท่องกราฟอีกรูปแบบที่คล้ายคลึงกันคือการค้นหาในแนวลึก การค้นในลักษณะนี้ถูกใช้เป็นแนวคิดพื้นฐานในการแก้ปัญหาทฤษฏีกราฟรวมถึงการค้นในปริภูมิสถานะ เนื่องจากมีลักษณะของการแวะผ่านปมไปทีละระดับ จึงเรียกอีกอย่างว่า การค้นทีละระดับ (Level-order search).
ดู ขั้นตอนวิธีของไดก์สตราและการค้นหาในแนวกว้าง
รายชื่อขั้นตอนวิธี
ทความนี้แสดงถึงรายชื่อขั้นตอนวิธีพร้อมรายละเอียดอย่างสั้น.
ดู ขั้นตอนวิธีของไดก์สตราและรายชื่อขั้นตอนวิธี
ขั้นตอนวิธีของฟลอยด์-วอร์แชล
ั้นตอนวิธีของฟลอยด์-วอร์แชล (Floyd–Warshall algorithm) หรือที่รู้จักในนามว่า ขั้นตอนวิธีของฟลอยด์, ขั้นตอนของรอย-วอร์แชล หรือ ขั้นตอนวิธีของรอย-ฟลอยด์ เป็นขั้นตอนวิธีการวิเคราะห์กราฟเพื่อที่จะหาระยะทางของเส่นทางสั้นสุดในกราฟที่มีน้ำหนักของเส้นเชื่อมเป็นบวก หรือ น้ำหนักของเส้นเชื่อมเป็นลบ ก็ได้แต่ไม่สามารถหาได้ถ้ามีวงจรลบ โดยการทำงานหนึ่งครั้งของขั้นตอนวิธีนี้จะได้คำตอบของระยะทางของเส้นทางสั้นสุดของทุกๆคู่ปมบนกราฟ อย่างไรก็ตามจะไม่สามารถคืนค่ารายละเอียดของเส้นทางสั้นสุดในแต่ละคู่ปมได้ ยกเว้นมีการเพิ่มเติมเข้าไป ขั้นตอนวิธีนี้เป็นตัวอย่างของกำหนดการพลวัตแบบด้านล่างขึ้นด้านบน โดยขั้นตอนวิธีนี้ถูกคิดขึ้นโดย โรเบิร์ต ฟลอยด์ ในปี 1962 อย่างไรก็ตามขั้นตอนวิธีนี้มีส่วนสำคัญเหมือนกับอัลกอริทึมของเบอร์นาร์ด รอยด์ ในปี 1959 และของสตีเฟน วอร์แชล ในปี 1962 ในการค้นหา ความสัมพันธ์แบบถ่ายทอดของกราฟ (Transitive closure).
ดู ขั้นตอนวิธีของไดก์สตราและขั้นตอนวิธีของฟลอยด์-วอร์แชล
ขั้นตอนวิธีของจอห์นสัน
ั้นตอนวิธีของจอห์นสัน เป็นขั้นตอนวิธีที่ทำการปรับกราฟไม่ให้มีน้ำหนักติดลบเพื่อให้สามารถใช้ขั้นตอนวิธีของไดค์สตราได้ในการหาเส้นทางสั้นที่สุดระหว่างทุกคู่จุดหรือปม ซึ่งเป็นขั้นตอนวิธีที่เหมาะในการใช้กับกราฟระบุทิศทางที่มีเส้นเชื่อมน้อยเพราะถ้าเส้นเชื่อมเยอะจะช้ากว่า ขั้นตอนวิธีของฟลอยด์-วอร์แชล แต่ต้องไม่มีวงรอบที่น้ำหนักติดลบอยู่ด้วย ผู้คิดค้นวิธีการนี้คือ โดนัลด์ บี.
ดู ขั้นตอนวิธีของไดก์สตราและขั้นตอนวิธีของจอห์นสัน
ขั้นตอนวิธีของครูสกาล
การจำลองการทำงานของขั้นตอนวิธีของครูสกาล ขั้นตอนวิธีของครูสกาล (อังกฤษ: Kruskal's algorithm) เป็นขั้นตอนวิธีแบบละโมบในทฤษฎีกราฟ ที่ใช้หา ต้นไม้แบบทอดข้ามน้อยสุด (Minimum spanning tree) สำหรับกราฟเชื่อมโยงแบบมีน้ำหนัก นั้นหมายความว่าเราจะได้เซตย่อยของเส้นเชื่อมในต้นไม้ที่เชื่อมทุกๆปม โดยที่ผลรวมของน้ำหนักบนเส้นเชื่อมจะมีค่าน้อยที่สุด หากกราฟไม่เป็นกราฟเชื่อมโยง เราจะได้ ป่าแบบทอดข้ามน้อยสุด (คือต้นไม้แบบทอดข้ามน้อยสุดแต่ละต้นในกราฟ) ขั้นตอนวิธีนี้ปรากฏครั้งแรกบนนิตยสารทางวิทยาศาสตร์ชื่อ Proceedings of the American Mathematical Society หน้.
ดู ขั้นตอนวิธีของไดก์สตราและขั้นตอนวิธีของครูสกาล
ขั้นตอนวิธีของเบลแมน-ฟอร์ด
ั้นตอนวิธีของเบลแมน-ฟอร์ด (Bellman-Ford Algorithm) เป็นขั้นตอนวิธีที่ใช้ในการแก้ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวสำหรับเส้นเชื่อมที่มีน้ำหนักใดๆ นอกจากนี้ขั้นตอนวิธียังสามารถตรวจพบวัฏจักรที่มีน้ำหนักรวมของเส้นเชื่อมเป็นลบ หรือที่เรียกว่าวัฏจักรเชิงลบ (Negative cycle) ซึ่งทำให้ปัญหาวิถีสั้นสุดไม่นิยาม ขั้นตอนวิธีนี้ถูกคิดค้นโดยนักพัฒนาชื่อริชาร์ด เบลแมน (Richard Bellman) และเลสเตอร์ ฟอร์ด จูเนียร์ (Lester Ford Jr).
ดู ขั้นตอนวิธีของไดก์สตราและขั้นตอนวิธีของเบลแมน-ฟอร์ด
ต้นไม้วิถีสั้นสุด
ในทฤษฎีกราฟ ต้นไม้วิถีสั้นสุด เป็นต้นไม้ที่ได้จากการแก้ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวบนกราฟที่กำหนดให้ โดยต้นไม้นี้จะเป็นกราฟย่อยของกราฟนั้นและระยะทางระหว่างรากกับจุดยอดใด ๆ มีค่าน้อยที่สุด การที่แก้ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวแล้วได้ต้นไม้นั้นเพราะว่าหากมีสองวิถีระหว่างรากกับโหนด v (มีวัฏจักร) เราสามารถเลือกใช้วิถีที่สั้นกว่า และลบเส้นเชื่อมที่มีระยะทางของวิถีที่ยาวกว่าได้โดยไม่ทำให้ระยะทางจากรากไปโหนดใดๆเพิ่มขึ้น หากโหนดทุกๆคู่ในกราฟที่กำหนดให้มีวิถีสั้นสุดเพียงแบบเดียว จะได้ว่าต้นไม้วิถีสั้นสุดก็จะมีเพียงแบบเดียวด้วยเช่นกัน ในกราฟที่ไม่มีน้ำหนักติดลบ ขั้นตอนวิธีของไดค์สตรา สามารถคำนวณหาต้นไม้วิถีสั้นสุดได้ สำหรับกราฟที่มีน้ำหนักติดลบ สามารถใช้ ขั้นตอนวิธีของเบลแมน-ฟอร์ด แทนได้ ดี.
ดู ขั้นตอนวิธีของไดก์สตราและต้นไม้วิถีสั้นสุด
ปัญหาวิถียาวสุด
ปัญหาวิถียาวสุด (Longest path problem) เป็นหนึ่งในปัญหาทางคณิตศาสตร์ในเรื่องทฤษฎีกราฟ ซึ่งมีไว้สำหรับค้นหาวิถีเชิงเดียว (Simple path) ที่มีระยะทางมากที่สุดนับจากปมเริ่มต้นไปยังปมปลายทางบนกราฟถ่วงน้ำหนัก (Weighted graph) ลักษณะของปัญหาวิถียาวสุดจะคล้ายคลึงกันกับปัญหาวิถีสั้นสุด (Shortest path problem) ซึ่งเป็นการหาวิถีเชิงเดียวบนกราฟที่มีระยะทางสั้นที่สุดแทน เราสามารถหาวิถีสั้นสุดบนกราฟใดๆได้ในเวลาที่เป็นฟังก์ชันพหุนาม (Polynomial time) นั่นหมายถึงปัญหาวิถีสั้นสุดที่ลักษณะของปัญหาเป็นแบบปัญหาการตัดสินใจนั้นจัดอยู่ในกลุ่มความซับซ้อนแบบพี แต่ในทางกลับกัน ปัญหาวิถียาวสุดนั้นกลับยังไม่มีขั้นตอนวิธีใดที่ทำงานได้อย่างถูกต้องในเวลาที่เป็นฟังก์ชันพหุนาม กล่าวคือเป็นปัญหาที่อยู่ในกลุ่มเอ็นพี และได้รับการพิสูจน์แล้วว่าปัญหาวิถียาวสุดนั้นเกิดจากการลดรูปมาจากปัญหาวิถีฮัลมินตัน (Hamiltonian path problem) ซึ่งอยู่ในกลุ่มเอ็นพีบริบูรณ์ ทำให้ปัญหานี้อยู่ในกลุ่มเอ็นพีบริบูรณ์เช่นเดียวกัน.
ดู ขั้นตอนวิธีของไดก์สตราและปัญหาวิถียาวสุด
ปัญหาวิถีสั้นสุด
วิถีสั้นสุดบนกราฟไม่ระบุทิศทางที่ไม่ถ่วงน้ำหนักระหว่างจุดยอด 6 กับ 1 คือ (6, 4, 5, 1) ในทฤษฎีกราฟ ปัญหาวิถีสั้นสุด (shortest path problem) เป็นปัญหาที่ต้องการหาวิถีสั้นสุดระหว่างจุดยอด 2 จุดภายในกราฟ กล่าวคือในวิถีสั้นสุดนั้น ผลรวมของน้ำหนักในเส้นเชื่อมแต่ละเส้นรวมกันแล้วน้อยที่สุดในบรรดาวิถีทั้งหมด ตัวอย่างปัญหานี้เช่นการหาวิธีเดินทางจากจุดหนึ่งไปอีกจุดหนึ่งในแผนที่ ในกรณีนี้ จุดยอดแทนด้วยสถานที่ต่างๆ ส่วนเส้นเชื่อมแทนด้วยถนนหรือเส้นทาง และน้ำหนักบนเส้นเชื่อมแทนด้วยเวลาในการเดินทางด้วยถนนหรือเส้นทางนั้น.
ดู ขั้นตอนวิธีของไดก์สตราและปัญหาวิถีสั้นสุด
หรือที่รู้จักกันในชื่อ อัลกอริทึมของดิสตราส์