Вопрос по algorithm – Как найти путь точной длины в графе

1

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

Узлы не могут быть снова посещены.

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

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

& quot; путь, который близок к моим ожиданиям & quot; - это расплывчато. goat

Ваш Ответ

5   ответов
2

Гамильтонова проблема цикла, учитывая эффективный алгоритм решения Вашей проблемы.

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

1

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 - длина пути, а route [] [] - матрица смежности графа. путь является глобальной переменной. Это может учитывать циклы - это учитывает ВСЕ пути заданной длины. С главной звоните

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

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

@DominikT .: да
ой, извините. я не осознавал, что вам нужны настоящие пути ... это просто даст вам количество путей. :П
в DFS n - количество узлов, k - желаемая длина пути, а t - конечный узел, верно? Dominik T.
6

чтобы рекурсивно найти путь необходимой длины.

Код Псуэдо:

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

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

Замечания:

The algorithm will generate paths that might not be simple. If you need only simple paths - you also need to maintain visited set, and add each vertex when you append it to the found path, and remove it when you remove it from the path. If you want to find only one such path - you should return value from the function, (true if such a path was found), and break the loop (and return true) when the return value is true.
Я пытался создать ваш псевдокод на Java, но что-то не так, и я не знаю, что:pastebin.com/60u3FYmf   Где adj [] [] - это моя матрица смежности графа, а путь хранится в стеке. Dominik T.
У меня есть такой график (сейчас я тестирую этот):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 Dominik T.
Ну, не могу быть уверен, но с первого взгляда: (1) Почему вы перебираете от 1 до numVertex включительно, а не от 0 до numVertex-1 включительно? массивы в Java основаны на 0. (2) Кажется, ты скучаешьvisited.pop() после рекурсивного вызова, поэтомуvisited набор заполняется, но элементы никогда не удаляются после того, как вы исчерпали определенный путь. (3) Должно быть еще одно предложение остановки (которое я также пропустил в псевдокоде, скоро отредактирую) дляdepth == 0 && v is not target - который должен прекратить эту ветку.
0

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

0

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

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

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

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

Похожие вопросы