Публикации по теме 'shortest-path'
Головоломка для программирования: билет на скоростное прохождение
Я люблю спидраны, будь то Видео Summoning Salt или Селеста 202-ягодные забеги . Но вопрос скорости прохождения Как быстро можно пройти игру? это не то, что вы часто видите в настольных играх. Но в моем последнем упражнении я посмотрел на новую любимую игру моего сына Ticket to Ride First Journey , о которой можно задать этот существенный вопрос. Программирование ответа на него — это то, что отправит нас в одиссею оценки, приближения, эвристики и старомодного поиска методом грубой..
Беллман Форд против Дейкстры (Интуиция)
Алгоритм Беллмана Форда используется для поиска кратчайшего пути в графе, содержащем отрицательные ребра. Алгоритм Дейкстры, используемый для той же цели, работает для графов без отрицательных ребер. Основная идея здесь состоит в том, чтобы продолжать извлекать узел, который в данный момент находится на минимальном расстоянии. Это результат предположения, что добавление дополнительных ребер увеличивает стоимость пути, и это верно для графа с положительными ребрами.
В графе с..
Объяснение кода Дейкстры на C++
Он будет немного большим, так как я все объясню. Вот ссылка на очень простую и прямую задачу алгоритма Дейкстры, чтобы попробовать и
"решение"
Пожалуйста, прочитайте немного теории Дейкстры в Интернете или в какой-нибудь книге, надеюсь, вы легко ее найдете.
Объяснение кода выглядит следующим образом:
**Что нужно сделать (в задаче)››› Требуется найти кратчайший путь от вершины 1 до последней, т.е. количество вершин равно последней, так как они пронумерованы последовательно от 1 до..
Кратчайший путь алгоритма Беллмана Форда с одним источником
Алгоритм Беллмана-Форда находит кратчайший путь от исходной вершины ко всем вершинам графа. Граф может содержать ребра с отрицательным весом, но не должен содержать цикл с отрицательным весом, достижимый из исходной вершины.
Алгоритм возвращает TRUE, если нет цикла с отрицательным весом, и FALSE, если существует цикл с отрицательным весом, достижимый из исходной вершины. Если существует цикл с отрицательным весом, достижимый из исходной вершины, то решения не существует.
На рис...
Динамическое программирование в Javascript
Что такое динамическое программирование?
Метод решения сложной проблемы путем разбиения ее на набор более простых подзадач, решения каждой из этих подзадач только один раз и сохранения их решений. Динамическое программирование работает над проблемами с оптимальной подструктурой и перекрывающимися подзадачами.
Оптимальная основа
Говорят, что проблема имеет оптимальную подструктуру , если оптимальное решение может быть построено из оптимальных решений ее подзадач. Пример:
Глядя..
Понимание алгоритма Флойда-Уоршалла
Первоначально опубликовано на Seedbx.com 2 декабря 2020 г.
Поиск кратчайшего пути во взвешенном графе — сложная задача, но поиск кратчайшего пути из каждой вершины в любую другую вершину — непростая задача.
В этом посте мы обсудим алгоритм Флойда-Уоршалла, который идеально подходит для этой работы.
Примечание . Во всех псевдокодах используется индексация на основе 0, а отступы используются для различения блоков кодов.
Постановка задачи
Пусть G — взвешенный ориентированный..
Вопросы по теме 'shortest-path'
Предложения для KSPA на неориентированном графе
Существует специальная реализация KSPA, которую нужно переписать. Текущая реализация использует модифицированный алгоритм Дейкстры, псевдокод которого примерно объясняется ниже. Я так думаю, он широко известен как KSPA, использующий стратегию...
828 просмотров
schedule
02.09.2022
Получение кратчайшего пути между двумя узлами в quickgraph
я хочу спросить, есть ли способ сгенерировать кратчайший путь от узла A к узлу B без создания кратчайших путей ко всем другим узлам (остановиться, когда узел B находится в исследуемом наборе) с A-звездой в QuickGraph.
Я хочу подключить QuickGraph к...
2826 просмотров
schedule
19.11.2022
Производительность алгоритма кратчайшего пути в JUNG API
Я использую JUNG API для расчета кратчайших путей между несколькими узлами в графах среднего размера (от 20 до 100 узлов). Прямо сейчас я перебираю свои узлы и использую простую функцию «ShortetsPath», чтобы вычислить кратчайший путь для двух узлов....
1969 просмотров
schedule
06.07.2023
Используя кучу Фибоначчи, возможно ли/легко представить соседей, а также минимальное расстояние
Я пытаюсь разработать реализацию dijkstras с кучами Фибоначчи. Я пытаюсь понять, возможно ли представить, кроме минимального расстояния в O (logn) (с удалением), но соседей любого заданного узла? Или это нарушает структуру кучи Фибоначчи? В...
389 просмотров
schedule
09.04.2023
Как установить целевую вершину в QuickGraph Dijkstra или A*
Я использую QuickGraph версии 3.6 и нашел функцию SetRootVertex, но не нашел SetTagretVertex. Мне это нужно, потому что я ищу короткие пути в огромном графе, и это значительно ускорит программу.
Речь идет о классах DijkstraShortestPathAlgorithm и...
2254 просмотров
schedule
13.11.2022
Как найти все вершинно-непересекающиеся пути в графе?
Предположим, что в графе есть 3 целевых узла.
Путь с непересекающимися вершинами означает, что на пути нет одинаковых узлов, кроме конечных узлов.
Как для любого отдельного узла, скажем, узла i, найти все вершинно-непересекающиеся пути от узла i...
25565 просмотров
schedule
27.10.2022
Как найти все кратчайшие пути с помощью алгоритма A*?
Я знаю, что алгоритм A * может найти кратчайший путь. Но проблема в моей работе в том, что мне нужно найти все кратчайшие пути. Точнее, может существовать несколько кратчайших путей, но мне нужно выбрать один кратчайший путь в порядке приоритета...
2126 просмотров
schedule
29.09.2022
Кратчайший путь при отсутствии данного ребра
Предположим, нам дан взвешенный граф G (V, E).
Граф содержит N вершин ( пронумерованных от 0 до N-1 ) и M двунаправленных ребер .
Каждое ребро (vi, vj) имеет положительное расстояние d (т.е. расстояние между двумя вершинами vivj равно d)...
3178 просмотров
schedule
16.06.2023
найти, существует ли путь определенной длины в ациклическом графе
В ациклическом графе я пытаюсь выяснить, существует ли путь длины L между двумя заданными узлами. Мои вопросы в том, какой лучший и самый простой алгоритм для использования в этом случае.
Обратите внимание, что граф имеет максимум 50 узлов и 100...
2281 просмотров
schedule
17.11.2022
Кратчайшие пути для всех пар, разрешение ничьей
Я создаю программу, которая будет вычислять центральность межличностного отношения для всех узлов в невзвешенном графе. Для этого мне нужно найти ASSSP (Все кратчайшие пути из одного источника). Создавая программу, я понял, что со временем у меня...
1563 просмотров
schedule
12.12.2022
Поиск кратчайшего пути с помощью FGL
Я использую библиотеку функциональных графов Мартина Эрвига (FGL) для представления следующего простого ориентированного взвешенного графа.
genLNodes :: [LNode String]
genLNodes = zip [1..5] ["A","B","C","D","E"]
genLEdges :: [LEdge Int]...
1083 просмотров
schedule
08.05.2023
Кратчайший путь в плане шестиугольника?
В последнем соревновании IEEE Xtreme я пытался решить следующую проблему:
Input Две точки p1(x1,y1) , p2(x2,y2) вы должны найти длину кратчайшего пути от p1 до p2,
например, если p1(1,1), p2(4,4), то кратчайший путь имеет длину 9 ребер,...
1117 просмотров
schedule
12.04.2022
Мультиграф и самый дешевый путь
Мне нужно решить проблему, мне нужно найти самый дешевый путь между двумя городами, но есть несколько возможных путей между двумя соседними городами, поэтому у меня есть мультиграф, и я могу получить скидку между двумя краями. Существует ли алгоритм...
2806 просмотров
schedule
22.02.2024
Кратчайшее расстояние пути между точками, заданными как координаты X-Y
В настоящее время я работаю над проектом, в котором есть вектор, содержащий координаты X и Y примерно для 800 точек. Эти точки представляют собой электрическую сеть линий. Моя цель — вычислить путь кратчайшего расстояния между точкой A и точкой B,...
4823 просмотров
schedule
16.05.2022
существует ли маршрут из города a в город b не более чем за x дней?
Я был на собеседовании в торговой фирме, мне задали этот вопрос,
вы путешествуете по штату на автобусах, автобусы могут останавливаться в любых C возможных городах, и вам нужно найти способ добраться из города a в город b. Всего имеется B...
1512 просмотров
schedule
05.11.2022
Нахождение кратчайшего пути
У меня есть набор точек на графике. Я хочу найти кратчайший путь, соединяющий подмножество этого графика, используя линии, которые являются горизонтальными, вертикальными или под углом 45 градусов влево или вправо. Кто-нибудь может предложить...
121 просмотров
schedule
24.08.2022
Алгоритм поиска кратчайшего пути сквозь стену
Я пишу ИИ для текстовой игры, и проблема в том, что я застрял в том, как определить самый тонкий участок стены. Например, следующее представляет 2D-карту, где «^» — это персонаж, который хочет пройти сквозь стену, представленную символами «*», в...
1836 просмотров
schedule
12.01.2023
путаница с алгоритмом Дейкстры?
Согласно книге по алгоритмам Corman , Дейкстра применим только к тем графам, все ребра которых имеют неотрицательные веса. Означает ли это, что если есть какое-либо ребро с отрицательным весом, оно не будет работать для всего графа? или не будет ли...
669 просмотров
schedule
07.07.2022
Путь с минимальной стоимостью для посещения набора точек в заданном порядке ровно один раз?
Эта проблема:
Нам дан набор из N точек на двумерной плоскости, мы должны найти путь, который проходит через все точки в порядке 1-2-3....N и возвращается к 1 таким образом, чтобы затрачиваемое время было минимальным. Мы можем переместиться на один...
968 просмотров
schedule
20.08.2022
Поиск кратчайших путей взвешенного графа с использованием стеков
Мне будет предоставлен какой-то такой график, как на картинке ниже. Я искал некоторые алгоритмы, но мне кажется, что я не могу их понять. На самом деле, используя алгоритм Флойда-Уоршалла , это вроде как возможно, но к сожалению, мне разрешено...
1415 просмотров
schedule
08.09.2022
