Существует ли алгоритм вычисления перестановки расстояний?

Это связано с проблемой коммивояжера. Сначала необходимо сгенерировать все перестановки, а затем прикрепить пункт назначения (такой же, как источник). То есть: 1) abcd abdc ....

2) абвда абдца ....а

У меня есть все расстояния, и мне нужен только алгоритм, чтобы суммировать их. Интересно, есть ли алгоритм (предпочтительнее C), который я могу использовать для этого, или где-то есть готовое решение.


algorithm permutation traveling-salesman hamiltonian-cycle
person nnn    schedule 21.10.2010    source источник
comment
Итак, учитывая abcde, вы хотите просуммировать расстояния ab, bc, cd, de?   -  person JoshD    schedule 22.10.2010
comment
Вам тоже нужно получить перестановки?   -  person JoshD    schedule 22.10.2010
comment
У меня есть список перестановок, например abcda   -  person nnn    schedule 22.10.2010

Ответы (1)


arrow_upward
2
arrow_downward

Это как-то тривиально.

int sum = 0;
for (i = 0; i < length-1; i++)
{
  sum += distance[group[i]][group[i+1]];
}

Где distance - это двумерный массив (матрица, если хотите), который содержит расстояние между двумя узлами. группа должна быть массивом или вектором или узлами в порядке перемещения.

Если вам также нужно получить каждую перестановку, используйте next_permutation.

Вот краткий пример того, каким может быть расстояние:

int distance[4][4] = {
 {0,2,1,0},
 {2,0,1,2},
 {1,1,0,1},
 {0,2,1,0},
};

Обратите внимание, что это будет симметричная матрица для вашей задачи.

person JoshD    schedule 21.10.2010
comment
Это должно быть длиной списка узлов. Он всегда должен быть одинаковым для вашей ситуации (5 для примера, который вы привели). - person JoshD; 22.10.2010
comment
Я работаю над оператором переключения для функции расстояния, и я не хочу вводить одинаковые расстояния с перевернутыми местами источника и назначения. Есть ли что-то еще, что я могу сделать? - person nnn; 22.10.2010
comment
Не используйте оператор switch. Поместите расстояния в матрицу (тип vector‹vector‹int› ›). Тогда вы можете просто return distances[i][i+1]. Нижние индексы должны быть значениями узла. Итак, для узлов a и b вы можете сделать distances[0][1]. Кроме того, вы можете сначала расположить два параметра в порядке возрастания, поэтому, учитывая b, a, вы переключите их на a, b. - person JoshD; 22.10.2010