Есть ли алгоритм для вычисления перестановки расстояний?

Question

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

2) abcda abdca .... a

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

Answer 1

Это довольно тривиально.

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},
};

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