Фиксированная длина пути между двумя узлами графа
https://stackoverflow.com/questions/1603334
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Существует ли алгоритм, который, если задано два узла на графике, найдет маршрут между ними, который принимает указанное количество прыжков? Любой узел может быть подключен к любому другому.
Точки на данный момент расположены в 2D-пространстве, поэтому я не уверен, что график является лучшим подходом.
Решение
Если у вас есть узлы, которые ищут маршруты с точки зрения прыжков, то, вероятно, правильный подход - график. Я не уверен, что понимаю, что вы пытаетесь сделать и каковы ограничения, тем не менее, особенно в отношении «любого узла может быть подключен к любому другому»; .. который кажется немного открытым.
Несмотря на это, однако; с некоторым графическим представлением:
Похоже, что начинать с первого узла и выполнять оттуда поиск в глубину и завершать поиск, если (a) количество выполненных прыжков больше указанного вами числа или (b) мы достигли второго узла; это определит первый (не только) путь, соединяющий два узла (не более) с таким количеством прыжков.
Если это должен быть точно указанный переход, прекратите любую ветвь поиска, если переходы прошли, и завершите с успехом, если вы также достигли второго узла.
Другие советы
Пробовали ли вы многократное углубление DFS ?
Тупой подход: (структура данных - это массив стеков). В основном это поиск по ширине (BFS) до глубины N, за исключением того, что если петли разрешены (вы не уточнили, но я предполагаю, что это так), вы не исключаете посещенные узлы из дальнейшего поиска.
<Ол>Вставьте начальный узел в стек, хранящийся в массиве с индексом 0 (индекс = глубина)
Для каждого уровня / индекса "l" 0-N:
Для каждого узла в стеке, хранящемся на уровне "l", найдите всех его соседей и поместите их в стек, хранящийся на уровне "l + 1".
Важно: , если ваша задача позволяет находить пути, содержащие петли, НЕ проверяйте, посещали ли вы какой-либо узел, который вы добавили. Если это не разрешает циклы, используйте хэш посещенных узлов, чтобы не добавлять ни одного узла дважды **
Остановитесь, когда закончите уровень "N-1".
Обведите все узлы, которые вы только что добавили, в стек по индексу " N " и найдите ваш пункт назначения. Если найдено: успех, если нет, такой путь отсутствует.
Обратите внимание, что если к «каждому узлу можно подключиться», вы подразумеваете, что граф ПОЛНО ПОДКЛЮЧЕН, тогда существует математический ответ, не затрагивающий фактически посещение узлов
(однако формула слишком длинна для записи в поле ввода текста StackOverflow)
