Variations in Travelling Salesman Problem (TSP)

Simple TSP เราทราบกันแล้วว่า คือปัญหา “Shortest Hamiltonian Cycle” กล่าวคือ พยายามหาเส้นทางที่สั้นที่สุด จากจุดเริ่มต้นเดินทางผ่านทุกจุด แล้วกลับมายังจุดเริ่มต้นอีกครั้ง โดยให้สามารถผ่านแต่ละจุดได้เพียงครั้งเดียวเท่านั้น .. เปรียบได้กับในชีวิตจริง เช่น ปัญหาการผูกเชือกรองเท้า “The Shorlace Problem” เป็นต้น

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

Simple TSP

ตัวอย่างปัญหา “Shoelace Problem” .. คิดว่า ผูกเชือกรองเท้าวิธีไหน จะใช้เชือกสั้นที่สุด

Simple Variations of the TSP

ถูกดัดแปลงมาจากปัญหาในชีวิตจริงเช่นกัน

  • The MAX TSP:

หา Tour ที่ยาวที่สุด

  • The bottleneck TSP:

หา Tour ที่มี Edge ที่มีค่าน้อยสุด, คอขวด

  • TSP with multiples visit (TSPM):

เหมือน TSP แต่สามารถ Visit แต่ละ Node ได้มากกว่า 1 ครั้ง

More Variations of The TSP

ลองดูที่ http://books.google.com/books?id=5RuNx2TIbIcC&lpg=PP1&pg=PA25

Note

– อ้างอิงจาก “The traveling salesman problem and its variations“, by Gregory Gutin, Abraham P. Punnen

Advertisements

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s