Utazó értékesítő probléma: Python, C++ Algoritmus

By: Sarah Chen Sarah Chen
Hours korszerűsített

Mi az utazó értékesítő probléma (TSP)?

A Traveling Salesman Problem (TSP) az elméleti számítástechnika klasszikus kombinatorikai problémája. A feladat a legrövidebb utat keresi egy gráfban azzal a feltétellel, hogy az összes csomópontot csak egyszer kell meglátogatni, és visszatérni a kiindulási városba.

A problémafelvetés megadja a városok listáját az egyes városok közötti távolságokkal együtt.

Célkitűzés: A kiindulási városból való induláshoz csak egyszer látogassa meg a többi várost, és térjen vissza újra az eredeti városba. Célunk, hogy megtaláljuk a lehető legrövidebb utat az oda-vissza út teljesítéséhez.

Példa a TSP-re

Itt egy grafikont adunk meg, ahol 1, 2, 3 és 4 a városokat jelöli, a minden élhez tartozó súly pedig a városok közötti távolságot jelenti.

Példa a TSP-re

A cél az, hogy megtaláljuk a túra lehető legrövidebb útvonalát, amely a kiindulási városból indul, bejárja a grafikont, miközben a többi várost vagy csomópontot csak egyszer keresi fel, és visszatér a kiindulási városba.

A fenti grafikonon az optimális útvonal a minimális költségút követése: 1-2-4-3-1. Ez a legrövidebb út pedig 10+25+30+15 =80-ba kerülne

Különböző megoldások utazó értékesítői problémára

Különböző megoldások utazó értékesítői problémára

A Traveling Salesman Problem (TSP) NP-nehéz problémaként van besorolva, mivel nincs benne polinomiális idő algoritmus. A komplexitás exponenciálisan nő a városok számának növekedésével.

Számos módja van az utazó eladó problémájának (tsp) megoldásának. Néhány népszerű megoldás:

A brute force megközelítés a naiv módszer utazó eladói problémák megoldására. Ebben a megközelítésben először kiszámítjuk az összes lehetséges utat, majd összehasonlítjuk őket. Egy n városból álló gráfban az utak száma a n! Számításilag nagyon költséges az utazó eladó problémájának megoldása ebben a brute force megközelítésben.

Az elágazásos módszer: A probléma ebben a megközelítésben részproblémákra oszlik. Az egyes részproblémák megoldása optimális megoldást jelentene.

Ez az oktatóanyag bemutatja a dinamikus programozási megközelítést, ennek az elágazó és kötött módszernek a rekurzív változatát az utazó értékesítő problémájának megoldására.

Dinamikus programozás egy ilyen módszer az optimális megoldások keresésére az összes lehetséges útvonal elemzésével. Ez az egyik olyan pontos megoldási mód, amely viszonylag magasabb költséggel oldja meg az utazó eladók problémáit, mint a mohó módszerek amelyek közel optimális megoldást nyújtanak.

Ennek a megközelítésnek a számítási összetettsége az O(N^2*2^N) amelyről ebben a cikkben később lesz szó.

A legközelebbi szomszéd módszere egy heurisztikus alapú mohó megközelítés, ahol a legközelebbi szomszéd csomópontot választjuk. Ez a megközelítés számítási szempontból olcsóbb, mint a dinamikus megközelítés. De ez nem ad garanciát az optimális megoldásra. Ezt a módszert közel optimális megoldásokhoz használják.

Algoritmus utazó értékesítő problémához

A dinamikus programozási megközelítést fogjuk használni az utazó értékesítő probléma (TSP) megoldására.

Az algoritmus megkezdése előtt ismerkedjünk meg néhány terminológiával:

  • Egy gráf G=(V, E), amely csúcsok és élek halmaza.
  • V a csúcsok halmaza.
  • E az élek halmaza.
  • A csúcsok éleken keresztül kapcsolódnak össze.
  • A Dist(i,j) két csúcs, az i és a j közötti nem negatív távolságot jelöli.

Tegyük fel, hogy S a városok részhalmaza, és a következőhöz tartozik: {1, 2, 3, …, n}, ahol 1, 2, 3…n a városok és i, j két város ebben a részhalmazban. Most a költség(i, S, j) úgy van definiálva, mint az S-beli legrövidebb út látogató csomópontjának hossza, amelynek pontosan egyszer van a kezdő- és végpontja i, illetve j.

