Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11642
Последний выпуск: 19.06.2015

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


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)

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 

Комментарии

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

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

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог