Поиск кратчайшего пути

 Msg  : 1653 из 3561
 From : Alexey Gorshenev                       2:5011/211.5     Чтв 24 Авг 00 23:33 
 To   : Ivan  Kryak                                             Птн 25 Авг 00  13:26 
 Subj : Maze 

                     Здpавствyйте, Ivan  Kryak! 

23 Aug 00 13:54, Ivan  Kryak wrote to All: 

 IK> Поделитесь алгоpитмом  задачи о лабиpинте. Есть  каpта-2-меpный массив, 
 IK> надо найти кpатчайший  пyть из одной клетки в  дpyгyю, если pазpешены 
 IK> ходы по веpтикали,  гоpизонтали и диагоналям. Алгоpитм  желательно на 
 IK> Pas'е, но можно  на C++. 

Я знаю два способа решения  такой задачи. 
1. Реккурсивный. Из начальной  клетки идем в пустые соседние.  Далее из соседних  
клеток идем в соседние  соседних и т.д. Как только  дошли до нужной клетки 
проверяем длину пути. Если  меньше минимального, то запоминаем  новый путь. 
Конечно же надо сделать  отсечение путей, больших текущего  найденного 
минимального. Если перебрали  все варианты путей, а до  искомой клетки не дошли,  
то его (пути) не существует. 
2. Hе реккурсивный. Пусть  в матрице 1-стена,0-пусто. Ставим  в начальной точке 
число 2. Далее просматриваем  весь массив. Если встречаем  пустую клетку, у 
которой соседняя клетка равна  2, то ставим в эту клетку  число 3. Затем ещё раз  
просматриваем, но уже ищем  3, а ставим 4. Это продолжается  до тех пор, пока не  
поставим число в клетку  конца пути. Если за просмотр  не сделано ни одного 
изменения, то значит пути  не существует.В полученной матрице  получить все 
кратчайшие пути - элементарно. 
Каким лучше пользоваться -  зависит от данных. Если нужны  реализации алгоритмов  
на Пасе, мыль. 

                                              До встpечи, Ivan. 

--- GoldED/W32 3.0.1 
 * Origin: Russia, Sterlitamak,  Copyright ALCOM 2000 (2:5011/211.5) 

1.

72K

24 мая 2011 года

sfok3

1 / / 24.05.2011

11 июня 2011, 03:44:05

а как же "Алгоритм поиска пути A star"?

2.

19K

12 июня 2006 года

Taras55

0 / / 12.06.2006

12 июня 2006, 23:50:59

карта - M*N, длина искомого пути - L,
тогда сложность первого (в лучшей реализации) = O(M*N)
второго = O(M*N*L)
но если во втором не пробегать каждый раз весь масив, а хранить список новых клеток, то сложность резко упадет до = O(Min(L^2,M*N)), что при маленьких путях выигрывет у всех с большым отрывом, а при большых сравнимо с первым.

3.

Аноним

4 ноября 2005, 19:21:13

Да, забыл. В одном из конкурсов Хакера, надо было найти кратчайший путь, прога была написана на языке СИ.
Всем удачи 8-)

4.

Аноним

4 ноября 2005, 19:18:36

Не плохо ...

5.

Аноним

+2 / -0

9 июля 2004, 13:18:11

пошли мне реализацию на visual basic

сейчас пошли , иначе мне кранты.