Оптимальный путь к графу, содержащий n узлов

Question

Существует ли установленный алгоритм для нахождения пути от точки A к точке B в ориентированном взвешенном графе, который посещает ровно N узлов, но не обязательно какие-либо узлы в частности?

Answer 1

Эта проблема, как известно, является NP-трудной благодаря уменьшению с гамильтонова пути .В частности, вы можете решить гамильтонову траекторию с уменьшением полиномиального времени до этой задачи следующим образом: для каждой возможной пары узлов (s, t) в графе с n узлами спросите, существует ли путь из s в t, который проходитчерез ровно n узлов.Это делает только полиномиальные вызовы вашего решателя, поэтому любое решение вашей задачи за полиномиальное время приведет к решению задачи с гамильтоновым путем за полиномиальное время.

Короче говоря, вы не должны ожидатьалгоритм времени для этой задачи, если P = NP.

Answer 2

Я не уверен, правильно ли я понял, можете ли вы выполнить поиск в глубину (до N-1 слоев от источника)?

Если вы сможете посетить пункт назначения в этом слое.Вы можете проложить там путь.

Answer 3

Я предполагаю, что вы пытаетесь найти самый короткий / самый длинный вес с N узлами.Это, вероятно, не оптимально, но из вашего исходного графа вы можете сгенерировать граф состояний с узлами 'N * (# Nodes)', представляющими собой исходный узел и количество предпринятых шагов, и выполнить его с помощью алгоритма кратчайшего пути, например http://en.wikipedia.org/wiki/Dijkstra's_algorithm.

т.е.

A->B->C
 \___/

становится

(A,0)->(B,1)->(C,2)
  \>(C,1)

Тогда вашим целевым узлом будет узел (B, N) - B с N шагами.Этот подход учитывает циклы в исходном графе, если это не DAG ((X, 0) -> (Y, 1) -> (X, 2))