Кратчайший путь при обходе x уникальных узлов

У меня есть график, где все мои узлы имеют расчетное расстояние друг от друга.

Теперь я хочу начать с моего startNode, а затем найти путь с наименьшим вычисленным значением, если путь имеет X уникальных узлов. Думайте об этом как о карте: мы начинаем в Париже и хотим посетить 3 города. Я хочу найти путь с 3 полными остановками от Парижа с наименьшим расчетным значением.

Я думаю о реализации модифицированного алгоритма Дейкстры, который обычно дает мне кратчайшее расстояние до конечного пункта назначения, а затем моими конечными пунктами назначения являются все пункты назначения X_level_out, что должно дать мне время выполнения чего-то вроде O(nodes^level) .

Есть ли в этом смысл? Есть ли другие предложения?


c# algorithm data-structures dijkstra graph-theory
person Lars Holdgaard    schedule 09.05.2013    source источник
comment
Нечего сказать, кроме того, что модифицированный Дейкстры должен работать нормально.   -  person Bernhard Barker    schedule 09.05.2013
comment
Похоже, простая вариация BFS должна подойти.   -  person Eran    schedule 09.05.2013
comment
У меня есть график, где все мои узлы имеют расчетное расстояние друг от друга. - Означает ли это, что ваш граф завершен (ребро между всеми парами узлов)?   -  person mbeckish    schedule 09.05.2013
comment
Эран: Как бы вы сделали это с BFS? Мбекиш: А нет, извините. Это не завершено.   -  person Lars Holdgaard    schedule 09.05.2013
comment
Посмотрите на алгоритм Флойда-Уоршалла   -  person isaach1000    schedule 09.05.2013
comment
@LarsHoldgaard Вы можете использовать BFS, чтобы найти все узлы, которые находятся на уровне X. При обходе ребер просто соблюдайте минимальные расстояния, как в алгоритме Дейкстры. (Сама Дейкстра является обобщением BFS, но здесь вам не нужно использовать полную Дейкстру, поскольку длина пути или уровень фиксированы).   -  person Eran    schedule 12.05.2013

Ответы (1)


arrow_upward
1
arrow_downward

Для заданного взвешенного неориентированного графа G(V,E) и множества S, подмножества V, найдите дерево минимальной стоимости, которое охватывает узлы в S. Эта проблема известна в литературе как проблема дерева Штейнера. Задача является NP-полной, что означает, что не существует известного полиномиального алгоритма, который найдет точное решение задачи. Однако существуют алгоритмы, решающие задачу Штейнера за экспоненциальное время (O(2^N) или O(2^M)).

Алгоритм наивного или кратчайшего пути.

Find the Shortest path tree from one participant node to the rest of the graph. 
Prune the parts of the tree that do not lead to a participant.

Сложность O(N^2), CR = O(M).

Алгоритм «Жадный или ближайший участник — первый». (Такахаши, Мацуяма, 1980) Начните с участника.

Find the participant that is closest to the current tree. 
Join the closest participant to the closest part of the tree. 
Repeat until you have connected all nodes.

Сложность O(M N^2), CR = O(1), на самом деле CR ‹= 2.

Алгоритм Коу, Марковского и Бермана (KMB 1981).

1. Find the complete distance graph G' 
  (G' has V' = S , and  for each  pair of nodes (u,v) in VxV there is an edge with weight equal to the weight of the min-cost path between these nodes p_(u,v)  in G) 
2. Find a minimum spanning tree  T' in G' 
3. Translate tree T' to the  graph G: substitute every edge of T', which is an edge  of G' with the corresponding path of G. Let us call T the result of the translation. 
4. Remove any possible cycles from T.

Сложность O(M N^2), CR = O(1), на самом деле CR ‹= 2.

person Aditya    schedule 18.05.2013