เครื่องแก้ปัญหาพนักงานขายเดินทาง (TSP)

ค้นหาเส้นทางที่สั้นที่สุดในการเยี่ยมชมเมืองทุกเมืองเพียงครั้งเดียวและกลับไปยังจุดเริ่มต้น ใช้การคำนวณแบบ Dynamic Programming (Held-Karp) สำหรับจำนวนเมืองน้อย และใช้ Heuristics แบบ Nearest-Neighbor + 2-opt สำหรับจำนวนเมืองที่มากขึ้น รองรับทั้งพิกัดหรือเมทริกซ์ระยะทาง พร้อมแสดงผลการเดินทางแบบ SVG เคลื่อนไหว

ตัวอย่างด่วน:

5 เมือง รูปสี่เหลี่ยม+ยอด 8 เมืองแบบสุ่ม 8 เมืองหลวงใน EU เมทริกซ์ 4×4 เกณฑ์มาตรฐาน 10 เมือง รูปสามเหลี่ยม (เส้นทางแบบเปิด)

⌖ พิกัด (x, y) ▦ เมทริกซ์ระยะทาง

เมืองหรือเมทริกซ์

บรรทัดพิกัด: A, 10, 20 หรือ 10 20 บรรทัดเมทริกซ์: 0 10 15 20 — หนึ่งแถวต่อบรรทัด, เป็นรูปจัตุรัส, ค่าไม่เป็นลบ สูงสุด 40 เมือง

ป้ายกำกับเมทริกซ์ (ไม่จำเป็น)

ป้ายกำกับแยกด้วยจุลภาคหรือเว้นวรรค หนึ่งป้ายต่อแถวเมทริกซ์ หากละไว้จะใช้ A, B, C... โดยอัตโนมัติ

อัลกอริทึม

ประเภทเส้นทาง

Embed เครื่องแก้ปัญหาพนักงานขายเดินทาง (TSP) Widget

เกี่ยวกับ เครื่องแก้ปัญหาพนักงานขายเดินทาง (TSP)

เครื่องแก้ปัญหาพนักงานขายเดินทาง เป็นเครื่องคำนวณเชิงการศึกษาและใช้งานจริงสำหรับ ปัญหาพนักงานขายเดินทาง (Traveling Salesman Problem - TSP) แบบดั้งเดิม: เมื่อกำหนดชุดของเมืองและระยะทางระหว่างคู่เมือง ให้หาเส้นทางที่สั้นที่สุดที่เป็นไปได้ซึ่งไปเยือนทุกเมืองเพียงครั้งเดียวและกลับสู่จุดเริ่มต้น เครื่องมือนี้รองรับทั้งพิกัดระนาบหรือเมทริกซ์ระยะทางที่กำหนดเอง เลือกอัลกอริทึมที่ดีที่สุดโดยอัตโนมัติตามขนาดของปัญหา และแสดงผลเส้นทางที่ได้เป็นแผนที่ SVG แบบเคลื่อนไหว

ปัญหาพนักงานขายเดินทางคืออะไร?

ในทางทฤษฎี เมื่อกำหนดกราฟถ่วงน้ำหนักที่สมบูรณ์ G = (V, E) โดยมีชุดจุดยอด V = {1, 2, ..., n} และน้ำหนักเส้นเชื่อม d(i, j) ปัญหา TSP จะหาการเรียงสับเปลี่ยน π ของจุดยอดที่ให้ค่าต่ำสุดของ:

minimize Σ_i=1^n-1 d(π(i), π(i+1)) + d(π(n), π(1))

พจน์สุดท้ายคือการปิดวงจร TSP เป็นหนึ่งในปัญหาที่เก่าแก่ที่สุดและมีการศึกษากันมากที่สุดในการหาค่าที่เหมาะสมที่สุดเชิงจัดหมู่ มันเป็นปัญหาประเภท NP-hard ในกรณีทั่วไป ซึ่งหมายความว่าไม่มีอัลกอริทึมที่รู้จักที่สามารถแก้ปัญหาได้ทุกกรณีในเวลาพหุนาม อย่างไรก็ตาม มันปรากฏในการประยุกต์ใช้ในโลกแห่งความเป็นจริงมากมาย: การวางเส้นทางยานพาหนะ, การเจาะแผงวงจร PCB, การจัดลำดับ DNA, เส้นทางการเลือกสินค้าในคลังสินค้า, ตารางการสังเกตการณ์ทางดาราศาสตร์ และแม้แต่การส่งไปรษณีย์ในชนบท

