Фиксированная длина пути между двумя узлами графа - PullRequest
Новая
       5

Фиксированная длина пути между двумя узлами графа

1 голос
/ 22 октября 2009

Существует ли алгоритм, который, если задано два узла на графике, найдет маршрут между ними, который принимает указанное количество прыжков? Любой узел может быть подключен к любому другому.

Точки на данный момент расположены в 2D-пространстве, поэтому я не уверен, что график является лучшим подходом.

Ответы [ 3 ]

2 голосов
/ 22 октября 2009
1 голос
/ 22 октября 2009

Тупой подход: (структура данных - массив стеков). В основном это поиск по ширине (BFS) до глубины N, за исключением того, что если петли разрешены (вы не уточнили, но я предполагаю, что это так), вы не исключаете посещенные узлы из дальнейшего поиска.

  1. Вставить начальный узел в стек, сохраненный в массиве с индексом 0 (индекс = глубина)

  2. Для каждого уровня / индекса "l" 0-N:

    Для каждого узла в стеке, хранящемся на уровне "l", найдите всех его соседей и поместите их в стек, хранящийся на уровне "l + 1".

    Важно: если ваша задача позволяет находить пути, содержащие петли, НЕ проверяйте, посещали ли вы какой-либо узел, который вы добавили. Если это не разрешает циклы, используйте хэш посещенных узлов, чтобы не добавлять ни одного узла дважды **

  3. Остановитесь, когда закончите уровень "N-1".

  4. Выполните цикл по всем узлам, которые вы только что добавили, в стек по индексу "N" и найдите целевой узел. Если найдено: успех, если нет, такой путь отсутствует.

Обратите внимание, что если под «каждый узел может быть связан» вы подразумеваете ПОЛНОСТЬЮ ПОДКЛЮЧЕННЫЙ граф, то существует математический ответ, не связанный с фактическим посещением узлов

(однако формула слишком длинна для записи в поле ввода текста StackOverflow)

1 голос
/ 22 октября 2009

Если у вас есть узлы, которые ищут маршруты с точки зрения прыжков, то, вероятно, правильный подход - график. Я не уверен, что понимаю, что вы пытаетесь сделать и каковы ограничения, тем не менее, особенно в отношении «Любой узел может быть подключен к любому другому» ... который кажется немного открытым.

Несмотря на это, однако; с некоторым графическим представлением:

Похоже, что начинать с первого узла и выполнять оттуда поиск в глубину и завершать поиск, если (a) количество выполненных прыжков больше указанного вами числа или (b) мы достигли второго узла; это определит первый (не только) путь, соединяющий два узла (не более) с таким количеством прыжков.

Если это должен быть точно указанный переход, прекратите любую ветвь поиска, если переходы прошли, и завершите с успехом, если вы также достигли второго узла.

...