Оптимизация решения для грубой силы TSP

Question

Оптимизация решения для грубой силы TSP

Я работаю над небольшим проектом для решения TSP, но у меня возникла проблема. Идея состоит в том, чтобы оптимизировать локальную часть неоптимального пути, просто найдя наилучшую комбинацию. Это достигается с помощью простой функции генерации рекурсивной перестановки.

Теперь я хочу проверить, есть ли у текущего решения какой-либо потенциал для улучшения (логика: не вызывать функцию перестановки, если вес решения больше, чем текущий лучший)

У меня проблема в том, что текущая реализация улучшает решение, но не делает его оптимальным (я сравнил результаты с простым перебором). Буду признателен, если вы укажете на мои логические недостатки или ошибки.
М — это стоимость матрицы. помощь — текущее решение, лучшее — лучшее решение (переменные класса)

   void City::Generate(int** M, int* help, int k, int &auxcost, int* best) {
int cost2 = 0; // текущая цена
if (k == range){
for (int i = 0; i < range - 1; i++)
cost2 += M[help[i]][help[i + 1]];

if (cost2 < auxcost ){
auxcost = cost2;
memcpy(best, help,range *sizeof(int));
changed = true;
}
}
else{
for (int j2 = k; j2<range; j2++){
swap(help[k], help[j2]);

for (int i = 0; i < range - 1; i++)
tcost += M[help[i]][help[i + 1]];if (tcost <= auxcost)
Generate(M, help, k + 1, start, end, auxcost, best);
swap(help[k], help[j2]);
}
}
}

0

c++np optimization traveling-salesman

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Насколько я понимаю, ваша ошибка в вычислительной tcost вырезать рекурсию.
Вы назначили место для каждого города help[0]..help[k], Тем не менее, вы вычисляете tcost

for (int i = 0; i < range - 1; i++)
tcost += M[help[i]][help[i + 1]];

для полной перестановки, как вы уже исправили все города! В действительности, ваша рекурсивная функция может улучшить расположение help[k+1]..help[range-1] часть текущей перестановки, обеспечивая тем самым более оптимальный ответ, чем auxcost,

Вместо этого вы должны оценить только часть перестановки, которой вы являетесь не планирую изменить. Значения help[0], help[1], ..., help[k] не изменится, если вы продолжите рекурсию. Таким образом, если значение x, рассчитывается таким образом:

int x = 0;
for (int i = 0; i < k; i++)  // notice the difference in exit condition
x += M[help[i]][help[i + 1]];

больше, чем auxcostто эта ветвь рекурсии не найдет оптимального решения наверняка.

1