เครื่องมือนี้ทำงานอย่างไร

การเขียนโปรแกรมแบบไดนามิก Held–Karp (แม่นยำ)

สำหรับกรณีขนาดเล็ก (สูงสุด 12 เมือง) ระบบจะคำนวณเส้นทางที่พิสูจน์ได้ว่าเหมาะสมที่สุดโดยใช้อัลกอริทึม Held–Karp ซึ่งตีพิมพ์โดย Richard Bellman และ Michael Held & Richard Karp ในปี 1962 ความสัมพันธ์เวียนเกิดที่สำคัญคือ C(S, j) ซึ่งเป็นเส้นทางที่สั้นที่สุดจากจุดยอด 1 ไปยังจุดยอด j โดยผ่านชุดย่อย S พอดี:

C(S, j) = min_{k ∈ S \ {j}} [ C(S \ {j}, k) + d(k, j) ]

ต้นทุนเส้นทางที่เหมาะสมที่สุดคือ min_j [C({1,...,n}, j) + d(j, 1)] อัลกอริทึม Held–Karp ทำงานในเวลา O(2ⁿ · n²) และหน่วยความจำ O(2ⁿ · n) ซึ่งเป็นการปรับปรุงครั้งใหญ่จากวิธี Brute Force n! แต่ก็ยังเป็นแบบเอกซ์โพเนนเชียล เมื่อเกินกว่า 20 เมือง การใช้หน่วยความจำจะเริ่มเป็นไปไม่ได้ในทางปฏิบัติ

Nearest-Neighbor + 2-opt (ฮิวริสติก)

สำหรับกรณีที่มีขนาดใหญ่ขึ้น ระบบจะใช้ฮิวริสติกสองขั้นตอน ขั้นแรก Nearest-Neighbor จะสร้างเส้นทางอย่างรวดเร็วโดยการเดินไปยังเมืองที่ใกล้ที่สุดที่ยังไม่ได้ไปเยือนจากจุดเริ่มต้นแต่ละจุด ระบบจะลองใช้จุดเริ่มต้นหลายๆ จุดและเก็บเส้นทางที่ดีที่สุดไว้ จากนั้นการค้นหาเฉพาะที่แบบ 2-opt จะปรับปรุงเส้นทางโดยการลบเส้นเชื่อมสองเส้นซ้ำๆ และเชื่อมต่อเส้นทางที่ได้ใหม่ในอีกทางหนึ่งที่เป็นไปได้:

ก่อน: ... a — b ... c — d ... หลังการสลับแบบ 2-opt: ... a — c ... b — d ... ถ้า d(a,c) + d(b,d) < d(a,b) + d(c,d) → ยอมรับการสลับ, กลับลำดับเส้นทางย่อย b..c

ในทางเรขาคณิต 2-opt จะกำจัด "จุดตัด" ในเส้นทาง: เส้นเชื่อมสองเส้นใดๆ ที่ตัดกันสามารถเปลี่ยนเป็นแบบไม่ตัดกันเพื่อให้ได้ความยาวรวมที่สั้นลงได้เสมอ อัลกอริทึมจะหยุดที่ค่าเหมาะสมที่สุดเฉพาะที่ซึ่งไม่มีการสลับใดที่ช่วยให้ดีขึ้นได้ เรียกว่าเส้นทางแบบ 2-optimal ในกรณีแบบยุคลิดที่เหมือนจริง 2-opt มักจะพบเส้นทางที่อยู่ภายใน 2–5% ของค่าที่เหมาะสมที่สุดจริงในเวลาเพียงไม่กี่มิลลิวินาที

รูปแบบการนำเข้าข้อมูล

