Вопросы по теме 'shortest-path'
Простая редукция (полнота NP)
Я ищу средство, чтобы доказать, что проблема кратчайшего пути бикритерии np завершена. То есть, учитывая граф с длинами и весами, мне нужно знать, существует ли путь в графе из s в t с общей длиной ‹= L и весом ‹= W.
Я знаю, что должен взять...
1195 просмотров
schedule
14.05.2022
Модификация алгоритма кратчайшего пути (маршрут от узла к самому себе)
Я применяю алгоритм кратчайшего пути для всех пар ( Floyd-Warshall ) к этому ориентированному графу:
Граф представлен своей матрицей смежности. Простой код выглядит так:
public class ShortestPath {
public static void main(String[] args)...
2832 просмотров
schedule
19.04.2023
Нециклический путь ко всем узлам
Есть ли алгоритм или набор алгоритмов, которые позволили бы вам найти кратчайшее расстояние пешком от произвольного начального узла, чтобы каждый узел посещался в весовом неориентированном графе? Это не совсем Коммивояжер, потому что меня не волнует,...
1513 просмотров
schedule
02.04.2022
Поиск кратчайшего пути между двумя точками сетки с помощью Haskell
Это проблема, которую я могу достаточно легко решить нефункциональным способом.
Но решение этого на Haskell доставляет мне большие проблемы. Моя неопытность, когда дело доходит до функционального программирования, безусловно, является причиной....
2948 просмотров
schedule
20.04.2022
Алгоритм поиска кратчайшего пути с наименьшим количеством пересадок
Я уже построил ориентированный граф со стоимостью (расстояние между каждой станцией) для трех маршрутов челноков. Стоимость проезда от станции до станции любого шаттла одинакова, поэтому остается только минимизировать пересадки.
Я хочу, чтобы это...
1662 просмотров
schedule
30.06.2022
Реализация A* в проверке PHP
Это код, который я получил с сайта здесь , и я хотел бы знать, реализация A* правильная. Я просмотрел его и сравнил со страницей в Википедии, и он кажется действительным. Причина, по которой я спрашиваю, заключается в том, что на сайте говорится,...
1448 просмотров
schedule
10.01.2024
Могу ли я использовать алгоритм Прима вместо алгоритма Дейкстры для поиска кратчайшего пути?
Я весь день боролся за понимание алгоритма Дейкстры и его реализацию без каких-либо значительных результатов. У меня есть матрица городов и их расстояний. Что я хочу сделать, так это указать точку отправления и точку назначения, чтобы найти...
2957 просмотров
schedule
28.02.2023
Возврат только вершин фактического кратчайшего пути
Я знаю, что заголовок немного сумбурный, но я не знаю, как его лучше объяснить.
Что я пытаюсь сделать:
Используя граф, найденный в текстовом файле, найдите и распечатайте кратчайший путь (минимальное количество вершин) из вершины A в вершину...
12487 просмотров
schedule
25.03.2023
Какой самый простой алгоритм / решение для кратчайшего пути одной пары через неориентированный граф с реальными весами?
Мне нужно найти кратчайший путь через неориентированный граф, узлы которого являются действительными (положительными и отрицательными) взвешенными. Эти веса подобны ресурсам, которые вы можете получить или потерять, войдя в узел.
Общая стоимость...
2791 просмотров
schedule
12.05.2022
Как найти лучший путь в графе со взвешенными узлами и вершинами
Допустим, у меня есть этот график
всегда полный график
один начальный узел - также финишный узел
взвешенные узлы и вершины
Я хочу найти путь как можно короче, но с лучшим результатом (сумма очков узлов) - другими словами, путь,...
1996 просмотров
schedule
29.08.2022
Минимальное связующее дерево между начальной точкой и набором требуемых узлов
Я пытаюсь определить оптимальный вариант поиска, чтобы сравнить его с написанным мной алгоритмом поиска.
У меня есть набор узлов, помеченных как «обязательные», и узел, помеченный как «начало», остальные помечены как «необязательные». Я хочу найти...
1282 просмотров
schedule
16.02.2022
Как реализовать алгоритм Дейкстры на Прологе, возвращающий список ребер?
Я уже некоторое время пытаюсь реализовать алгоритм кратчайшего пути Дейкстры в JIProlog. В Интернете доступно несколько реализаций, например здесь и здесь , но все они возвращают путь в виде списка узлов. Это проблематично для моей реализации,...
4859 просмотров
schedule
15.09.2023
Как я могу использовать алгоритм звезды, чтобы найти первые 100 кратчайших путей?
Как я могу использовать алгоритм звезды, чтобы найти первые 100 кратчайших путей?
2765 просмотров
schedule
06.11.2023
Кратчайший путь в попытке
Для проекта Data Structures я должен найти кратчайший путь между двумя словами, такими как «кошка» и «собака», но мне разрешено менять только одну букву за раз. Я пытаюсь сделать это, реализуя три и могу похоже, не может реализовать поиск кратчайшего...
663 просмотров
schedule
11.05.2022
Кратчайший путь в неориентированном графе, который посещает k вершин
Рассмотрим неориентированный граф. Есть n вершин и m ребер. У всех ребер есть вес.
Я хочу разработать алгоритм, который будет принимать исходную вершину «s», принимающую вершину «t» и число «k» в качестве входных данных. Результатом работы...
1424 просмотров
schedule
02.02.2022
Кратчайший путь между двумя заданными узлами в невзвешенном графе / дереве
Я ищу алгоритм для определения кратчайшего пути между двумя узлами невзвешенного графа с использованием матрицы смежности. Я знаю Дейкстру и Беллмана - Форда, но ни один из найденных не подходит для определения кратчайшего пути между двумя заданными...
4266 просмотров
schedule
24.11.2023
Распечатайте все координаты ячеек для кратчайшего пути
Я успешно разработал алгоритм кратчайшего пути для лабиринта (см. код ниже). Однако я хочу сохранить координаты кратчайшего пути в параметре стека, который передается в мою функцию. Может ли кто-нибудь посоветовать мне, как я могу этого добиться?...
3033 просмотров
schedule
22.08.2022
Как создать взвешенную матрицу смежности в Matlab
У меня есть набор данных в следующем формате:
UID Lat Long LocID
u1 lt1 lg1 l1
u1 lt2 lg2 l2
u1 lt3 lg3 l3
u2 lt4 lg4 l4
u3 lt1 lg1 l1
u3 lt4 lg4 l4
Отсюда мне...
1127 просмотров
schedule
24.02.2023
Максимальная прибыль с использованием алгоритма Дейкстры
Алгоритм Дейкстры — один из самых быстрых алгоритмов решения задачи о кратчайшем пути. В моем случае сеть состоит из узлов, где вес преимущества — это прибыль, которую я получаю. Мне было интересно, смогу ли я обратить алгоритм Дейкстры, чтобы...
2828 просмотров
schedule
12.05.2023
Как реализовать A* с минимальным количеством узлов на пути?
Я реализовал свой алгоритм A* таким образом, что он находит кратчайший путь к цели, учитывая, что он может перемещаться только в соседние/смежные ячейки. (Предположим, что узлы — это ячейки сетки). Таким образом, есть 8 окружающих клеток, которые он...
89 просмотров
schedule
17.04.2023
