ปัญหาการเดินทางของคนขายยา
ปัญหานี้เป็นปัญหาที่มีการกล่าวถึงและเป็นที่รู้จักกันดี สมมุติว่า มีพนักงานขายยาคนหนึ่ง ต้องการนำภาพยนตร์ไปฉายตามเมืองต่างๆ และโฆษณาขายยา ปรากฏว่าการเดินทางไปยังเมืองต่างๆ มีถนนเชื่อม เมืองเหล่านั้น มีระยะทางของถนนที่เชื่อมแต่ละเมืองเป็นข้อจำกัด พนักงานขายต้องการเดินทางไปให้ครบทุกเมือง แล้วกลับมายังจุดเริ่มต้นให้ได้ ระยะทางรวมกันสั้นที่สุด
ตัวอย่างเช่น มีเมือง ห้า เมือง คือ A,B,C,D และ S พนักงานขายอยู่ที่เมือง S ต้องการเดินทางไปยังเมืองต่างๆ โดยแผนผังการเชื่อมโยงแต่ละเมือง แสดงดังรูป
วิธีแก้ปัญหานี้ก็เพื่อให้ได้คำตอบที่ดีที่สุด คือเดินทางได้ระยะทางรวมกันน้อยที่สุด สำหรับคำตอบของกรณีนี้คือ เริ่มจาก S เดินทางไปยัง A,B,C และ D ตามลำดับ แล้วกลับมายัง S ทำนองเดียวกันกับปัญหาเรื่องเขาวงกตคือ หากให้จำนวนเมืองมีมากขึ้น การแก้ปัญหานี้จะซับซ้อนมากขึ้น และอาจยุ่งยากซับซ้อนมากตามจำนวนของเมืองที่มีอยู่ในปัญหา
ที่มา : รศ. ยืน ภู่วรวรรณ, สำนักบริการคอมพิวเตอร์ มหาวิทยาลัยเกษตรศาสตร์