Минимальный цикл затрат на полном графике

Question

У меня есть полный граф с ненаправленными взвешенными ребрами, и мне нужно найти цикл с наименьшей стоимостью через подмножество узлов графа. В отличие от Traveling Salesman, любой узел может быть посещен более одного раза, и не все узлы должны посещаться, и под стоимостью я подразумеваю, что путь должен иметь наименьшую сумму весов пройденных ребер.

Например, вот граф в виде матрицы смежности:

  a b c d
a 0 3 4 5
b 3 0 2 4
c 4 2 0 1
d 5 4 1 0

где вес каждого ребра используется для каждого элемента. Циклы начинаются и заканчиваются в a и в том числе [b,d] будет выглядеть

[a,b,d,a] -> 3+4+5 = 12
[a,b,d,b,a] -> 3+4+4+3 = 14
[a,b,c,d,c,a] -> 3+2+1+1+4 = 11

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

Answer 1

Циклы начинаются и заканчиваются в a и в том числе [b,d] просто означает, что цикл должен посещать узлы a, b, d. [a,b,d,a] = [b,d,a,b] (циклы справа). Ваша проблема называется k-TSP. Смотрите здесь. Но это очень сложно реализовать и может не соответствовать тому, что вы ищете.

Так что я просто дам вам более простой способ. Сначала создайте кратчайший цикл, который проходит только через эти узлы. Затем замените каждое ребро наименьшим путем между двумя узлами. Я думаю, что это разумно, я опускаю оптимальность. Вот шаги:

• V = узлы E= ребра и M= обязательные для посещения узлы.
• Создать цикл C запустив TSP на M (без использования других узлов), добавив дополнительный край, чтобы сделать цикл.
• Теперь используем все узлы V. Для каждого ребра uv в C, делать:
• Найти кратчайший путь w между u а также v используя алгоритм Дийсктра (в графе не должно быть отрицательного цикла).
• замещать uv с w,