algorithm
Путешественник

замечания

Алгоритм грубой силы

Путь через каждую вершину ровно один раз совпадает с порядком верстки вершины. Таким образом, чтобы вычислить минимальную стоимость прохода через каждую вершину ровно один раз, мы можем переборщить каждую единственную из N! перестановки чисел от 1 до 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

Сложность времени

Есть N! перестановки, и стоимость каждого пути вычисляется в O(N) , поэтому этот алгоритм принимает время O(N * N!) для вывода точного ответа.

Алгоритм динамического программирования

Обратите внимание, что если мы рассмотрим путь (по порядку):

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

и путь

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

Стоимость перехода от вершины 1 к вершине 2 к вершине 3 остается неизменной, так зачем ее пересчитывать? Этот результат можно сохранить для последующего использования.

Пусть dp[bitmask][vertex] представляет собой минимальную стоимость перемещения по всем вершинам, соответствующий бит в bitmask установлен в 1 заканчивающийся в vertex . Например:

dp[12][2] 

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

Так как 12 представляет 1100 в двоичном формате, dp[12][2] представляет перемещение по вершинам 2 и 3 в графе с концом, заканчивающимся в вершине 2.

Таким образом, мы можем иметь следующий алгоритм (реализация C ++):

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)

Эта строка может быть немного запутанной, поэтому давайте медленно ее протекаем:

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

Здесь bitmask | (1 << i) устанавливает i-й бит bitmask в 1, что означает, что i-я вершина была посещена. i после запятой представляет новый pos в вызове функции, который представляет новую «последнюю» вершину. cost[pos][i] заключается в добавлении стоимости перехода от вершины pos к вершине i .

Таким образом, эта строка заключается в обновлении стоимости cost до минимально возможного значения перемещения в любую другую вершину, которая еще не была посещена.

Сложность времени

Функция TSP(bitmask,pos) имеет значения 2^N для bitmask и значения N для pos . Каждая функция выполняет время O(N) для запуска (цикл for ). Таким образом, для реализации точного ответа эта реализация принимает время O(N^2 * 2^N) .