ตัวอย่างโจทย์ที่กำหนดขึ้นเอง

ตัวอย่างการหาระยะทางที่สั้นที่สุด

โจทย์ :

เด็กชายทรงพล ต้องการไปยังโรงเรียนด้วยระยะทางที่ใกล้ที่สุด โดยจากบ้านไปยังสวนสาธารณะ วัด และตลาด เป็นระยะทาง 5 8 และ 4 เมตร จากสวนสาธารณะ ตลาด และวัด ไปยังโรงพยาบาลเป็นระยะทาง 7 5 และ 12 เมตร จากตลาด และวัด ไปยังสถานีตำรวจเป็นระยะทาง 11 และ 11 เมตร และจากโรงพยาบาล และสถานีตำรวจ ไปยังโรงเรียนเป็นระยะทาง 9 และ 6 เมตร ตามลำดับ

วิธีทำ :

ให้ A แทน บ้าน

     B แทน สวนสาธารณะ

     C แทน วัด

     D แทน ตลาด

                    E แทน โรงพยาบาล

     F แทน สถานีตำรวจ

     G แทน โรงเรียน

Step 1 : หาเส้นทางที่จะไปได้ ซึ่งจะเห็นได้ว่ามีจาก A ไป B  A ไป C และ A ไป D

Step 2 : เลือกเส้นทางที่ระยะทางสั้นที่สุด ซึ่งจะได้ A ไป D ระยะทาง 4 เมตร ที่สั้นที่สุด

Step 3 : หาเส้นทางที่จะไปได้ ซึ่งจะเห็นได้ว่ามีจาก A ไป D ไป E และ A ไป D ไป F

Step 4 : เลือกเส้นทางที่ระยะทางสั้นที่สุด ซึ่งจะได้ A ไป D ไป F ระยะทาง 9 เมตร ที่สั้นที่สุด

Step 5 : หาเส้นทางที่จะไปได้ ซึ่งจะเห็นได้ว่ามี A ไป D ไป E ไป G  และ A ไป D ไป F

Step 6 : เลือกเส้นทางที่ระยะทางสั้นที่สุด ซึ่งจะได้ A ไป D ไป F ระยะทาง 15 เมตร ที่สั้นที่สุด

Step 7 : เลือกเส้นทางที่ระยะทางสั้นที่สุด ซึ่งจะได้ A ไป D ไป E ไป G ระยะทาง 18 เมตร ที่สั้นที่สุด

Do when 16/12/2018 8.12 PM

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