Киньте в меня алгоритмами выбора оптимального пути из А в Б.

← →
Карелин Артем © (2005-09-29 13:51) [0]

Задача такая: есть нехилая карта города, надо разработать алгоритм поиска пути из одного места в другое по улицам города с учетом степени сложности дорог между точками.

← →
stone © (2005-09-29 13:52) [1]

Графы?

← →
XGarik © (2005-09-29 14:00) [2]

Тут смотрел:
http://algolist.manual.ru/

← →
alpet © (2005-09-29 14:01) [3]

Аналоговый способ: карта выполняется из стекла, все дороги представляют собой каналы заполненные к примеру аргоном. В точках A и B прикладывается напряжение. По идее короткий путь должен высветится.

← →
Карелин Артем © (2005-09-29 14:35) [4]

> alpet © (29.09.05 14:01) [3]

Хех. Это сколько же будет стоить карта города из стекла? И как сложность учитывать? :))

> stone © (29.09.05 13:52) [1]

А конкретнее можно название этой предметной области в целях самостоятельных раскопок информации? А то у меня образования академического в программировании нет. Даже как правильно этот раздел теории назвать не знаю.

← →
stone © (2005-09-29 14:38) [5]

> Карелин Артем © (29.09.05 14:35) [4]

А так и называется, в базу заносятся все участки дорог, а потом, используя теорию графов, можно получить наиболее короткий (оптимальный) маршрут

← →
TUser © (2005-09-29 15:01) [6]

Выбираем начальную точку. Добавляем ее в множество Reached. Далее последовательно делаем следующее
1. Найти самое дешевое ребро, исходящее из Reached (т.е. самое дешевое из всех тех ребер, одна из вершин которых уже есть в Reached, а второй там нет. Пусть это вершины А и Б). Цена ребра при этом равна цене пути из начала в А + метка, которая приписана этому ребру.
2. Добавить эту вторую вершину в Reached. Кратчайший путь в Б есть "Кратчайший путь в А" + "добавленное ребро". Если она - конечная вершина, то заканчиваем работу.

Корректность алгоритма (алгоритм Дейкстры). Пусть в некоторый момент в Reached находятся вершины, для которых кратчайшие пути найдены правильно. При этом находимый путь в вершину Б также будет самым дешевым. Действителньо, из всех путей, проведенных исключительно через вершины множества Reached, этот - самый дешевый. А если предположить, что найдется другой более дешевый путь начало -> Reached -> не-Reached -> Б, то получается, что должно быть выбрано ребро, ведущее не в Б, а в некоторую другую вершину. На первом шаге работы алгоритма Reached состоит из одной вершины - начала - и путь туда (из начала в начало) указан правильно. Таким образом первая вершина будет добавлена корректно, а потом вторая и все последующие.

Ассимптотика алгоритма - квадратичная, так как на каждом шаге мы добавляем одну вершину, и должны просматривать число ребер, линейно зависящее от размера графа. Выгодно храниться все ребра исходящие из reached в виде бинарного дерева, - тогда легко можно найти самое дешевое.

В случае если требуется найти все кратчайшие пути для каждой пары вершин можно применить алгоритм Флойда. Это выгоднее n-кратного применения алгоритма Дейкстры (для каждого возможного начала), если граф хранится в виде матрицы смежности.

← →
TUser © (2005-09-29 15:02) [7]

> Аналоговый способ: карта выполняется из стекла, все дороги представляют собой каналы заполненные к примеру аргоном. В точках A и B прикладывается напряжение. По идее короткий путь должен высветится.

Это метод Форда-Фалкертона. Из пушки по воробьям.

← →
Некто © (2005-09-29 15:21) [8]

жаль что я забыл это за практической невостребованностью таких знаний, а то бы подсказал =(

← →
Sandman29 (2005-09-29 15:48) [9]

Двунаправленный поиск в ширину.

← →
Внук © (2005-09-29 15:51) [10]

Это называется "Нахождение кратчайшего пути на графе". Изучается в дисциплинах "Методы оптимизации" и "Исследование операций".

← →
nk © (2005-09-29 16:04) [11]

... "задача комивояжера" ? ))

← →
Desdechado © (2005-09-29 17:22) [12]

nk
Нет, это принципиально разные задачи. Комивояжер должен вернуться в исходную, побывав во всех вершинах не более одногораза.

автору
Внук верно сказал. В любом учебнике по теме есть несколько точных методов и много приближенных.

Яндекс по "алгоритм поиска оптимального пути" нашел 7094 ссылки...
Почитай все и будет тебе счастье!

← →
vrem (2005-09-29 18:30) [14]

А если расстояние меньше, а дорога хуже? или пробки чаще или гаишники злее :) и всё это меняется от времени?. короче с "ценой пути" сложно, а так графы или "транспортная задача о покупках" или как - заданы цены разных предприятий на продукцию разных видов, есть набор покупок, который нужно купить, вопрос у какого предприятия и какой вид продукции купить

Бред все это.
Или физика стала математикой ?

> с учетом степени сложности дорог между точками

расстояние умножаешь на коефициет сложности

Волновой алгоритм поиска пути
Достоинствa - простотa, нaдёжность, 100% сaмый короткий путь (для клaссического методa). Hедостaтки - большой объём требуемой пaмяти и не сaмaя высокaя скорость нaхождения пути. В "HЛО-2", при перечисленных выше условиях, нaхождение пути может достигaть по времени до 1/10 секунды. Это, конечно, приемлимо для пошаговых стрaтегий и логических игрушек, но с трудом подойдёт для динaмических игр. A про попытку реaлизaции нa Бейсике я вообще молчу (рaзве в кaчестве примерa).

http://cs.mipt.ru/docs/comp/rus/programming/algorithms/tree_station/vpoisk.htm

Киньте в меня алгоритмами выбора оптимального пути из А в Б. Найти похожие ветки