Például a költség (1, {2, 3, 4}, 1) a legrövidebb út hosszát jelöli, ahol:

  • A kezdő város az 1
  • A 2., 3. és 4. várost csak egyszer látogatják meg
  • A végpont az 1

A dinamikus programozási algoritmus a következő lenne:

  • Állítsa be a költség(i, , i) = 0 értéket, ami azt jelenti, hogy i-vel kezdjük és fejezzük be, a költség pedig 0.
  • Amikor |S| > 1, akkor definiáljuk a költség(i, S, 1) = ∝ ahol i !=1 . Mert kezdetben nem tudjuk, hogy pontosan mekkora költséggel lehet eljutni az i-es városba az 1-es városba más városokon keresztül.
  • Most 1-kor kell kezdenünk és be kell fejeznünk a körutat. A következő várost úgy kell kiválasztanunk, hogy

költség(i, S, j)=min költség (i, S−{i}, j)+dist(i,j) ahol i∈S és i≠j

Az adott ábra szomszédsági mátrixa a következő lenne:

Algoritmus utazó értékesítő problémához

dist(i,j) 1 2 3 4
1 0 10 15 20
2 10 0 35 25
3 15 35 0 30
4 20 25 30 0

Lássuk, hogyan működik az algoritmusunk:

Step 1) Azt fontolgatjuk, hogy az 1-es városból indulunk, egyszer felkeresünk más városokat, és visszatérünk az 1-es városba.

Step 2) S a városok részhalmaza. Algoritmusunk szerint minden |S|-re > 1, akkor beállítjuk a távolság költségét(i, S, 1) = ∝. Itt a cost(i, S, j) azt jelenti, hogy i városból indulunk, egyszer meglátogatjuk S városait, most pedig j városnál vagyunk. Ezt az útköltséget végtelennek állítottuk be, mert még nem ismerjük a távolságot. Tehát az értékek a következők lesznek:

Költség (2, {3, 4}, 1) = ∝ ; a jelölés azt jelenti, hogy a 2. várostól indulunk, átmegyünk a 3., 4. városon, és elérjük az 1-et. Az út költsége pedig végtelen. Hasonlóképpen-

költség(3, {2, 4}, 1) = ∝

költség(4, {2, 3}, 1) = ∝

Step 3) Most az S összes részhalmazához meg kell találnunk a következőket:

költség(i, S, j)=min költség (i, S−{i}, j)+dist(i,j), ahol j∈S és i≠j

Ez azt jelenti, hogy az i-nél kezdődő, a városok részhalmazának egyszeri végighaladása és a j városba való visszatérés minimális költségútja. Figyelembe véve, hogy az utazás az 1. városban kezdődik, az optimális útköltség a következő lenne: költség(1, {egyéb városok}, 1).

KAPCSOLÓDÓ CIKKEK

Nézzük meg, hogyan érhetjük el ezt:

Most S = {1, 2, 3, 4}. Négy elem van. Ezért a részhalmazok száma 2^4 vagy 16 lesz. Ezek a részhalmazok

1) |S| = Null:

{Φ}

2) |S| = 1:

{{1}, {2}, {3}, {4}}

3) |S| = 2:

{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}

4) |S| = 3:

{{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}

5) |S| = 4:

{{1, 2, 3, 4}}

Mivel 1-től kezdjük, eldobhatjuk az 1-es várost tartalmazó részhalmazokat.

Az algoritmus számítása:

1) |S| = Φ:

költség (2, Φ, 1) = dist(2, 1) = 10

költség (3, Φ, 1) = dist(3, 1) = 15

költség (4, Φ, 1) = dist(4, 1) = 20

2) |S| = 1:

költség (2, {3}, 1) = diszt(2, 3) + költség (3, Φ, 1) = 35+15 = 50

költség (2, {4}, 1) = diszt(2, 4) + költség (4, Φ, 1) = 25+20 = 45

költség (3, {2}, 1) = diszt(3, 2) + költség (2, Φ, 1) = 35+10 = 45

költség (3, {4}, 1) = diszt(3, 4) + költség (4, Φ, 1) = 30+20 = 50

