Алгоритм нахождения кратчайшего пути

oleg1966

Для ситуации примерно следующей.... (из "а" в "б")

при том, идти из одной точки можно по всем направлениям включая диагональные....

spiritmc

Построй граф и ищи так, как тебе нравится или умеешь:
прямым поиском (в ширину построить расстояния, потом найти путь...
---
...Я работаю...

oleg1966

немного не понял...
то есть, можно по действиям:
куда сделать первый шаг из А?, что делать, если он не один? куда соответственно идти дальше?

anutamakk

Есть волновой алгоритм, он же алгоритм Ли - модификация алгоритма Дейкстры, если ты имеешь достаточно памяти . Любая книжка по алгоритмам и гугль дадут кучу информации.

afony

Есть такой алгоритм:
1. Работаем с матрицой; каждой клеточке лабиринта соответствует элемент матрицы.
2. Во все пустые клетки, соседние с начальной, записываем 1.
3. На k-ом шаге во все пустые клетки, соседние с теми, в которых написано число k, записываем число k+1;
4. Пункт 3. повторять до тех пор, пока не будет записано какое-либо число в конечную клетку.
5. Число m, записанное в конечную клетку будет означать длину кратчайшего пути.
6. Чтобы восстановить кратчайший путь, проводим индукцию в обратном порядке, т.е. берем конечную клетку и находим соседнюю с ней с написанным номером m-1, далее ищем соседнюю уже для этой клетки с номером m-2, и т.д.
7. Пройденные при обратной индукции клетки и образуют искомый путь.
Это и есть волновой алгоритм, упомянутый выше.

oleg1966

ГЕНИАЛЬНО!
Спасибо! - рюхнул...
ЗЫ это просто гениально.... нет слов...
ЗЗЫ еще раз пасиба.

kliM

гениальный, но общеизвестный

oleg1966

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

afony

Не за что. Мне он тоже понравился, когда я впервые с ним столкнулся.

resident

это ж поиск в ширину

illegal

Один из самых лучших - алгоритм A*.
Посмотреть его и еще много дургих подходов можно здесь:
http://dev.dtf.ru/articles/read.php?id=50

naami_moloko

Неа, предложил частный случай реализации очень классного алгоритма, который называется волновой.
В частности, например, он используется и при распознавании образов - строится "горка" от начального объекта, накладывается шаблон и смотрится сумма пересечения(в кратце если)...

kliM

он используется и при распознавании образов

в частности мехматяниным Козловым ... не помню инициалы
Оставить комментарий
Имя или ник:
Комментарий: