Программу Для Нахождения Кратчайшего Пути
Хочется написать программу, которая выдаст оптимальный маршрут между двумя адресами (с учетом расписания движения общественного транспорта - метро, автобус, трамвай). Скажите, пожалуйста, что и где почитать по теме? По каким ключевым словам искать ресурсы? Программы: Программа для нахождения кратчайшего пути сборки кубика: Скачать. Алгоритм предназначен для нахождения К путей. Кратчайшего пути Pk-1. Пути Программа.
Наверняка многим из гейм-девелоперов (или просто людям, увлекающимися програмировагнием) будет интересно услышать эти четыре важнейших алгоритма, решающих задачи о кратчайших путях. Сформулируем определения и задачу. Графом будем называть несколько точек (вершин), некоторые пары которых соединены отрезками (рёбрами).
Граф связный, если от каждой вершины можно дойти до любой другой по этим отрезкам. Циклом назовём какой-то путь по рёбрам графа, начинающегося и заканчивающегося в одной и той же вершине. И ещё граф называется взвешенным, если каждому ребру соответствует какое-то число (вес). Не может быть двух рёбер, соединяющих одни и те же вершины. Каждый из алгоритмов будет решать какую-то задачу о кратчайших путях на взвешенном связном. Кратчайший путь из одной вершины в другую — это такой путь по рёбрам, что сумма весов рёбер, по которым мы прошли будет минимальна.
Для ясности приведу пример такой задачи в реальной жизни. Пусть, в стране есть несколько городов и дорог, соединяющих эти города. При этом у каждой дороги есть длина.
Вы хотите попасть из одного города в другой, проехав как можно меньший путь. Считаем, что в графе n вершин и m рёбер.
Пойдём от простого к сложному. Алгоритм Флойда-Уоршелла Находит расстояние от каждой вершины до каждой за количество операций порядка n^3. Веса могут быть отрицательными, но у нас не может быть циклов с отрицательной суммой весов рёбер (иначе мы можем ходить по нему сколько душе угодно и каждый раз уменьшать сумму, так не интересно). В массиве d0 n — 10 n — 1 на i-ой итерации будем хранить ответ на исходную задачу с ограничением на то, что в качестве «пересадочных» в пути мы будем использовать вершины с номером строго меньше i — 1 (вершины нумеруем с нуля).
Пусть идёт i-ая итерация, и мы хотим обновить массив до i + 1-ой. Для этого для каждой пары вершин просто попытаемся взять в качестве пересадочной i — 1-ую вершину, и если это улучшает ответ, то так и оставим.
Всего сделаем n + 1 итерацию, после её завершения в качестве «пересадочных» мы сможем использовать любую, и массив d будет являться ответом. N итераций по n итераций по n итераций, итого порядка n^3 операций. Псевдокод: прочитать g // g0. N - 1 - массив, в котором хранятся веса рёбер, gij =, если ребра между i и j нет d = g for i = 1. N + 1 for j = 0. N - 1 for k = 0. N - 1 if djk dji - 1 + di - 1k djk = dji - 1 + di - 1k вывести d Алгоритм Форда-Беллмана Находит расстояние от одной вершины (дадим ей номер 0) до всех остальных за количество операций порядка n.
m. Аналогично предыдущему алгоритму, веса могут быть отрицательными, но у нас не может быть циклов с отрицательной суммой весов рёбер. Заведём массив d0 n — 1, в котором на i-ой итерации будем хранить ответ на исходную задачу с ограничением на то, что в путь должно входить строго меньше i рёбер. Если таких путей до вершины j нет, то dj = (это должна быть какая-то недостижимая константа, «бесконечность»). В самом начале d заполнен. Чтобы обновлять на i-ой итерации массив, надо просто пройти по каждому ребру и попробовать улучшить расстояние до вершин, которые оно соединяет.
Кратчайшие пути не содержат циклов, так как все циклы неотрицательны, и мы можем убрать цикл из путя, при этом длина пути не ухудшится (хочется также отметить, что именно так можно найти отрицательные циклы в графе: надо сделать ещё одну итерацию и посмотреть, не улучшилось ли расстояние до какой-нибудь вершины). Поэтому длина кратчайшего пути не больше n — 1, значит, после n-ой итерации d будет ответом на задачу. N итераций по m итераций, итого порядка n. m операций. Псевдокод: прочитать e // e0. M - 1 - массив, в котором хранятся рёбра и их веса (first, second - вершины, соединяемые ребром, value - вес ребра) for i = 0. N - 1 di = d0 = 0 for i = 1.
M - 1 if dej.second dej.first + ej.value dej.second = dej.first + ej.value if dej.first dej.second + ej.value dej.first = dej.second + ej.value вывести d Алгоритм Дейкстры Находит расстояние от одной вершины (дадим ей номер 0) до всех остальных за количество операций порядка n^2. Все веса неотрицательны. На каждой итерации какие-то вершины будут помечены, а какие-то нет. Заведём два массива: mark0 n — 1 — True, если вершина помечена, False иначе, d0 n — 1 — для каждой вершины будет храниться длина кратчайшего пути, проходящего только по помеченным вершинам в качестве «пересадочных». Также поддерживается инвариант того, что для помеченных вершин длина, указанная в d, и есть ответ.
Сначала помечена только вершина 0, а gi равно x, если 0 и i соединяет ребро весом x, равно, если их не соединяет ребро, и равно 0, если i = 0. На каждой итерации мы находим вершину, с наименьшим значением в d среди непомеченных, пусть это вершина v. Тогда значение dv является ответом для v. Пусть, кратчайший путь до v из 0 проходит не только по помеченным вершинам в качестве «пересадочных», и при этом он короче dv. Возьмём первую встретившуюся непомеченную вершину на этом пути, назовём её u. Длина пройденной части пути (от 0 до u) — du.
Len = du, где len — длина кратчайшего пути из 0 до v (т. Отрицательных рёбер нет), но по нашему предположению len меньше dv. Значит, dv len = du. Но тогда v не подходит под своё описание — у неё не наименьшее значение dv среди непомеченных. Теперь смело помечаем вершину v и пересчитываем d. Так делаем, пока все вершины не станут помеченными, и d не станет ответом на задачу. N итераций по n итераций (на поиск вершины v), итого порядка n^2 операций.
Псевдокод: прочитать g // g0. N - 1 - массив, в котором хранятся веса рёбер, gij =, если ребра между i и j нет d = g d0 = 0 mark0 = True for i = 1. N - 1 marki = False for i = 1. N - 1 v = -1 for i = 0. N - 1 if (not marki) and ((v -1) or (dv di)) v = i markv = True for i = 0. N - 1 if di dv + gvi di = dv + gvi вывести d Алгоритм Дейкстры для разреженных графов Делает то же самое, что и алгоритм Дейкстры, но за количество операций порядка m. log(n).
Следует заметить, что m может быть порядка n^2, то есть эта вариация алгоритма Дейкстры не всегда быстрее классической, а только при маленьких m. Что нам нужно в алгоритме Дейкстры? Нам нужно уметь находить по значению d минимальную вершину и уметь обновлять значение d в какой-то вершине.
В классической реализации мы пользуемся простым массивом, находить минимальную по d вершину мы можем за порядка n операций, а обновлять — за 1 операцию. Воспользуемся (во многих объектно-ориентированных языках она встроена). Куча поддерживает операции: добавить в кучу элемент (за порядка log(n) операций), найти минимальный элемент (за 1 операцию), удалить минимальный элемент (за порядка log(n) операций), где n — количество элементов в куче.
Создадим массив d0 n — 1 (его значение то же самое, что и раньше) и кучу q. В куче будем хранить пары из номера вершины v и dv (сравниваться пары должны по dv). Также в куче могут быть фиктивные элементы.
Так происходит, потому что значение dv обновляется, но мы не можем изменить его в куче. Поэтому в куче могут быть несколько элементов с одинаковым номером вершины, но с разным значением d (но всего вершин в куче будет не более m, я гарантирую это).
Когда мы берём минимальное значение в куче, надо проверить, является ли этот элемент фиктивным. Для этого достаточно сравнить значение d в куче и реальное его значение. А ещё для записи графа вместо двоичного массива используем массив списков.
M раз добавляем элемент в кучу, получаем порядка m. log(n) операций.
Псевдокод: прочитать g // g0. N - 1 - массив списков, в i-ом списке хранятся пары: first - вершина, соединённая с i-ой вершиной ребром, second - вес этого ребра d0 = 0 for i = 0. N - 1 di = for i in g0 // python style di.first = i.second q.add(pair(i.second, i.first)) for i = 1. N - 1 v = -1 while (v = -1) or (dv!= val) v = q.top.second val = q.top.first q.removeTop markv = true for i in gv if di.first dv + i.second di.first = dv + i.second q.add(pair(di.first, i.first)) вывести d Метки:.
Добавить метки Пометьте публикацию своими метками Метки лучше разделять запятой. Например: программирование, алгоритмы. К сожалению, А. показывает не очень хорошую скорость. И, например, в стратегии, где надо пускать много юнитов по длинному пути (выбрали пачку из 100 юнитов и шлём на вражескую базу за речкой в другом конце карты) в обычном виде будет страшно глючить. Я бы с удовольствием почитал об оптимизациях этих алгоритмов.
Были мысли о кешировании результата (но как корректно применить кеш, что делать при динамически меняющейся карте) и (бить карту на блоки/использовать контрольные точки). Но всё-же хотелось бы почитать про готовые решения. Действительно, в этой статье алгоритмы поиска в графе описаны в больше мере с математической точки зрения, нежели с точки зрения гейм-дева. В играх поиск пути обычно заканчивается на А. и компании ( IDA, D., fringe search ) а дальше идут специфичные для представления и топологии карты оптимизации — иерархический поиск, мемоизация, прогрессивное улучшение, адаптивный поиск итп. Если же игра — интерактивная, то найденное решение требует дальнейшей обработки с учетом динамических коллизий, сглаживания и всего остального.
Программа Для Драйверов
Кстате, стоит упомянуть, что поиск на графе даже в гейм-деве не ограничивается картами. Это так же ИИ, планирование и многое другое.