Есть ли алгоритм, который будет, если заданы два узла на графике, найти маршрут между ними, который принимает указанное количество переходов? Любой узел может быть подключен к любому другому.Исправлена длина пути между двумя узлами графа
Точки в данный момент находятся в 2D-пространстве, поэтому я не уверен, что график лучше всего подходит.
Если у вас есть узлы, которые ищут маршруты в терминах переходов, то график, вероятно, является правильным подходом. Я не уверен, что понимаю, что вы пытаетесь сделать и какие ограничения существуют, особенно в отношении «Любой узел может быть подключен к любому другому» .., который кажется немного открытым.
Не считая этого, однако; с некоторым графическим представлением:
Кажется, что начинаем с первого узла и делаем там первый поиск глубины и завершаем поиск, если (а) сделанные переходы больше указанного вами числа или (b) мы имеем прибыл во второй узел; это определит первый (не только) путь, соединяющий два узла в (самое большее), что много переходов.
Если он должен быть точно указанными перелетами, завершите любую ветвь поиска, если хмель перешли, и прекратите успешно, если вы также прибыли на второй узел.
Вы попробовали iterated-deepening DFS?
Тупой подход: (структура данных представляет собой массив стеков). Это в основном делает Breadth First Search (BFS) до глубины N, за исключением того, что если разрешены циклы (вы не уточнили, но я предполагаю, что они есть), вы не исключаете посещаемые узлы из дальнейшего поиска.
Нажмите начальный узел на стеке хранится в массиве с индексом 0 (индекс = глубина)
Для каждого уровня/индекса "л" 0-N:
Для каждого узла на стек, хранящийся на уровне «l», найти всех его соседей и направить их в стек, хранящийся на уровне «l + 1».
Важно: Если ваша задача позволяет находить пути, содержащие циклы, НЕ проверяйте, уже ли вы посещали какой-либо узел, который вы добавляете. Если он не разрешает циклы, используйте хеш посещенных узлов, чтобы не добавлять ни одного узла дважды **
Остановить, когда вы закончите уровень «N-1».
Прокрутите все узлы, которые вы только что добавили в стек, указав «N», и найдите свой целевой узел. Если обнаружено: успех, если нет, нет такого пути.
Пожалуйста, обратите внимание, что если на «каждый узел может быть подключен» вы подразумевающее ПОЛНОСТЬЮ связный граф, то существует математический ответ, не связанных с фактически посещающие узлы
(впрочем, формула слишком долго писать в поле ввода текста StackOverflow)
Просто шутите - если # из узлов полностью связанного графика N> = 3, возможно, можно перейти от любого узла к любому узлу через ЛЮБОЕ число шагов S. Если S% 3 == 0, перемещайтесь по любому треугольнику для S/3-1 раз, затем перейдите на любой другой узел, вернитесь к месту назначения и перейдите к целевому узлу. Если S% 3 == 1, пройдите вокруг любого треугольника для S/3-1 раз, затем перейдите к целевому узлу. Если S% 3 == 2, перемещайтесь вокруг любого треугольника для S/3-1 раз, затем перейдите к любому другому узлу, а затем к целевому узлу. СДЕЛАННЫЙ. – DVK
0 Я не уверен, что существует хороший алгоритм, но я знаю, что вы не всегда будете иметь правильное решение. Например, если у вас треугольный граф, вы не найдете пути от точки A до точки B, которая занимает 3 прыжка. –
Вы можете, если вам разрешено повторно посещать узлы, например. путешествовать по кругу.Чтобы перейти с 1 на 2, пройдите 1-3-1-2. 3 прыжка, и вы там. – DVK