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

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

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

  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

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


path-finding graph-traversal
person jzx    schedule 21.02.2013    source источник
comment
Не могли бы вы рассказать больше о подмножестве полного графа, которое необходимо пройти? Будет ли указано подмножество узлов для каждого случая, например что-то вроде заданного полного графа узлов [a, b, c, d, e, f, g] с указанными весами ребер, найдите цикл минимальной стоимости через подмножество [a, b, d, f], которое может повторно посещать узлы? Если да, то чем это будет отличаться от задачи, если для полного графа узлов [a, b, d, f] найти цикл с минимальной стоимостью, который может повторно посещать узлы? В качестве альтернативы, может ли решение, которое находит цикл подмножества, включать посещающие узлы, которых нет в подмножестве?   -  person Simon    schedule 26.02.2013
comment
Да, необходимо учитывать узлы вне подмножества, даже если промежуточные узлы не являются необходимыми для цикла. Вот почему: Учтите, что ребра между каждым узлом в подмножестве могут быть более дорогими, чем короткие ребра на узле за пределами подмножества. Итак, если у меня есть набор [a,b,c], и мне нужно двигаться только от a к b, если ребро из a->b имеет вес 10, a->c имеет вес 2, а c->b имеет вес 2, то очевидно, что любой алгоритм должен учитывать c, поскольку он является частью лучшего пути. Для данного графа может быть несколько лучших путей с одинаковой стоимостью.   -  person jzx    schedule 26.02.2013

Ответы (1)


arrow_upward
3
arrow_downward

Циклы, начинающиеся и заканчивающиеся на 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.
person user568109    schedule 02.03.2013
comment
О, отлично, я думаю, что теперь смогу с этим взяться! Очень полезно, спасибо! - person jzx; 04.03.2013