ปัญหาพนักงานขายเดินทาง: Python, C++ ขั้นตอนวิธี
ปัญหาพนักงานขายเดินทาง (TSP) คืออะไร?
ปัญหาพนักงานขายการเดินทาง (TSP) เป็นปัญหาเชิงผสมผสานแบบคลาสสิกของวิทยาการคอมพิวเตอร์เชิงทฤษฎี โจทย์ให้หาเส้นทางที่สั้นที่สุดในกราฟโดยมีเงื่อนไขให้ไปทุกจุดเพียงครั้งเดียวแล้วกลับเมืองต้นทาง
คำชี้แจงปัญหาจะแสดงรายชื่อเมืองพร้อมระยะทางระหว่างแต่ละเมือง
วัตถุประสงค์: หากต้องการเริ่มต้นจากเมืองต้นทางให้เยี่ยมชมเมืองอื่นเพียงครั้งเดียวแล้วกลับสู่เมืองเดิมอีกครั้ง เป้าหมายของเราคือการหาเส้นทางที่สั้นที่สุดที่เป็นไปได้เพื่อให้เส้นทางไปกลับเสร็จสมบูรณ์
ตัวอย่างของ TSP
ในที่นี้จะให้กราฟโดยที่ 1, 2, 3 และ 4 เป็นตัวแทนของเมือง และน้ำหนักที่เกี่ยวข้องกับทุกขอบแสดงถึงระยะห่างระหว่างเมืองเหล่านั้น
เป้าหมายคือการค้นหาเส้นทางที่สั้นที่สุดที่เป็นไปได้สำหรับการทัวร์ที่เริ่มต้นจากเมืองต้นทาง สำรวจกราฟในขณะที่เยี่ยมชมเมืองหรือโหนดอื่นเพียงครั้งเดียว และกลับไปยังเมืองต้นทาง
สำหรับกราฟด้านบน เส้นทางที่เหมาะสมที่สุดคือไปตามเส้นทางต้นทุนขั้นต่ำ: 1-2-4-3-1. และเส้นทางที่สั้นที่สุดนี้จะมีราคา 10+25+30+15 = 80
วิธีแก้ปัญหาต่างๆ สำหรับปัญหาพนักงานขายที่เดินทาง
ปัญหา Travelling Salesman (TSP) จัดอยู่ในประเภทปัญหา NP-hard เนื่องจากไม่มีอัลกอริทึมเวลาพหุนาม ความซับซ้อนจะเพิ่มขึ้นแบบเลขชี้กำลังเมื่อจำนวนเมืองเพิ่มขึ้น
มีหลายวิธีในการแก้ปัญหาพนักงานขายที่กำลังเดินทาง (ช้อนชา) โซลูชันยอดนิยมบางประการ ได้แก่:
วิธีเดรัจฉานกำลังเป็นวิธีที่ไร้เดียงสา เพื่อแก้ไขปัญหาพนักงานขายเดินทาง ในแนวทางนี้ ก่อนอื่นเราจะคำนวณเส้นทางที่เป็นไปได้ทั้งหมดแล้วจึงเปรียบเทียบ จำนวนเส้นทางในกราฟที่ประกอบด้วย n เมืองคือ n! การแก้ปัญหาพนักงานขายที่เดินทางด้วยวิธีการใช้กำลังเดรัจฉานนี้มีราคาแพงมากในการคำนวณ
วิธีการสาขาและขอบเขต: ปัญหาจะแบ่งออกเป็นปัญหาย่อยในแนวทางนี้ การแก้ปัญหาย่อยแต่ละปัญหาเหล่านั้นจะเป็นทางออกที่ดีที่สุด
บทช่วยสอนนี้จะสาธิตวิธีการเขียนโปรแกรมแบบไดนามิก ซึ่งเป็นเวอร์ชันแบบเรียกซ้ำของวิธีสาขาและขอบเขตนี้ เพื่อแก้ปัญหาพนักงานขายที่กำลังเดินทาง
การเขียนโปรแกรมแบบไดนามิก เป็นวิธีการในการแสวงหาแนวทางแก้ไขที่เหมาะสมที่สุดโดยการวิเคราะห์เส้นทางที่เป็นไปได้ทั้งหมด เป็นหนึ่งในวิธีการแก้ปัญหาที่แน่นอนที่ช่วยแก้ปัญหาพนักงานขายที่เดินทางด้วยต้นทุนที่ค่อนข้างสูงกว่า วิธีการโลภ ที่ให้วิธีแก้ปัญหาที่ใกล้เคียงที่สุด
ความซับซ้อนในการคำนวณของแนวทางนี้คือ โอ(น^2 * 2^น) ซึ่งจะกล่าวถึงในบทความนี้ในภายหลัง
วิธีเพื่อนบ้านที่ใกล้ที่สุด เป็นแนวทางแบบโลภที่อิงตามฮิวริสติก โดยเราเลือกโหนดเพื่อนบ้านที่ใกล้ที่สุด แนวทางนี้มีค่าใช้จ่ายในการคำนวณน้อยกว่าแนวทางแบบไดนามิก แต่ไม่ได้รับประกันผลลัพธ์ที่ดีที่สุด วิธีนี้ใช้สำหรับผลลัพธ์ที่ใกล้เคียงที่สุด
อัลกอริทึมสำหรับปัญหาพนักงานขายเดินทาง
เราจะใช้วิธีการเขียนโปรแกรมแบบไดนามิกเพื่อแก้ปัญหาการเดินทางของพนักงานขาย (TSP)
ก่อนที่จะเริ่มอัลกอริทึม เรามาทำความรู้จักกับคำศัพท์บางประการก่อน:
- กราฟ G=(V, E) ซึ่งเป็นเซตของจุดยอดและขอบ
- V คือเซตของจุดยอด
- E คือเซตของขอบ
- จุดยอดเชื่อมต่อกันผ่านขอบ
- Dist(i,j) หมายถึงระยะห่างที่ไม่เป็นลบระหว่างจุดยอดสองจุด นั่นคือ i และ j
สมมติว่า S เป็นเซตย่อยของเมืองและเป็นของ {1, 2, 3, …, n} โดยที่ 1, 2, 3…n คือเมืองต่างๆ และ i, j คือสองเมืองในกลุ่มย่อยนั้น ตอนนี้ราคา (i, S, j) ถูกกำหนดในลักษณะเดียวกับความยาวของเส้นทางที่สั้นที่สุดที่เยี่ยมชมโหนดใน S ซึ่งครั้งหนึ่งเคยมีจุดเริ่มต้นและจุดสิ้นสุดเป็น i และ j ตามลำดับ
ตัวอย่างเช่น ราคา (1, {2, 3, 4}, 1) แสดงถึงความยาวของเส้นทางที่สั้นที่สุดโดยที่:
- เมืองเริ่มต้นคือ 1
- เมืองที่ 2, 3 และ 4 มีการเยี่ยมชมเพียงครั้งเดียว
- จุดสิ้นสุดคือ 1
อัลกอริธึมการเขียนโปรแกรมแบบไดนามิกจะเป็น:
- กำหนดต้นทุน (i, , i) = 0 ซึ่งหมายความว่าเราเริ่มต้นและสิ้นสุดที่ i และต้นทุนคือ 0
- เมื่อ |ส| > 1 เรากำหนด cost(i, S, 1) = ∝ โดยที่ i !=1 เพราะในตอนแรกเราไม่ทราบค่าใช้จ่ายที่แน่นอนในการเข้าถึงเมือง i ถึงเมือง 1 ผ่านเมืองอื่น
- ตอนนี้เราต้องเริ่มต้นที่ 1 และทัวร์ให้จบ เราจำเป็นต้องเลือกเมืองต่อไปในลักษณะ-
ต้นทุน(i, S, j)=ต้นทุนขั้นต่ำ (i, S−{i}, j)+dist(i,j) โดยที่ i∈S และ i≠j
สำหรับรูปที่กำหนด เมทริกซ์ที่อยู่ติดกันจะเป็นดังต่อไปนี้:
dist(ฉัน,เจ) | 1 | 2 | 3 | 4 |
1 | 0 | 10 | 15 | 20 |
2 | 10 | 0 | 35 | 25 |
3 | 15 | 35 | 0 | 30 |
4 | 20 | 25 | 30 | 0 |
มาดูกันว่าอัลกอริทึมของเราทำงานอย่างไร:
ขั้นตอน 1) เรากำลังพิจารณาการเดินทางโดยเริ่มจากเมือง 1 ไปเที่ยวเมืองอื่นหนึ่งครั้งแล้วกลับเมือง 1
ขั้นตอน 2) S คือเซตย่อยของเมือง ตามอัลกอริทึมของเรา สำหรับ |S| > 1 ทั้งหมด เราจะตั้งค่าต้นทุนระยะทาง (i, S, 1) = ∝ โดยที่ต้นทุน (i, S, j) หมายถึงเราเริ่มต้นที่เมือง i โดยเยี่ยมชมเมืองต่างๆ ของ S หนึ่งครั้ง และตอนนี้เราอยู่ที่เมือง j เราตั้งค่าต้นทุนเส้นทางนี้เป็นอนันต์เนื่องจากเรายังไม่ทราบระยะทาง ดังนั้นค่าต่างๆ จะเป็นดังต่อไปนี้:
ราคา (2, {3, 4}, 1) = ∝ ; สัญลักษณ์แสดงว่าเรากำลังเริ่มต้นที่เมือง 2 ผ่านเมือง 3, 4 และไปถึง 1 และต้นทุนเส้นทางคืออนันต์ ในทำนองเดียวกัน-
ราคา(3, {2, 4}, 1) = ∝
ราคา(4, {2, 3}, 1) = ∝
ขั้นตอน 3) ตอนนี้ สำหรับเซตย่อยทั้งหมดของ S เราจำเป็นต้องค้นหาสิ่งต่อไปนี้:
cost(i, S, j)=min cost (i, S−{i}, j)+dist(i,j) โดยที่ j∈S และ i≠j
นั่นหมายถึงเส้นทางต้นทุนขั้นต่ำสำหรับการเริ่มต้นที่ i ผ่านส่วนย่อยของเมืองหนึ่งครั้ง และกลับสู่เมือง j เมื่อพิจารณาว่าการเดินทางเริ่มต้นที่เมือง 1 ต้นทุนเส้นทางที่เหมาะสมที่สุดจะเป็น= ต้นทุน (1, {เมืองอื่นๆ}, 1)
มาดูกันว่าเราจะบรรลุเป้าหมายดังกล่าวได้อย่างไร:
ตอนนี้ S = {1, 2, 3, 4} มีองค์ประกอบสี่ประการ ดังนั้นจำนวนเซตย่อยจะเป็น 2^4 หรือ 16 เซตย่อยเหล่านั้นคือ-
1) |ส| = ค่าว่าง:
{Φ}
2) |ส| = 1:
{{1}, {2}, {3}, {4}}
3) |ส| = 2:
{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
4) |ส| = 3:
{{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}
5) |ส| = 4:
{{1, 2, 3, 4}}
เมื่อเราเริ่มต้นที่ 1 เราสามารถละทิ้งเซตย่อยที่มีเมือง 1 ได้
การคำนวณอัลกอริทึม:
1) |ส| = Φ:
ราคา (2, Φ, 1) = dist(2, 1) = 10
ราคา (3, Φ, 1) = dist(3, 1) = 15
ราคา (4, Φ, 1) = dist(4, 1) = 20
2) |ส| = 1:
ราคา (2, {3}, 1) = dist(2, 3) + ราคา (3, Φ, 1) = 35+15 = 50
ราคา (2, {4}, 1) = dist(2, 4) + ราคา (4, Φ, 1) = 25+20 = 45
ราคา (3, {2}, 1) = dist(3, 2) + ราคา (2, Φ, 1) = 35+10 = 45
ราคา (3, {4}, 1) = dist(3, 4) + ราคา (4, Φ, 1) = 30+20 = 50
ราคา (4, {2}, 1) = dist(4, 2) + ราคา (2, Φ, 1) = 25+10 = 35
ราคา (4, {3}, 1) = dist(4, 3) + ราคา (3, Φ, 1) = 30+15 = 45
3) |ส| = 2:
ราคา (2, {3, 4}, 1) = นาที [ dist[2,3]+ราคา(3,{4},1) = 35+50 = 85,
dist[2,4]+ต้นทุน(4,{3},1) = 25+45 = 70 ] = 70
ราคา (3, {2, 4}, 1) = นาที [ dist[3,2]+ราคา(2,{4},1) = 35+45 = 80,
dist[3,4]+ต้นทุน(4,{2},1) = 30+35 = 65 ] = 65
ต้นทุน (4, {2, 3}, 1) = นาที [ dist[4,2]+ต้นทุน(2,{3},1) = 25+50 = 75
dist[4,3]+ต้นทุน(3,{2},1) = 30+45 = 75 ] = 75
4) |ส| = 3:
ราคา (1, {2, 3, 4}, 1) = นาที [ dist[1,2]+ราคา(2,{3,4},1) = 10+70 = 80
dist[1,3]+ต้นทุน(3,{2,4},1) = 15+65 = 80
dist[1,4]+ต้นทุน(4,{2,3},1) = 20+75 = 95 ] = 80
ดังนั้นทางออกที่ดีที่สุดก็คือ 1-2-4-3-1
รหัสเทียม
Algorithm: Traveling-Salesman-Problem Cost (1, {}, 1) = 0 for s = 2 to n do for all subsets S belongs to {1, 2, 3, … , n} of size s Cost (s, S, 1) = Infinity for all i Є S and i ≠ 1 Cost (i, S, j) = min {Cost (i, S – {i}, j) + dist(i, j) for j Є S and i ≠ j} Return min(i) Cost (i, {1, 2, 3, …, n}, j) + d(j, i)
การใช้งานใน C/C++
นี่คือการดำเนินการใน C++:
#include <bits/stdc++.h> using namespace std; #define V 4 #define MAX 1000000 int tsp(int graph[][V], int s) { vector<int> vertex; for (int i = 0; i < V; i++) if (i != s) vertex.push_back(i); int min_cost = MAX; while(next_permutation(vertex.begin(), vertex.end())) { int current_cost = 0; int j = s; for (int i = 0; i < vertex.size(); i++) { current_cost += graph[j][vertex[i]]; j = vertex[i]; } current_cost += graph[j][s]; min_cost = min(min_cost, current_cost); return min_cost; } } int main() { int graph[][V] = { { 0, 10, 15, 20 },{ 10, 0, 35, 25 },{ 15, 35, 0, 30 },{ 20, 25, 30, 0 } }; int s = 0; cout << tsp(graph, s) << endl; return 0; }
Output:
80
การนำไปปฏิบัติใน Python
from sys import maxsize from itertools, import permutations V = 4 def tsp(graph, s): vertex = [] for i in range(V): if i != s: vertex.append(i) min_cost = maxsize next_permutation=permutations(vertex) for i in next_permutation: current_cost = 0 k = s for j in i: current_cost += graph[k][j] k = j current_cost += graph[k][s] min_cost = min(min_cost, current_cost) return min_cost graph = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]] s = 0 print(tsp(graph, s))
Output:
80
โซลูชั่นทางวิชาการเพื่อ TSP
นักวิทยาศาสตร์คอมพิวเตอร์ใช้เวลาหลายปีในการค้นหาอัลกอริทึมเวลาพหุนามที่ดีขึ้นสำหรับปัญหา Travelling Salesman จนถึงตอนนี้ ปัญหานี้ยังคงเป็นปัญหา NP-hard
แม้ว่าโซลูชั่นบางส่วนต่อไปนี้จะได้รับการเผยแพร่ในช่วงไม่กี่ปีที่ผ่านมาซึ่งช่วยลดความซับซ้อนลงในระดับหนึ่ง:
- TSP แบบสมมาตรแบบคลาสสิกได้รับการแก้ไขโดยวิธี Zero Suffix
- อัลกอริธึมการปรับให้เหมาะสมตามชีวภูมิศาสตร์ขึ้นอยู่กับกลยุทธ์การย้ายถิ่นเพื่อแก้ไขปัญหาการปรับให้เหมาะสมที่สามารถวางแผนได้เป็น TSP
- อัลกอริทึมวิวัฒนาการหลายวัตถุประสงค์ได้รับการออกแบบมาเพื่อแก้ไข TSP หลายรายการโดยใช้ NSGA-II
- ระบบ Multi-Agent แก้ปัญหา TSP ของ N เมืองด้วยทรัพยากรคงที่
การประยุกต์ใช้ปัญหาพนักงานขายเดินทาง
ปัญหาพนักงานขายการเดินทาง (TSP) ถูกนำมาใช้ในโลกแห่งความเป็นจริงทั้งในรูปแบบที่บริสุทธิ์ที่สุดและแบบแก้ไข บางส่วนได้แก่:
- การวางแผน โลจิสติกส์ และการผลิตไมโครชิป: ปัญหาการใส่ชิปมักเกิดขึ้นในอุตสาหกรรมไมโครชิป ปัญหาเหล่านั้นสามารถวางแผนได้เป็นปัญหาของพนักงานขายที่เดินทาง
- การหาลำดับดีเอ็นเอ: การปรับเปลี่ยนปัญหาพนักงานขายที่เดินทางเล็กน้อยสามารถนำมาใช้ในการจัดลำดับดีเอ็นเอได้ ที่นี่ เมืองต่างๆ เป็นตัวแทนของชิ้นส่วน DNA และระยะทางแสดงถึงการวัดความคล้ายคลึงกันระหว่างชิ้นส่วน DNA สองชิ้น
- ดาราศาสตร์นักดาราศาสตร์ได้นำปัญหา Travelling Salesman Problem มาใช้เพื่อลดเวลาที่ใช้ในการสังเกตแหล่งที่มาต่างๆ
- ปัญหาการควบคุมที่เหมาะสมที่สุด: การกำหนดปัญหาของพนักงานขายที่เดินทางสามารถนำไปใช้ในปัญหาการควบคุมที่เหมาะสมที่สุด อาจมีข้อจำกัดอื่นๆ เพิ่มเข้ามาอีกหลายประการ
การวิเคราะห์ความซับซ้อนของ TSP
- ความซับซ้อนของเวลา: มีทั้งหมด 2N ปัญหาย่อยของแต่ละโหนด ดังนั้นจำนวนปัญหาย่อยทั้งหมดจะเป็น N*2N- แต่ละปัญหาย่อยต้องใช้เวลาเป็นเส้นตรงในการแก้ไข หากไม่ได้ระบุโหนดต้นทาง เราจะต้องรันลูปสำหรับโหนด N
ดังนั้นความซับซ้อนของเวลาทั้งหมดสำหรับโซลูชันที่เหมาะสมที่สุดจะเป็น จำนวนโหนด * จำนวนของปัญหาย่อย * เวลาในการแก้ปัญหาย่อยแต่ละปัญหา ความซับซ้อนของเวลาสามารถกำหนดเป็น O(N)2 * 2^น)
- ความซับซ้อนของอวกาศ: วิธีการเขียนโปรแกรมแบบไดนามิกใช้หน่วยความจำเพื่อจัดเก็บ C(S, i) โดยที่ S คือเซตย่อยของชุดจุดยอด มีทั้งหมด 2 อันN เซ็ตย่อยสำหรับแต่ละโหนด ดังนั้นความซับซ้อนของพื้นที่คือ O(2^N)
ต่อไปคุณจะได้เรียนรู้เกี่ยวกับ อัลกอริทึมตะแกรงของ Eratosthenes