költség (4, {2}, 1) = diszt(4, 2) + költség (2, Φ, 1) = 25+10 = 35

költség (4, {3}, 1) = diszt(4, 3) + költség (3, Φ, 1) = 30+15 = 45

3) |S| = 2:

költség (2, {3, 4}, 1) = min [ diszt[2,3]+Költség(3,{4},1) = 35+50 = 85,

diszt[2,4]+Költség(4,{3},1) = 25+45 = 70 ] = 70

költség (3, {2, 4}, 1) = min [ diszt[3,2]+Költség(2,{4},1) = 35+45 = 80,

diszt[3,4]+Költség(4,{2},1) = 30+35 = 65 ] = 65

költség (4, {2, 3}, 1) = min [ disz[4,2]+Költség(2,{3},1) = 25+50 = 75

diszt[4,3]+Költség(3,{2},1) = 30+45 = 75 ] = 75

4) |S| = 3:

költség (1, {2, 3, 4}, 1) = min [ disz[1,2]+Költség(2,{3,4},1) = 10+70 = 80

diszt[1,3]+Költség(3,{2,4},1) = 15+65 = 80

diszt[1,4]+Költség(4,{2,3},1) = 20+75 = 95 ] = 80

Tehát az lenne az optimális megoldás 1-2-4-3-1

Algoritmus utazó értékesítő problémához

Pszeudo-kód

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)

Megvalósítás C/C++

Itt van a megvalósítás 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

Végrehajtás 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

Akadémiai megoldások a TSP-hez

Számítógépes tudósok éveket töltöttek azzal, hogy egy továbbfejlesztett polinomiális idő algoritmust keressenek a Traveling Salesman Probléma megoldására. Eddig még mindig NP-nehéz a probléma.

Bár a következő megoldások közül néhányat az elmúlt években tettek közzé, amelyek bizonyos fokig csökkentették a bonyolultságot:

  • A klasszikus szimmetrikus TSP-t a Zero Suffix módszerrel oldják meg.
  • A Biogeography-alapú optimalizálási algoritmus a migrációs stratégián alapul, hogy megoldja a TSP-ként tervezhető optimalizálási problémákat.
  • A Multi-Objective Evolutionary Algorithm az NSGA-II-n alapuló több TSP megoldására készült.
  • A Multi-Agent System N város TSP-jét oldja meg rögzített erőforrásokkal.

Utazó kereskedő probléma alkalmazása

A Traveling Salesman Problem (TSP) a valós világban a legtisztább és módosított formában is alkalmazható. Néhány ezek közül:

  • Tervezés, logisztika és mikrochipek gyártása: A chip behelyezési problémák természetesen felmerülnek a mikrochip iparban. Ezek a problémák tervezhetők utazó eladói problémáknak.
  • DNS szekvenálás: Az utazó eladó problémájának enyhe módosítása felhasználható a DNS-szekvenálás során. Itt a városok a DNS-fragmenseket, a távolság pedig a két DNS-fragmens közötti hasonlóság mértékét jelenti.
  • Csillagászat: Az utazó kereskedő problémát a csillagászok alkalmazzák, hogy minimalizálják a különféle források megfigyelésével töltött időt.
  • Optimális szabályozási probléma: Travelling Salesman A probléma megfogalmazása optimális szabályozási problémák esetén alkalmazható. Lehetséges, hogy számos egyéb korlátozás is hozzáadásra kerül.

A TSP komplexitáselemzése

  • Idő összetettsége: Összesen 2 vanN részproblémák minden csomóponthoz. Tehát a részfeladatok teljes száma N*2 lenneN. Mindegyik részprobléma megoldásához lineáris időre van szükség. Ha az eredet csomópont nincs megadva, akkor N csomóponthoz hurkot kell futtatnunk.

    Tehát az optimális megoldás teljes időbonyolultsága a csomópontok száma * részproblémák száma * az egyes részproblémák megoldásához szükséges idő. Az időbonyolultság O(N2 * 2^N).

  • Tér összetettsége: A dinamikus programozási megközelítés a memóriát használja a C(S, i) tárolására, ahol S a csúcskészlet egy részhalmaza. Összesen 2 db vanN részhalmazokat minden csomóponthoz. Tehát a tér komplexitása O(2^N).

Ezután megtudhatja Eratosthenes algoritmus szitája