โหมดพิกัด (x, y)

หนึ่งเมืองต่อบรรทัด แต่ละบรรทัดคือ ป้ายกำกับ, x, y — ป้ายกำกับเป็นตัวเลือกเสริม ระบบจะคำนวณระยะทางแบบยุคลิดโดยอัตโนมัติและแสดงผลเมืองในตำแหน่งจริง

A, 10, 20 B, 40, 70 C, 75, 30 Paris: 2.35, 48.86 10 20 ← ตั้งชื่ออัตโนมัติ C1

โหมดเมทริกซ์ระยะทาง

เมทริกซ์จัตุรัสขนาด n × n ของระยะทางที่ไม่เป็นลบ หนึ่งแถวต่อบรรทัด ค่าแยกด้วยเว้นวรรคหรือจุลภาค เมทริกซ์อาจเป็นแบบสมมาตรหรือไม่สมมาตรก็ได้ — เมทริกซ์ที่ไม่สมมาตรจำลองถนนเดินรถทางเดียว ราคาเที่ยวบินที่มีความพร้อมจำกัด และการเดินทางที่ขึ้นอยู่กับลม คุณสามารถระบุป้ายกำกับในช่องป้ายกำกับเมทริกซ์ได้

0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0

การเปรียบเทียบอัลกอริทึม

อัลกอริทึม	ความซับซ้อนของเวลา	หน่วยความจำ	คุณภาพผลลัพธ์	ขนาดที่ใช้ได้จริง
Brute force	O(n!)	O(n)	เหมาะสมที่สุด	n ≤ 10
Held–Karp DP	O(2ⁿ · n²)	O(2ⁿ · n)	เหมาะสมที่สุด	n ≤ 20
Nearest-Neighbor	O(n²)	O(n)	~แย่กว่าเหมาะสมที่สุด 25%	n ≤ หลักพัน
NN + 2-opt	O(n² · จำนวนรอบ)	O(n)	~แย่กว่าเหมาะสมที่สุด 2–5%	n ≤ หลักร้อย

วิธีใช้งานเครื่องแก้ปัญหานี้

เลือกโหมดการนำเข้าข้อมูล พิกัดหากเมืองของคุณมีตำแหน่ง (x, y) ที่มีความหมาย; เมทริกซ์ระยะทางหากต้นทุนของคุณไม่ใช่แบบยุคลิดหรือไม่สมมาตร
วางหรือพิมพ์ข้อมูลของคุณ หนึ่งเมืองหรือหนึ่งแถวต่อบรรทัด คลิกปุ่มตัวอย่างด่วนเหนือแบบฟอร์มเพื่อกรอกตัวอย่างที่ถูกต้อง
เลือกอัลกอริทึม ปล่อยไว้ที่ อัตโนมัติ เพื่อการตั้งค่าเริ่มต้นที่เหมาะสม: Held–Karp เมื่อขนาดปัญหาเล็กพอที่จะพิสูจน์ความเหมาะสมที่สุดได้, นอกนั้นใช้ NN + 2-opt บังคับใช้อัลกอริทึมเฉพาะหากต้องการเปรียบเทียบ
เลือกแบบปิดหรือเปิด เส้นทางแบบปิดจะกลับไปยังจุดเริ่มต้น — คือ TSP แบบดั้งเดิม โหมดเส้นทางแบบเปิดจะแก้ปัญหาเส้นทางแฮมิลตันที่เกี่ยวข้องซึ่งพนักงานขายสิ้นสุดที่เมืองอื่น
คลิก แก้ปัญหา หน้าผลลัพธ์จะแสดงความยาวเส้นทางรวม, ภาพเคลื่อนไหว SVG ของเส้นทาง (คลิก "เล่นภาพเคลื่อนไหวอีกครั้ง" เพื่อเล่นซ้ำ), ลำดับเมืองทั้งหมด, รายละเอียดต่อเส้นเชื่อม และเมทริกซ์ระยะทางที่มีการไฮไลท์เส้นเชื่อมที่ใช้ในเส้นทาง

ตัวอย่างการทำงาน

