Variations• Hamiltonian Cycle– Is t

Variations
• Hamiltonian Cycle
– Is there a cycle that visits each vertex exactly once
– Ignores costs
• Triangle inequality constraint
– C(u,v) < C(u,x) + C(x,v)
• Euclidean Traveling Salesman
– Vertices are points on the plane and the cost is
the Euclidian distance between them
– Implies triangle inequality

ผลลัพธ์ (ไทย) 1:

ความแตกต่าง• Hamiltonian วงจร– จะมีวงจรที่เข้าชมแต่ละจุดเหมือนกัน-ละเว้นต้นทุน•สามเหลี่ยมอสมการข้อจำกัด– C(u,v) < C(u,x) + C(x,v)•ขาย Traveling Euclidean-จุดยอดเป็นจุดบนเครื่องบิน และต้นทุนEuclidian ระยะห่างระหว่างพวกเขา-ความหมายของอสมการสามเหลี่ยม

ผลลัพธ์ (ไทย) 2:

รูปแบบ
•วงจรมิลโตเนียน
- มีวงจรที่เข้าชมแต่ละจุดสุดยอดครั้งว่า
- ละเว้นค่าใช้จ่าย
• จำกัด สามเหลี่ยมความไม่เท่าเทียมกัน
- C (U, V) <C (U, x) + C (x, V)
•ยุคลิดเดินทางพนักงานขาย
- จุดที่ จุดบนเครื่องบินและค่าใช้จ่ายเป็น
ระยะ Euclidian ระหว่างพวกเขา
- นัยสามเหลี่ยมความไม่เท่าเทียมกัน

ผลลัพธ์ (ไทย) 3:

การเปลี่ยนแปลง
-
( Hamiltonian วงจรมีวงจรที่เข้าชมแต่ละจุดยอดที่แน่นอนอีกครั้ง
-
- สามเหลี่ยมอสมการข้อจำกัดไม่สนใจต้นทุน– c ( u , v
) < C ( u , x ) c ( x , v )
-
( ใช้พนักงานขายเดินทางจุดเป็นจุดที่เครื่องบินและค่าใช้จ่ายคือ

euclidian ระยะห่างระหว่างพวกเขา ( หมายถึงรูปสามเหลี่ยม