Как найти путь точной длины на графике

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

Узлы нельзя посещать снова.

Итак, предположим, что у моего графа 9 узлов, а кратчайший путь построен из 4 узлов.
Я хочу иметь дополнительную переменную, которая «сообщит» алгоритму, что я хочу найти путь, который имеет 7 узлов (например) и он вернет узлы, которые включены в мой ожидаемый путь {1,2,4,5,6,7,8}.
Конечно, если нет решения для пути, который я хочу, он ничего не вернет (или он вернет путь, близкий к моим вычислениям, скажем, 19 вместо 20).

Кто-то сказал про DFS с возвратом, но я ничего об этом не знаю.
Может ли кто-нибудь объяснить, как использовать DFS с возвратом, или порекомендовать другие алгоритмы для решения этой проблемы?


algorithm path-finding graph-algorithm
person Dominik T.    schedule 04.06.2012    source источник
comment
путь, который близок к моим ожиданиям - это расплывчато.   -  person goat    schedule 04.06.2012

Ответы (5)


arrow_upward
6
arrow_downward

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

Псевдокод:

DFS(depth,v,path):
  if (depth == 0 && v is target): //stop clause for successful branch
       print path
       return
  if (depth == 0): //stop clause for non successful branch
       return
  for each vertex u such that (v,u) is an edge:
       path.append(v) //add the current vertex to the path
       DFS(depth-1,u,path) //recursively check all paths for of shorter depth
       path.removeLast() // clean up environment

Вышеупомянутый алгоритм сгенерирует все пути необходимой глубины. Вызов
с DFS(depth,source,[]) (где [] - пустой список).

Примечание:

  • Алгоритм сгенерирует пути, которые могут быть непростыми. Если вам нужны только простые пути - вам также необходимо поддерживать visited set и добавлять каждую вершину, когда вы добавляете ее к найденному пути, и удалять ее, когда вы удаляете ее из пути.
  • Если вы хотите найти только один такой путь - вы должны вернуть значение из функции (истина, если такой путь был найден) и разорвать цикл (и вернуть истину), когда возвращаемое значение истинно.
person amit    schedule 04.06.2012
comment
Я пытался сделать ваш псевдокод на Java, но что-то не так, и я не знаю что: pastebin.com/60u3FYmf Где adj [] [] - моя матрица смежности графа, а путь хранится в стеке. - person Dominik T.; 05.06.2012
comment
Ну, не могу быть уверенным, но с первого взгляда: (1) Почему вы выполняете итерацию от 1 до numVertex включительно, а не от 0 до numVertex-1 включительно? массивы в java основаны на 0. (2) Кажется, вы пропустили visited.pop() после рекурсивного вызова, поэтому набор visited заполняется, но элементы никогда не удаляются после того, как вы исчерпали определенный путь. (3) Должен быть еще один пункт остановки (который я также пропустил в псевдокоде, скоро отредактирую) для depth == 0 && v is not target, который должен завершить эту ветвь. - person amit; 05.06.2012
comment
У меня есть такой график (сейчас я его тестирую): i.imgur.com/SWu09.jpg .. и когда я даю глубину 8 и начинаю 1 конец 9 (1,9), DFS ничего не показывает. Он должен писать [1,2,3,6,5,4,7,8,9] или [1,4,7,8,5,2,3,6,9]. Когда я даю глубину 3 и начинаю 1 конец 2 (1,2), он правильно пишет [1,4,5,2], но когда я меняю глубину на 5 - ничего. Он должен дать как минимум [1,4,7,8,5,2]. Я не знаю, что здесь не так: pastebin.com/CQpwfkg1 - person Dominik T.; 05.06.2012

arrow_upward
2
arrow_downward

Проблема, как указано, является NP-полной. Вы можете легко решить проблему гамильтонова цикла, имея эффективный алгоритм решения вашей проблемы.

Следовательно, не существует решения с полиномиальным временем (если только P = NP). Чтобы получить исчерпывающий поиск, решение с экспоненциальным временем, проверьте ответ @amit.

person maniek    schedule 04.06.2012

arrow_upward
1
arrow_downward

Одного dfs должно хватить:

void dfs(int start, int hops)
{
  if(hops == k && start == t)
    {
      path++;
      return;
    }
  else if(hops >= k)
    return;
  for(int w = 1; w <= n; w++)
    if(routes[start][w])
      dfs(w, hops + 1);
}

Здесь k - длина пути, а routes [] [] - матрица смежности графа. path - глобальная переменная. Это может учитывать циклы - он учитывает ВСЕ пути заданной длины. С главного звонить

path = 0;
dfs(source, k);
cout<<path;

Обратите внимание, что количество узлов на единицу больше, чем количество переходов. Также обратите внимание, что если длина пути огромна, эта функция быстро накапливается. Никакой каламбур.

person unnoticed ringwraith    schedule 05.06.2012
comment
в DFS n - количество узлов, k - желаемая длина пути, а t - конечный узел, верно? - person Dominik T.; 05.06.2012
comment
ой, извините. Я не понимал, что вам нужны настоящие пути ... это просто даст вам количество путей. :П - person unnoticed ringwraith; 07.06.2012

arrow_upward
0
arrow_downward

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

person fdermishin    schedule 04.06.2012

arrow_upward
0
arrow_downward

Предположим, вы можете найти в графе путь длиной d, тогда вы можете запустить этот алгоритм | V | раз и найдите самый длинный путь, который является NP-полным. Итак, вы можете попробовать следующий подход -

1) алгоритм аппроксимации 2) метод грубой силы (больше подходит для программирования). Используйте графический процессор для ускорения вашего кода.

Также вам может быть интересно, что -

существует алгоритм линейного времени для DAG.

person Dipendra Kumar Mishra    schedule 10.07.2012