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

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

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

โจทย์กำหนดรายชื่อเมืองพร้อมระยะทางระหว่างเมืองแต่ละคู่มาให้

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

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

พิจารณากราฟด้านล่าง ซึ่ง 1, 2, 3 และ 4 แทนเมืองต่างๆ และน้ำหนักบนเส้นเชื่อมแต่ละเส้นแสดงถึงระยะห่างระหว่างเมืองเหล่านั้น

เป้าหมายคือการค้นหาเส้นทางท่องเที่ยวที่สั้นที่สุด โดยเริ่มต้นจากเมืองต้นทาง แวะเยี่ยมชมเมืองอื่นๆ ทุกเมืองเพียงครั้งเดียว และกลับมายังเมืองต้นทางอีกครั้ง

จากกราฟด้านบน เส้นทางที่เหมาะสมที่สุดคือ 1-2-4-3-1ค่าใช้จ่ายในการเดินทางที่สั้นที่สุดคือ 10 + 25 + 30 + 15 = 80.

วิธีแก้ปัญหาต่างๆ สำหรับปัญหาพนักงานขายที่เดินทาง

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

มีหลายวิธีในการแก้ปัญหา TSP วิธีที่พบได้บ่อยที่สุด ได้แก่:

วิธีการใช้กำลังอย่างไม่ยั้งคิด: วิธีการแบบง่ายจะคำนวณเส้นทางที่เป็นไปได้ทั้งหมดแล้วนำมาเปรียบเทียบกัน จำนวนเส้นทางในกราฟที่มีเมือง n เมืองคือ n!ซึ่งทำให้การคำนวณด้วยวิธี Brute Force มีค่าใช้จ่ายสูงมากสำหรับเมืองที่มีขนาดใหญ่กว่าประมาณสิบเมือง

วิธีการแยกสาขาและจำกัดขอบเขต (Branch and Bound Method): ปัญหาจะถูกแบ่งออกเป็นปัญหาย่อย และผลลัพธ์ของการแก้ปัญหาย่อยเหล่านั้นจะรวมกันเป็นผลลัพธ์ที่ดีที่สุด การตัดแต่งเส้นทางอย่างมีประสิทธิภาพจะกำจัดเส้นทางที่ไม่สมบูรณ์ซึ่งไม่สามารถเอาชนะต้นทุนที่ดีที่สุดในปัจจุบันได้

คู่มือนี้สาธิตวิธีการ วิธีการเขียนโปรแกรมแบบไดนามิกซึ่งเป็นเวอร์ชันที่ใช้การจดจำผลลัพธ์ (memoization) ของวิธีการแยกสาขาและจำกัดขอบเขต (branch and bound) และตรงกับอัลกอริทึม Bellman-Held-Karp

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

ความซับซ้อนในการคำนวณของแนวทางนี้คือ O(N² × 2^N)ซึ่งเราจะกล่าวถึงในภายหลังในบทความนี้

วิธีเพื่อนบ้านที่ใกล้ที่สุด: วิธีการค้นหาแบบฮิวริสติกส์ที่โลภ (greedy) ซึ่งจะกระโดดไปยังเมืองที่ยังไม่เคยไปเยือนที่ใกล้ที่สุดเสมอ วิธีนี้ประหยัดกว่าการเขียนโปรแกรมแบบไดนามิกมาก แต่ไม่รับประกันว่าจะได้เส้นทางที่ดีที่สุด ดังนั้นจึงใช้สำหรับหาคำตอบที่ใกล้เคียงกับค่าต่ำสุดเมื่อความเร็วมีความสำคัญมากกว่าค่าต่ำสุดที่แน่นอน

อัลกอริทึมสำหรับปัญหาพนักงานขายเดินทาง

เราใช้วิธีการเขียนโปรแกรมเชิงพลวัต (Dynamic Programming) ในการแก้ปัญหา TSP ก่อนที่จะเริ่มอัลกอริทึม เรามาทำความเข้าใจคำศัพท์บางคำกันก่อน:

• กราฟ G = (V, E) คือเซตของจุดยอดและเส้นขอบ
• V คือเซตของจุดยอด
• E คือชุดของขอบ
• จุดยอดเชื่อมต่อกันผ่านขอบ
• Dist(i, j) แสดงถึงระยะทางที่ไม่เป็นลบระหว่างจุดยอด i และ j

สมมติให้ S เป็นเซตย่อยของเมืองที่สุ่มมาจาก {1, 2, 3, …, n} โดยที่ i และ j เป็นเมืองสองเมืองในเซตย่อยนั้น แล้ว cost(i, S, j) คือความยาวของเส้นทางที่สั้นที่สุดที่เริ่มต้นที่ i ผ่านทุกเมืองใน S เพียงครั้งเดียว และสิ้นสุดที่ j