พิจารณาห้าเมือง — สี่เหลี่ยมผืนผ้าบวกยอด: A (0, 0), B (4, 0), C (4, 3), D (0, 3), E (2, 5) ระบบจะให้ผลลัพธ์ดังนี้:

เส้นทาง: A → D → E → C → B → A
ความยาว: 3 + √8 + √8 + 3 + 4 ≈ 15.66
เหมาะสมที่สุดหรือไม่? ใช่ — Held–Karp พิสูจน์แล้วว่าไม่มีเส้นทางที่สั้นกว่านี้
ทำไมต้องลำดับนี้? เส้นทางเดินตามขอบเขตของจุดทั้งห้า (A → D → E → C → B → A) คุณสมบัติคลาสสิกของ Euclidean TSP คือเส้นทางที่เหมาะสมที่สุดจะไปเยือนจุดบนขอบเขตในลำดับวงกลม จุดภายในจะแทรกอยู่ระหว่างเพื่อนบ้านที่อยู่บนขอบเขต เส้นทางใดๆ ที่ตัดกันเอง เช่น A → C → B → D → E → A (ความยาว ≈ 21.8) สามารถเปลี่ยนให้ไม่ตัดกันได้เสมอโดย 2-opt เพื่อให้ได้ผลลัพธ์ที่สั้นลง

การประยุกต์ใช้ในโลกแห่งความเป็นจริง

โลจิสติกส์และการส่งสินค้า — ปรับเส้นทางประจำวันของคนขับผ่านจุดจอด 15 จุดเพื่อลดเชื้อเพลิงและเวลา
การผลิต — จัดลำดับรูที่สว่าน CNC ต้องเจาะบนแผงวงจร PCB เพื่อลดการเคลื่อนที่ของหัวเจาะ
การจัดลำดับจีโนม — จัดลำดับชิ้นส่วน DNA ตามความคล้ายคลึงของส่วนที่ซ้อนทับกัน โดยเข้ารหัสเป็นเมทริกซ์ระยะทาง
ดาราศาสตร์ — จัดตารางการหันกล้องโทรทรรศน์ระหว่างดวงดาวเป้าหมายเพื่อเพิ่มเวลาการสังเกตการณ์ให้สูงสุด
การเลือกสินค้าในคลังสินค้า — จัดลำดับการไปที่ช่องเก็บของเพื่อเตรียมคำสั่งซื้อด้วยจำนวนก้าวที่น้อยที่สุด
การวางแผนท่องเที่ยว — วางแผนทริปท่องเที่ยวหลายเมืองที่ลดเวลาเดินทางและค่าโดยสารให้น้อยที่สุด

คำถามที่พบบ่อย

ปัญหาพนักงานขายเดินทางคืออะไร?

ปัญหาพนักงานขายเดินทาง (TSP) คือการหาเส้นทางที่สั้นที่สุดที่เป็นไปได้ซึ่งไปเยือนทุกเมืองเพียงครั้งเดียวและกลับมายังเมืองเริ่มต้น เป็นหนึ่งในปัญหาที่มีชื่อเสียงที่สุดในการหาค่าที่เหมาะสมที่สุดเชิงจัดหมู่ และเป็นปัญหาประเภท NP-hard ในกรณีทั่วไป หมายความว่าไม่มีอัลกอริทึมที่รู้จักที่สามารถแก้ปัญหาได้ทุกกรณีในเวลาพหุนาม

อัลกอริทึม Held–Karp คืออะไร?

Held–Karp เป็นอัลกอริทึมการเขียนโปรแกรมแบบไดนามิกที่แก้ปัญหา TSP ได้อย่างแม่นยำในเวลา O(2ⁿ · n²) และหน่วยความจำ O(2ⁿ · n) มันเร็วกว่าวิธี Brute Force อย่างมากแต่ยังคงเป็นแบบเอกซ์โพเนนเชียล ดังนั้นในทางปฏิบัติจึงใช้สำหรับเมืองไม่เกิน 20 เมือง เครื่องมือนี้ใช้ Held–Karp เมื่อมีเมืองไม่เกิน 12 เมือง

