кратчайший путь из нескольких наборов

Мне нужно найти кратчайший путь между узлами в различных наборах, где я могу использовать узел только один раз из каждого набора. Каждый узел связан через расстояние со всеми остальными узлами. Существует исключение, когда узлы в наборе не связаны между собой. Путь должен содержать по одному узлу из каждого множества.

eg. 

    Set A - [a1, a2, a3]
    Set B - [b1, b2]
    Set C - [c1]
    Set D - [d1, d2, d3]
    Set Z - [z1, z2, z3]

Узлы a1,a2,a3,b1,b2...

например. Узел a1 имеет соединение с

b1,b2,c1,d1,d2,d3,z1,z2,z3

или узел c1 имеет связь с

a1,a2,a3,b1,b2,d1,d2,d3,z1,z2,z3

Возможный путь может быть:

a1 -> b1 -> c1 -> d1 -> z1, or c1 -> z2 -> a3 -> b1 -> d2

Расстояние между всеми узлами (кроме узлов в наборе, соединения нет) может быть от 0 до 1.


algorithm shortest-path dijkstra
person Matej    schedule 22.04.2013    source источник
comment
Вы отметились Дейкстрой, так что у вас уже есть идея? Что вы уже закодировали?   -  person Roger Rowland    schedule 22.04.2013
comment
Похоже на задачу коммивояжера.   -  person nhahtdh    schedule 22.04.2013
comment
должно быть не менее сложно, чем tsp, если только количество наборов не ограничено функцией с максимальным логарифмическим числом узлов n. представьте, что некий оракул сообщает вам заранее, какой узел выбрать из каждого набора. для каждого набора отбросить все остальные узлы. ваша проблема стала экземпляром tsp. NB: если ваша исходная проблема допускает несколько посещений одного и того же набора, это не будет отражено в указанной задаче tsp, хотя это еще больше усложнит ваш поиск.   -  person collapsar    schedule 22.04.2013

Ответы (1)


arrow_upward
1
arrow_downward

Это известно как обобщенная задача коммивояжера.

Из C. Нун и Дж. Бин, Эффективная трансформация обобщенной задачи коммивояжёра:

Обобщенная задача коммивояжёра (GTSP) — это полезная модель для задач, включающих решения о выборе и последовательности. Асимметричный вариант задачи определяется на ориентированном графе с узлами N, соединяющими дуги A, и вектором соответствующих стоимостей дуг c. Узлы предварительно сгруппированы в m взаимоисключающих и исчерпывающих наборов узлов. Соединительные дуги определяются только между узлами, принадлежащими разным множествам, то есть внутримножественных дуг нет. Каждая определенная дуга имеет соответствующую неотрицательную стоимость. GTSP можно сформулировать как задачу нахождения цикла m-дуги с минимальной стоимостью, который включает ровно один узел из каждого набора узлов.

В этой статье объясняется, как преобразовать вашу задачу в случай стандартной задачи коммивояжёра.

person Peter de Rivaz    schedule 22.04.2013