ตัวอย่างเช่น cost(1, {2, 3, 4}, 1) หมายถึงเส้นทางที่สั้นที่สุด โดยที่:

• เมืองเริ่มต้นคือ 1
• เมืองที่ 2, 3 และ 4 มีการเยี่ยมชมเพียงครั้งเดียว
• จุดสิ้นสุดคือ 1

ความสัมพันธ์เวียนเกิดของการเขียนโปรแกรมเชิงพลวัตคือ:

• ชุด cost(i, {}, i) = 0ซึ่งหมายความว่าเราเริ่มต้นและสิ้นสุดที่ i โดยไม่มีค่าใช้จ่าย
• เมื่อ |S| > 1, กำหนด cost(i, S, 1) = ∞ สำหรับ i ≠ 1เนื่องจากยังไม่ทราบค่าใช้จ่ายที่แท้จริงของการทัวร์
• เริ่มต้นที่เมืองที่ 1 เลือกเมืองถัดไปเพื่อให้ cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] สำหรับ i ∈ S และ i ≠ j.

สำหรับกราฟด้านบน เมทริกซ์ประชิดมีดังนี้:

ต่อไปนี้คือขั้นตอนการทำงานของอัลกอริธึม:

ขั้นตอน 1) การเดินทางเริ่มต้นที่เมืองที่ 1 เยี่ยมชมเมืองอื่นๆ ทุกเมืองหนึ่งครั้ง แล้วกลับมายังเมืองที่ 1 อีกครั้ง

ขั้นตอน 2) S คือเซตย่อยของเมืองต่างๆ สำหรับทุก |S| > 1 ให้เริ่มต้นค่า cost(i, S, 1) = ∞. ที่นี่ cost(i, S, j) หมายถึงเส้นทางการเดินทางที่เริ่มต้นที่ i เยี่ยมชมเมืองต่างๆ ใน ​​S หนึ่งครั้ง และไปถึง j เราเริ่มต้นจากอนันต์เพราะไม่ทราบระยะทาง ณ จุดนี้ ดังนั้นค่าต่างๆ คือ:

cost(2, {3, 4}, 1) = ∞ หมายความว่าเราเริ่มต้นที่เมืองที่ 2 ผ่านเมืองที่ 3 และ 4 แล้วไปถึงเมืองที่ 1 โดยมีค่าใช้จ่ายที่ไม่ทราบแน่ชัด ในทำนองเดียวกัน:

cost(3, {2, 4}, 1) = ∞

cost(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 ดังนั้นต้นทุนที่เหมาะสมที่สุดคือ cost(1, {other cities}, 1).

ดำเนินการตามขั้นตอนการเกิดซ้ำทีละขั้นตอน

ตอนนี้ S = {1, 2, 3, 4} มีสมาชิกสี่ตัว ดังนั้นจำนวนเซตย่อยคือ 2^4 = 16กลุ่มย่อยเหล่านั้นได้แก่:

1) |ส| = 0: {Φ}

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) |ส| = Φ:

• cost(2, Φ, 1) = dist(2, 1) = 10
• cost(3, Φ, 1) = dist(3, 1) = 15
• cost(4, Φ, 1) = dist(4, 1) = 20

2) |ส| = 1:

• cost(2, {3}, 1) = dist(2, 3) + cost(3, Φ, 1) = 35 + 15 = 50
• cost(2, {4}, 1) = dist(2, 4) + cost(4, Φ, 1) = 25 + 20 = 45
• cost(3, {2}, 1) = dist(3, 2) + cost(2, Φ, 1) = 35 + 10 = 45
• cost(3, {4}, 1) = dist(3, 4) + cost(4, Φ, 1) = 30 + 20 = 50
• cost(4, {2}, 1) = dist(4, 2) + cost(2, Φ, 1) = 25 + 10 = 35
• cost(4, {3}, 1) = dist(4, 3) + cost(3, Φ, 1) = 30 + 15 = 45

3) |ส| = 2:

• cost(2, {3, 4}, 1) = min [ dist(2, 3) + cost(3, {4}, 1) = 35 + 50 = 85, dist(2, 4) + cost(4, {3}, 1) = 25 + 45 = 70 ] = 70
• cost(3, {2, 4}, 1) = min [ dist(3, 2) + cost(2, {4}, 1) = 35 + 45 = 80, dist(3, 4) + cost(4, {2}, 1) = 30 + 35 = 65 ] = 65
• cost(4, {2, 3}, 1) = min [ dist(4, 2) + cost(2, {3}, 1) = 25 + 50 = 75, dist(4, 3) + cost(3, {2}, 1) = 30 + 45 = 75 ] = 75