2-opt คืออะไรและทำไมจึงถูกนำมาใช้?

2-opt เป็นฮิวริสติกการค้นหาเฉพาะที่ซึ่งจะลบเส้นเชื่อมสองเส้นออกจากเส้นทางปัจจุบันซ้ำๆ แล้วเชื่อมต่อเส้นทางที่เหลือทั้งสองเข้าด้วยกันในอีกรูปแบบหนึ่งที่เป็นไปได้ เมื่อเส้นทางใหม่สั้นลงจะเก็บการสลับนั้นไว้ 2-opt ทำงานในเวลาพหุนามต่อรอบการทำงานและสม่ำเสมอในการค้นหาเส้นทางที่ใกล้เคียงกับค่าที่เหมาะสมที่สุดภายในไม่กี่เปอร์เซ็นต์ ซึ่งเป็นเหตุผลว่าทำไมมันจึงเป็นฮิวริสติกยอดนิยมสำหรับปัญหา TSP ขนาดใหญ่

ควรใช้พิกัดหรือเมทริกซ์ระยะทางเมื่อใด?

ใช้พิกัดเมื่อเมืองของคุณอยู่ในระนาบที่มีระยะทางเป็นเส้นตรง เช่น จุดบนแผนที่ หรือตำแหน่งคลังสินค้า ใช้เมทริกซ์ระยะทางเมื่อต้นทุนระหว่างคู่เมืองไม่ใช่แบบยุคลิด เช่น ราคาเที่ยวบิน หรือเวลาเดินทางที่มีการจราจร โหมดเมทริกซ์ยอมรับระยะทางที่ไม่เป็นลบใดๆ แม้กระทั่งแบบไม่สมมาตร

คำตอบจาก 2-opt เป็นค่าที่เหมาะสมที่สุดหรือไม่?

ไม่ 2-opt จะให้เส้นทางแบบ 2-optimal ซึ่งหมายความว่าไม่มีเส้นเชื่อมคู่ใดที่สามารถสลับเพื่อสร้างเส้นทางที่สั้นกว่าได้ นี่คือค่าที่เหมาะสมที่สุดเฉพาะที่ และมักจะอยู่ภายในไม่กี่เปอร์เซ็นต์ของค่าที่เหมาะสมที่สุดในระดับโลก แต่ไม่ได้รับประกันว่าเป็นค่าที่ดีที่สุดในระดับโลก สำหรับเส้นทางที่พิสูจน์ได้ว่าเหมาะสมที่สุด ให้เลือก Held–Karp

เครื่องมือนี้รองรับเมทริกซ์ระยะทางที่ไม่สมมาตรหรือไม่?

รองรับ ในโหมดเมทริกซ์ระยะทาง คุณสามารถป้อนเมทริกซ์จัตุรัสที่ไม่เป็นลบได้ทุกรูปแบบ รวมถึงแบบไม่สมมาตรที่ D[i][j] แตกต่างจาก D[j][i] ทั้ง Held–Karp และ 2-opt สามารถจัดการกับเมทริกซ์ที่ไม่สมมาตรได้อย่างถูกต้อง สิ่งนี้มีประโยชน์สำหรับปัญหาการวางเส้นทางที่มีถนนเดินรถทางเดียว หรือการเดินทางที่ขึ้นอยู่กับทิศทางลม

อ่านเพิ่มเติม

อ้างอิงเนื้อหา หน้าหรือเครื่องมือนี้ว่า:

"เครื่องแก้ปัญหาพนักงานขายเดินทาง (TSP)" ที่ https://MiniWebtool.com/th/เครื่องแก้ปัญหาพนักงานขายเดินทาง-tsp/ จาก MiniWebtool, https://MiniWebtool.com/

โดยทีมงาน miniwebtool อัปเดตเมื่อ: 21 เม.ย. 2026

คุณสามารถลองใช้ AI แก้ปัญหาคณิตศาสตร์ GPT ของเรา เพื่อแก้ไขปัญหาทางคณิตศาสตร์ของคุณผ่านคำถามและคำตอบด้วยภาษาธรรมชาติ.