ตามหัวข้อเลยค่ะ

ปัญหานี้คล้ายกับ Traveling-salesman problem แต่เราสนใจเฉพาะกรณีเมื่อความยาวของเส้นเชื่อมระหว่างจุดยอดสองจุดใดๆ คือระยะทางระหว่างสองจุดนั้นบนระนาบแบบยุคลิค(Euclidean plane) ซึ่งหมายความว่าความยาวของเส้นเชื่อมต่างๆ ที่เชื่อมสามเมืองใดๆ ต้องเป็นไปตามสมการอิงรูปสามเหลี่ยม(triangle inequality) นั่นคือผลรวมของความยาวด้านทั้ง สองด้านใดๆ ต้องไม่น้อยกว่าด้านที่สาม(ซึ่งระยะทางของเมืองต่างๆ บนระนาบแบบยุคลิดมีคุณสมบัติข้อนี้) นอกจากนี้ยังมีเงื่อนไขเพิ่มเติมว่าวงจรต้องเป็นแบบ bitonic นั่นคือ ให้วงจรเริ่มที่จุดยอดซ้ายสุดจากนั้นไปทางขวาเรื่อยๆ จนถึงยอดขวาสุด แล้วจึงเริ่มเปลี่ยนทิศทางมาทางซ้ายเรื่อยๆ จนถึงจุดยอดเริ่มต้นเดิมรูปซ้ายข้างล่างนี้ ไม่ใช่วงจรแบบ bitonic ในขณะที่รูปขวาเป็นแบบวงจรแบบ bitonic
จงออกแบบอัลกอริทึมที่ใช้เวลาน้อยที่สุด เพื่อหาการเดินทางของพนักงานตามแบบข้อมูลที่กำหนด(สมมติให้จุดยอดทุกจุดมีพิกัดในแนวแกน x ไม่เหมือนกันเลย)

ขอบคุณล่วงหน้าค่ะ . ..