algorithm
Handelsreiziger

Opmerkingen

Brute Force-algoritme

Een pad door elk hoekpunt precies één keer is hetzelfde als het op een bepaalde manier bestellen van het hoekpunt. Dus, om de minimale kosten van reizen door elk hoekpunt precies één keer te berekenen, kunnen we elke N! van de N! bruut forceren N! permutaties van de getallen van 1 tot N

psuedocode

minimum = INF
for all permutations P

    current = 0                                

    for i from 0 to N-2
        current = current + cost[P[i]][P[i+1]]  <- Add the cost of going from 1 vertex to the next
    
    current = current + cost[P[N-1]][P[0]]      <- Add the cost of going from last vertex to the first

    if current < minimum                        <- Update minimum if necessary
        minimum = current
    
output minimum

Tijd Complexiteit

Er zijn N! permutaties doorlopen en de kosten van elk pad worden berekend in O(N) , dus dit algoritme heeft O(N * N!) tijd nodig om het exacte antwoord uit te voeren.

Dynamisch programmeeralgoritme

Merk op dat als we het pad (in volgorde) beschouwen:

(1,2,3,4,6,0,5,7)

en het pad

(1,2,3,5,0,6,7,4) 

De kosten om van hoekpunt 1 naar hoekpunt 2 naar hoekpunt 3 blijven hetzelfde, dus waarom moet het opnieuw worden berekend? Dit resultaat kan worden opgeslagen voor later gebruik.

Laat dp[bitmask][vertex] de minimale kosten vertegenwoordigen van het reizen door alle hoekpunten waarvan het overeenkomstige bit in bitmask is ingesteld op 1 eindigend op vertex . Bijvoorbeeld:

dp[12][2] 

   12   =   1 1 0 0
            ^ ^ 
vertices:   3 2 1 0

Aangezien 12 in binair dp[12][2] 1100 vertegenwoordigt, geeft dp[12][2] dat het door de hoekpunten 2 en 3 in de grafiek gaat met het pad dat eindigt op hoekpunt 2.

We kunnen dus het volgende algoritme hebben (C ++ implementatie):

int cost[N][N];                        //Adjust the value of N if needed
int memo[1 << N][N];                   //Set everything here to -1
int TSP(int bitmask, int pos){
    int cost = INF;
    if (bitmask == ((1 << N) - 1)){      //All vertices have been explored
        return cost[pos][0];             //Cost to go back
    }
    if (memo[bitmask][pos] != -1){       //If this has already been computed
        return memo[bitmask][pos];       //Just return the value, no need to recompute
    }
    for (int i = 0; i < N; ++i){         //For every vertex 
        if ((bitmask & (1 << i)) == 0){  //If the vertex has not been visited
            cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);   //Visit the vertex
        } 
    }
    memo[bitmask][pos] = cost;           //Save the result
    return cost;
}
//Call TSP(1,0)

Deze lijn kan een beetje verwarrend zijn, dus laten we hem langzaam doornemen:

cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);

Hier, bitmask | (1 << i) stelt het ie bitmask op 1, wat betekent dat het iepunt is bezocht. De i na de komma vertegenwoordigt de nieuwe pos in die functieaanroep, die het nieuwe "laatste" hoekpunt vertegenwoordigt. cost[pos][i] is om de kosten van de reis van het punt toe te voegen pos aan hoekpunt i .

Deze regel is dus om de waarde van de cost bij te werken tot de minimaal mogelijke waarde van reizen naar elke andere top die nog niet is bezocht.

Tijd Complexiteit

De functie TSP(bitmask,pos) heeft 2^N waarden voor bitmask en N waarden voor pos . Elke functie heeft O(N) tijd nodig om te werken (de for lus). Dus deze implementatie heeft O(N^2 * 2^N) tijd nodig om het exacte antwoord uit te voeren.