2nd Data Summary

การหาเส้นทางที่สั้นที่สุด

     สำหรับการหาเส้นทางที่สั้นที่สุดนั้น จะเป็นการสร้างแบบจำลองเส้นทางหรือแผนที่เป็น กราฟ ซึ่งประกอบไปด้วย จุด และ เส้น ซึ่งจะให้ตำแหน่งแทนด้วยจุด และให้ถนนแทนด้วยเส้น จากนั้นจะทำกราฟที่ได้มาเป็นตัวแทนของแผนที่ เพื่อนำไปคำนวณเส้นทางที่สั้นที่สุด  

รูปที่ 1 กราฟทีมี 2 จุด 1 เส้น

รูปที่ 2 กราฟทีมี 4 จุด 3 เส้น

รูปที่ 3 กราฟเป็นวัฏจักร

                จากรูปที่ 1-3 เป็นกราฟแบบง่าย แต่เมื่อนำมาใช้ในแผนที่นั้นจะซับซ้อนกว่านั้น ซึ่งมีชื่อเรียกว่า Multiple Graph

รูปที่ 4 Multiple Graph

ที่มา https://www.ryerson.ca/science/research/stories/story_pralat_2013/

               การจะหาเส้นทางที่สั้นที่สุดนั้น จะดูจากเส้นทางที่ผ่านจุดหรือระยะทางน้อยที่สุด

รูปที่ 5

ที่มา https://myalgo.wordpress.com/2010/09/04/weighted-shortest-path-dijkstras-algorithm/

จากรูปจะเห็นได้ว่า เมื่อต้องการเดินทางจากจุดที่ 1 ไปยังจุดที่ 7 ระยะทางที่ใกล้ที่สุด คือจาก จุดที่ 1 ไปยังจุดที่ 4 แล้วไปยังจุดที่ 7 ซึ่งมีระยะทางเพียง 5

การหาเส้นทางที่สั้นที่สุดจะใช้อัลกอริทึมที่มีชื่อว่า Dijkstra’s algorithm แล้วนำมาแปลงเป็นเส้นทางถนนต่อไป โดยมีการใส่ระยะเส้นทางไปด้วย

Dijkstra’s algorithm

Dijkstra’s algorithm ถูกคิดค้นขึ้นโดย Edsger Dijkstra นักวิทยาการคอมพิวเตอร์ชาวดัตช์ ในปี 1959 เพื่อแก้ไขปัญหาการหาเส้นทางที่สั้นที่สุดจากจุดหนึ่งใดๆ สำหรับกราฟที่มีความยาวของเส้นเชื่อมไม่เป็นลบ สำหรับขั้นตอนวิธี Dijkstra’s Algorithm นี้จะหาระยะทางสั้นที่สุดจากจุดหนึ่งไปยังจุดใด ๆ ในกราฟโดยจะหาเส้นทางที่สั้นที่สุดไปทีละจุดยอดเรื่อยๆ จนครบตามที่ต้องการ

Dijkstra’s algorithm

กำหนดให้จุด จุดหนึ่งภายในกราฟเป็นจุดเริ่มต้น และกำหนดให้ “ระยะทางของจุด X” หมายถึงระยะทางจากจุดเริ่มต้นไปยังจุด X ใด โดย Dijkstra’s algorithm จะกำหนดค่าระยะทางเริ่มต้นไว้บางจุดและจะเพิ่มค่าไปทีละขั้นตอน

1.             กำหนดให้ทุกจุดมีค่าระยะทางตามเส้นเชื่อม โดยให้จุดเริ่มต้นมีค่าเป็นศูนย์ และจุดอื่นๆมีค่าเป็นอนันต์

2.             ทำเครื่องหมายทุกจุด ยกเว้นจุดเริ่มต้นว่ายังไม่ไปเยือน ตั้งให้จุดเริ่มต้นเป็นจุดปัจจุบัน สร้างเซตของจุดที่ยังไม่ไปเยือนขึ้นมาเซตหนึ่งซึ่งประกอบด้วยจุดทุกจุด ยกเว้นจุดเริ่มต้น

3.     จากจุดปัจจุบัน พิจารณาจุดข้างเคียงตามเส้นเชื่อมทุกจุดที่ยังไม่ไปเยือน และคำนวณระยะทางต่อเนื่องของเส้นเชื่อม ตัวอย่างเช่น ถ้าจุดปัจจุบันคือ A มีระยะทางของจุดเป็น 6 และเส้นเชื่อมที่ต่อจาก A ไปยังจุดข้างเคียง B มีระยะทางเป็น 2 ดังนั้นระยะทางของจุด B (โดยผ่าน A) จึงเท่ากับ 6+2=8 เป็นต้น ถ้าระยะทางที่คำนวณได้มีค่าน้อยกว่าค่าระยะทางที่บันทึกอยู่ของจุดนั้น ให้เขียนทับค่าระยะทางของจุดดังกล่าว แม้ว่าจุดข้างเคียงได้ถูกพิจารณาแล้ว แต่ก็ยังไม่ทำเครื่องหมายว่าไปเยือนแล้ว (visited) ในขั้นตอนนี้ จุดข้างเคียงจะยังคงอยู่ในเซตของจุดที่ยังไม่ไปเยือนเช่นเดิม

4.     เมื่อพิจารณาจุดข้างเคียงจากจุดปัจจุบันครบทุกจุดแล้ว ทำเครื่องหมายที่จุดปัจจุบันว่าไปเยือนแล้ว (visited) และนำออกจากเซตของจุดที่ยังไม่ไปเยือน โดยจุดที่ไปเยือนแล้วนี้จะไม่ถูกนำมาตรวจสอบอีก ค่าระยะทางที่บันทึกอยู่จะสิ้นสุดและมีค่าน้อยที่สุด

5.     จุดปัจจุบันตัวถัดไปที่ถูกเลือกจะเป็นจุดที่มีค่าระยะทางน้อยสุดในเซตของจุดที่ยังไม่ไปเยือน

6.             ถ้าเซตของจุดที่ยังไม่ไปเยือนว่างแล้วให้หยุดการทำงาน ขั้นตอนวิธีเสร็จสิ้น แต่ถ้าหากไม่ใช่ให้เลือกจุดที่ยังไม่ไปเยือนที่มีค่าระยะทางน้อยสุดเป็นจุดปัจจุบัน แล้ววนกลับไปทำขั้นตอนที่ 3

รูปที่ 6 รูปแสดง Dijkstra’s algorithm

ที่มา https://www.appdisqus.com/2015/02/06/algorithm-of-google-here-apple-maps.html

Reference : https://www.appdisqus.com/2015/02/06/algorithm-of-google-here-apple-maps.html
                

Search when 15/12/2018 3.45 PM