Internet & Web Application

Travelling Salesman Problem (TSP)

TSP เป็น “Combinatorial Optimization” ที่ศึกษากันใน “Operations Research” และ “Theoretical Computer Science” โดยให้กลุ่มของเมือง และกลุ่มเส้นทางที่เชื่อมถึงกัน จากนั้นตั้งคำถามว่า ควรเลือกใช้เส้นทางใด ที่จะผ่านทุกเมือง โดยใช้เส้นทางสั้นที่สุด

ประโยชน์ที่ได้นำไปประยุกต์ใช้งานก็คือ การจัดการ, การขนส่ง, และอื่นอีกมากมาย

ในทางทฤษฎี การคำนวณ TSP อยู่ใน Class ของปัญหา NP-complete หรือพูดได้ว่าเวลาในการคำนวณที่แย่ที่สุดจะเป็น Exponential Function ของจำนวนเมือง ส่งผลให้เพียงไม่กี่ร้อยเมือง ก็ทำให้ต้องใช้เวลาทำงานของ CPU เป็นปีก็ว่าได้

เมื่อ Model แผนที่ให้มาอยู่ในรูปแบบของ Graph Theory แล้ว จะเห็นว่า TSP Tour เป็นรูปแบบของปัญหา “Hamiltonian Cycle” และสำหรับ Optimal TSP สามารถ Model ให้อยู่ในปัญหาแบบ “Shortest Hamiltonian Cycle” (Cycle คืออะไร ? … คือ path ที่ เริ่มต้นและจบลงที่ Vertex เดิม โดยให้สามารถซ้ำ Vertex ได้ )

บ่อยครั้งสำหรับ Input Graph ที่นำมาหา TSP จำเป็นต้องเป็น Complete Graph เพราะจำทำให้สามารถนำไปคำนวณได้ง่าย ใน Hamiltonian Cycle Problem (แน่นอน สามารถเปลี่ยนจาก Graph ใดใด ให้เป็น Complete Graph ได้ .. All Pair Shortest Path)

Asymmetric and symmetric

สำหรับ Symmetric TSP, ระยะทางระหว่าง 2 Vertex ที่ติดกัน จะเท่ากันทั้งไปและกลับ ซึ่งเกิดขึ้นบน Undirected Graph ต่างกันกับ Asymmetric TSP ที่ไม่จำเป็นต้องเท่ากันทั้งไปและกลับ ซึ่งจะใช้ Directed Graph เป็น Model

With metric distances

In the metric TSP the intercity distances satisfy the triangle inequality. This can be understood as “no shortcuts”, in the sense that the direct connection from A to B is never longer than the detour via C.

c_{ij} \le c_{ik} + c_{kj}

These edge lengths define a metric on the set of vertices. When the cities are viewed as points in the plane, many natural distance functions are metrics.

  • In the Euclidian TSP the distance between two cities is the Euclidean distance between the corresponding points.
  • In the Rectilinear TSP the distance between two cities is the sum of the differences of their x– and y-coordinates. This metric is often called the Manhattan distance or city-block metric.
  • In the maximum metric, the distance between two points is the maximum of the differences of their x– and y-coordinates.

The last two metrics appear for example in routing a machine that drills a given set of holes in a printed circuit. The Manhattan metric corresponds to a machine that adjusts first one co-ordinate, and then the other, so the time to move to a new point is the sum of both movements. The maximum metric corresponds to a machine that adjusts both co-ordinates simultaneously, so the time to move to a new point is the slower of the two movements.

Non-metric distances

Distance measures that do not satisfy the triangle inequality arise in many routing problems. For example, one mode of transportation, such as travel by airplane, may be faster, even though it covers a longer distance.

ประเด็นข้อสงสัยหนึ่งที่น่าสนใจคือ จากคำนิยามที่ว่า TSP ไม่อนุญาตให้ Visit ตัว Vertex ได้มากกว่า 1 ครั้ง .. แต่ทว่ามี Application มากมายที่ไม่ต้องการ Contraint นี้ … ทำให้เกิดทางแก้ไข อย่างในกรณีของ a symmetric, non-metric instance ที่สามารถลดรูปเป็น Matrix ของข้อมูล .. หรืออีกนัยหนึ่งคือ การแทนที่ Graph ปัญหา ด้วย Complete Graph โดยอาศัย Shortest Path ระหว่างสองจุดใน Graph นั่นเอง

Note

– อ้างอิง Wiki : Travelling Salesman Problem

Hamiltonian Path : คือ Path ที่ผ่านทุก Vertex เพียงครั้งเดียว (William Rowan Hamilton)

Eulerian Path : คือ Path ที่ผ่านทุก Edge เพียงครั้งเดียว (Leonhard Euler)

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