Recap:
Hamilton circle คือการเดินทาง (travelling)ผ่าน vertices และ edges ใน graph โดยที่
‣ ผ่านแต่ละ vertex เพียงครั้งเดียว
‣ จุดเริ่มต้นและจุดสิ้นสุกการเดินทางคือ vertex เดียวกัน
Travelling salesman problem (TSP) ใช้ scenario การเดินทางของ salesman คนหนึ่งที่ต้องการเดินทางจากเมืองหนึ่งไปยังอีกเมื่องหนึ่งโดยไม่ซ้ ำและจบการเดินทางที่เมืองแรกที่เริ่มเดินทาง โดยที่ต้นทุนการเดินทางต้องต่ำที่สุด
TSP เป็น greedy algorithm เหมือนกับ Prim's algorithm หรือ Kruskal's algorithm รวมกับความรู้เรื่อง Hamilton circle แต่ถูกนำมาใช้กับ weighted graph โดยต้นทุนการเดินทางสามารถคำนวณได้จากผลรวมของ weight ทั้งหมดในการเดินทาง
‣ TSP ที่ต้นทุนการเดินทาง \( A \rightarrow B = B \rightarrow A\) เรียกว่า Symetric TSP (STSP)
‣ TSP ที่ต้นทุนการเดินทาง \( A \rightarrow B \neq B \rightarrow A\) เรียกว่า Asymetric TSP (ATSP)
การแก้ปัญหา TSP
(อ่านเรื่อง Prim's algorithm และ Kruskal's algorithm ได้จาก Introduction to Graph theory part 3 )
 |
| รูปที่ 1 |
ถ้ามีเมือง 4 เมือง A,B,C และ D ต้นทุนการเดินทางแสดงในรูปที่ 1 ลองการใช้ Prim's algorithm เพื่อแก้ปัญหาก่อน เริ่มจากเลือก vertex A เป็นจุดเริ่มต้น (สามารถเลือก vertex ใดก็ได้) จากนั้นขั้นตอนที่เหลือจะเป็นดังรูปที่ 2 (เริ่มต้นจากตำแหน่งซ้ายบน) ซึ่งจะได้ต้นทุนรวมเป็น \( 6+2+2+5 = 15 \)
 |
| รูปที่ 2 แสดงขั้นตอนการแก้ปัญหาด้วย Prim's algorithm |
ต่อไปลองใช้ Kruskal's algorithm ดู ผลลัพธ์แสดงในรูปที่ 3
 |
| รูปที่ 3 แสดงผลลัพธ์จาก Kruskal's algorithm |
ปัญหานี้ผลของ Kruskal's algorithm ให้ค่ารวมของต้นทุนต่ำกว่าคือ 14
ความคิดเห็น
แสดงความคิดเห็น