оптимизация решения Brute-force TSP

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

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

Проблема, с которой я сталкиваюсь, заключается в том, что текущая реализация улучшает решение, но не делает его оптимальным (я сравнил результаты с простым перебором). Я был бы признателен, если бы вы указали на мои логические недостатки или/и ошибки. M - матрица затрат. help - текущее решение, best - лучшее решение (переменные класса)

   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]);
             }
         }
     }

c++ optimization np traveling-salesman
person Greenmachine    schedule 02.01.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Насколько я понимаю, ваша ошибка заключается в вычислении 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, то эта ветвь рекурсии не найдет оптимального решения наверняка.

person Mike Koltsov    schedule 15.01.2016
comment
Привет Майк. Да, это была проблема. Я понял это и не опубликовал свой ответ, как только проблема была решена. Но спасибо за ваше время и желание помочь. - person Greenmachine; 16.01.2016