algorithm
Путешественник
Поиск…
замечания
Задача Traveling Salesman - проблема нахождения минимальной стоимости перемещения по N
вершинам ровно один раз на вершину. Существует стоимость cost[i][j]
для перехода от вершины i
к вершине j
.
Для решения этой проблемы существует два типа алгоритмов: точные алгоритмы и алгоритмы аппроксимации
Точные алгоритмы
- Алгоритм грубой силы
- Алгоритм динамического программирования
Аппроксимационные алгоритмы
Быть добавленным
Алгоритм грубой силы
Путь через каждую вершину ровно один раз совпадает с порядком верстки вершины. Таким образом, чтобы вычислить минимальную стоимость прохода через каждую вершину ровно один раз, мы можем переборщить каждую единственную из 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)
.