ปัญหาพนักงานขายเดินทาง: Python, C++ ขั้นตอนวิธี

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

ปัญหาพนักงานขายการเดินทาง (TSP) เป็นปัญหาเชิงผสมผสานแบบคลาสสิกของวิทยาการคอมพิวเตอร์เชิงทฤษฎี โจทย์ให้หาเส้นทางที่สั้นที่สุดในกราฟโดยมีเงื่อนไขให้ไปทุกจุดเพียงครั้งเดียวแล้วกลับเมืองต้นทาง

คำชี้แจงปัญหาจะแสดงรายชื่อเมืองพร้อมระยะทางระหว่างแต่ละเมือง

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

ตัวอย่างของ TSP

ในที่นี้จะให้กราฟโดยที่ 1, 2, 3 และ 4 เป็นตัวแทนของเมือง และน้ำหนักที่เกี่ยวข้องกับทุกขอบแสดงถึงระยะห่างระหว่างเมืองเหล่านั้น

ตัวอย่างของ TSP

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

สำหรับกราฟด้านบน เส้นทางที่เหมาะสมที่สุดคือไปตามเส้นทางต้นทุนขั้นต่ำ: 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