Публикации по теме 'shortest-path'
Алгоритм Флойда-Уоршалла вручную
Хотя обычно достаточно просто понять, что алгоритм принимает в качестве параметров и что он возвращает, часто полезно более глубокое понимание этого. Лично я предпочитаю получить это понимание, выполняя вычисления для примера вручную, так как это заставляет меня действительно понимать каждый шаг алгоритма.
Что такое алгоритм Флойда-Уоршалла
Алгоритм Флойда-Уоршалла — это алгоритм поиска кратчайшего пути в ориентированном взвешенном графе. Алгоритм принимает представление матрицы..
Вопросы по теме 'shortest-path'
Кратчайший путь для дага
У меня есть граф с вершинами s и t, между которыми мне нужно найти кратчайший путь. У графика есть много специальных свойств, на которых я хотел бы извлечь выгоду:
Граф представляет собой DAG (ориентированный ациклический граф).
Я могу создать...
12441 просмотров
schedule
14.05.2022
поиск всех путей и кратчайшего пути для графа - Prolog
У меня проблема в моем коде с турбо-прологом, который ищет все пути и кратчайший путь в графе между двумя узлами. Проблема, которая у меня есть, заключается в том, чтобы проверить, находится ли узел в списке или нет (точно в предложении члена)...
10160 просмотров
schedule
09.03.2022
Как оптимизировать алгоритм Дейкстры для одного кратчайшего пути между двумя узлами?
Я пытался понять эту реализацию алгоритма Дейкстры на C и в то же время измените его так, чтобы был найден только кратчайший путь между двумя конкретными узлами (источник и пункт назначения).
Однако я не знаю точно, что делать. Как я это вижу,...
16138 просмотров
schedule
01.01.2023
кратчайший путь через лабиринт
Я работаю над проектом, в котором я должен пройти лабиринт, используя правило левой руки, и на основе пересечений, на которые попадает программа, мне нужно создать узел для подключения к графу, по которому я затем определю кратчайший путь. Цель...
2071 просмотров
schedule
02.07.2022
Расслабляет ли алгоритм Дейкстраса края кратчайшего пути по порядку?
В упражнении 24.3-5 «Введение в алгоритмы, 3-е издание» нужен пример того, что это неверно (не всегда верно). Это возможно? На мой взгляд, это невозможно, потому что каждое ребро расслаблено в то время, когда путь к текущей вершине уже определен....
7068 просмотров
schedule
25.05.2023
Дейкстра против Флойда-Уоршалла: поиск оптимального маршрута для всех пар узлов
Я читаю об алгоритме Дейкстры и алгоритме Флойда-Уоршалла. Я понимаю, что Dijkstra's находит оптимальный маршрут от одного узла ко всем другим узлам, а Floyd-Warshall находит оптимальный маршрут для всех пар узлов.
Мой вопрос: был бы алгоритм...
38531 просмотров
schedule
31.05.2022
Как определить факты в prolog db для планирования маршрутов метро?
Ну, я не могу решить, как мои факты должны выглядеть в базе данных пролога... и моя задача - написать предикат, который даст вам кратчайший путь между двумя станциями метро. У меня есть идея для решения этой проблемы, но меня беспокоит, как эффективно...
508 просмотров
schedule
09.08.2023
Кратчайший путь Java
Я пытаюсь сделать небольшую игру в защиту башни на Java. У меня есть сетка, состоящая из массива Point2D.Double с именем:
ПолеАрр[h][v]
h представляет горизонтальные поля, v вертикальные вертикальные поля
получается вот такая сетка...
3963 просмотров
schedule
30.04.2022
A* манхэттенское расстояние
Я искал алгоритм/псевдокод A*, следовал ему и закодировал. Я использовал манхэттенское расстояние для h(n). ( f(n) = g(n) + h(n) ) И это результат,
Это всегда происходит, когда нет стен, преграждающих путь, но когда я ставлю много стен,...
16006 просмотров
schedule
04.06.2022
Найдите кратчайший путь с помощью Boost Dijkstra с указанным МАКСИМАЛЬНЫМ РАССТОЯНИЕМ
Мне нравится использовать реализацию dijkstra от boost, чтобы найти кратчайший путь от узла
Однако в моей текущей проблеме у меня огромный граф, и мне нужно только найти кратчайшие пути к узлам, которые находятся на определенном расстоянии.
Я...
671 просмотров
schedule
17.01.2024
Как найти оптимальный маршрут к одному из множества маркеров?
На карте у меня есть массивы маркеров. Один статический, назовем station . Остальные тоже статичны, но они временные, назовем их fire . При нажатии на fire кратчайший маршрут должен быть построен к одному из stations . Я использую...
1249 просмотров
schedule
14.06.2023
Флойд-Уоршалл: все кратчайшие пути
Я реализовал метод Floyd-Warshall, чтобы возвращать расстояние кратчайшего пути между каждой парой узлов / вершин и единственного кратчайшего пути между каждой из этих пар.
Есть ли способ заставить его возвращать каждый кратчайший путь, даже если...
8047 просмотров
schedule
08.02.2023
Расчет расстояний между несколькими источниками и целями с помощью pgRouting
Я использую Postgres / PostGIS / pgRouting для подготовки набора данных для анализа, который я выполняю. Одно поле в наборе данных, которое мне нужно подготовить, - это кратчайшее расстояние между набором данных из 100 000 домашних хозяйств (точечные...
1522 просмотров
schedule
06.02.2023
Как обнаружить квадраты в сетке, которые НИКОГДА не могут быть частью кратчайшего пути после добавления блоков?
У меня есть сетка с началом, концом и некоторыми стенами. Юниты выбирают кратчайший путь (двигаются только вверх/вниз/влево/вправо) от начала до конца, минуя стены.
Пользователю разрешено добавлять столько дополнительных стен, сколько он...
776 просмотров
schedule
08.03.2022
кратчайший путь с поворотом одной кромки на ноль
задан неориентированный взвешенный граф G и две вершины: начальная вершина и конечная вершина
Какой самый эффективный алгоритм, который находит кратчайший путь от начала до конца с возможностью обратить вес ровно одного ребра в ноль?...
2439 просмотров
schedule
23.02.2023
Поиск всех кратчайших путей между двумя узлами в невзвешенном неориентированном графе
Мне нужна помощь в поиске всех кратчайших путей между двумя узлами в невзвешенном неориентированном графе .
Я могу найти один из кратчайших путей с помощью BFS, но пока я не понимаю, как мне найти и распечатать их все.
Любое представление об...
47872 просмотров
schedule
14.01.2024
Алгоритм удаления наименьшего количества ребер для увеличения длины кратчайшего пути в невзвешенном неориентированном графе
Учитывая матрицу смежности для невзвешенного неориентированного графа, существует ли эффективный способ (полиномиальный алгоритм) расширить / увеличить длину кратчайшего пути между любыми заданными двумя узлами s и t?
Пример:
В приведенном...
1981 просмотров
schedule
04.07.2023
Одна пара кратчайший путь несколько путешественников
Я программирую пошаговую стратегическую игру, и у меня есть особая проблема кратчайшего пути для одной пары. У меня есть взвешенный ориентированный граф с неотрицательными ненулевыми весами ребер, и вот загвоздка с несколькими путешественниками, то...
164 просмотров
schedule
09.05.2023
ИЗОБРАЖЕНИЕ В R: Найдите путь между вершинами, который максимизирует произведение атрибутов ребер.
Мне нужно найти способ найти путь между двумя вершинами, который максимизирует произведение атрибутов ребра. В моем случае атрибут края — это вероятность соединения. Предположим, я хочу найти путь с максимальной вероятностью между вершинами 1 и 4 в...
1433 просмотров
schedule
15.06.2023
кратчайший путь из нескольких наборов
Мне нужно найти кратчайший путь между узлами в различных наборах, где я могу использовать узел только один раз из каждого набора. Каждый узел связан через расстояние со всеми остальными узлами. Существует исключение, когда узлы в наборе не связаны...
238 просмотров
schedule
25.06.2023