4) |ส| = 3:

• cost(1, {2, 3, 4}, 1) = min [ dist(1, 2) + cost(2, {3, 4}, 1) = 10 + 70 = 80, dist(1, 3) + cost(3, {2, 4}, 1) = 15 + 65 = 80, dist(1, 4) + cost(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 in S and i != 1
        Cost (i, S, j) = min {Cost (i, S - {i}, j) + dist(i, j) for j in S and i != j}
Return min(i) Cost (i, {1, 2, 3, ..., n}, j) + d(j, i)

การใช้งานใน C/C++

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

#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;
    do {
        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);
    } while (next_permutation(vertex.begin(), vertex.end()));

    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

การขอ Python การนำไปใช้งานสะท้อนให้เห็นถึง C++ เวอร์ชันนี้แก้ไขแหล่งที่มา from itertools, import พิมพ์ผิดเครื่องหมายจุลภาค การวางผิดที่ return ภายในวงใน และรอยบุ๋มที่ผิดปกติบน s = 0.

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
    for perm in permutations(vertex):
        current_cost = 0
        k = s
        for j in perm:
            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 Problem หรือ TSP) จนถึงปัจจุบัน TSP ยังคงเป็นปัญหา NP-hard อยู่

เทคนิคหลายอย่างที่ได้รับการเผยแพร่ช่วยลดความซับซ้อนในทางปฏิบัติสำหรับปัญหา TSP บางประเภท:

• ปัญหา TSP สมมาตรแบบคลาสสิกได้รับการแก้ไขโดย วิธีการต่อท้ายศูนย์.
• การขอ อัลกอริทึมการเพิ่มประสิทธิภาพตามชีวภูมิศาสตร์ ใช้กลยุทธ์การย้ายถิ่นฐานเพื่อแก้ปัญหาการเพิ่มประสิทธิภาพที่สอดคล้องกับปัญหา TSP
• การขอ อัลกอริทึมวิวัฒนาการแบบหลายเป้าหมาย ได้รับการออกแบบมาสำหรับ TSP ที่มีหลายวัตถุประสงค์ และสร้างขึ้นบนพื้นฐานของ NSGA-II
• การขอ ระบบมัลติเอเจนต์ วิธีการนี้แก้ปัญหา TSP สำหรับเมือง N เมือง โดยมีทรัพยากรการคำนวณที่จำกัด
• การขอ ฮิวริสติกของ Lin-Kernighan และผู้สืบทอด แอลเคเอช นำเสนอทัวร์โดยมีความคลาดเคลื่อนไม่เกิน 2-3% จากค่าที่เหมาะสมที่สุด สำหรับกรณีที่มีเมืองขนาดใหญ่ที่มีประชากรนับล้านคน
• คองคอร์ด ใช้ระนาบตัดและวิธีการแยกสาขาเพื่อคำนวณหาค่าที่เหมาะสมที่สุดสำหรับกรณีตัวอย่างมาตรฐานที่มีเมืองนับหมื่นเมือง

การประยุกต์ใช้ปัญหาพนักงานขายเดินทาง

ปัญหาพนักงานขายเดินทาง (Travelling Salesman Problem) ปรากฏให้เห็นในโลกแห่งความเป็นจริงทั้งในรูปแบบดั้งเดิมและรูปแบบที่ดัดแปลงแล้ว ตัวอย่างการประยุกต์ใช้หลักๆ ได้แก่:

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

การวิเคราะห์ความซับซ้อนของ TSP

• ความซับซ้อนของเวลา: วิธีการเขียนโปรแกรมเชิงพลวัตของ Held-Karp แก้ปัญหาได้ 2 ข้อ^N ชุดย่อยสำหรับแต่ละโหนดเริ่มต้น โดยให้ N × 2^N ปัญหาย่อยแต่ละปัญหาใช้เวลาในการรวมแบบเชิงเส้น หากไม่ได้ระบุโหนดต้นทาง จะต้องวนลูปภายนอกผ่านโหนด N โหนด ความซับซ้อนของเวลาทั้งหมดคือ O(N² × 2^N).
• ความซับซ้อนของอวกาศ: โต๊ะ DP จัดเก็บ C(S, i) สำหรับแต่ละเซตย่อย S ของเซตจุดยอด มี 2^N เซตย่อยต่อโหนด ดังนั้นความซับซ้อนของพื้นที่จึงเป็น O(N × 2^N)ซึ่งมักเขียนว่า O(2^N) เมื่อกำหนดให้ N เป็นค่าคงที่

ต่อไป มาเรียนรู้เกี่ยวกับ... อัลกอริทึมตะแกรงของ Eratosthenes.

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