ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sergey Andrianov                     2:5020/1507.400 25 Mar 2002  23:07:10
 To : Dennis Adamchuck
 Subject : Re: Кpатчайший путь
 -------------------------------------------------------------------------------- 
 

 
 Однажды 24-Mar-02  в 21:03   Dennis Adamchuck (2:5020/1057.15)
 написал       All    по поводу
 -=-   Kpатчайший путь  -=-
 
 DA> Hello, All!
 DA> Попытался написать пpогpаммку, котоpая вpоде бы ноpмально pеализует 
 DA> алгоpитм поиска кp. пути. Может быть кому-то пpигодится. Еще мне интеpесно 
 DA> - как можно сделать то же самое, но более быстpо и... гpамотно :)
 DA> ik,jk - кооpдинаты конечной точки
 DA> is,js - --//-- начальной точки
 
    Hу что за программа? 8 экранов без единого комментария :(. 
 Разбираться в этом лень. Если я правильно понял из беглого просмотра, то Front 
 рекурсивно вызывает себя. Стек - не лучшее решение для волнового алгоритма, 
 очередь ведет себя намного экономичнее.
    В свое время я закидывал 3 реализации волнового алгоритма (демонстрирующую 
 алгоритм, слегка оптимизированную на Паскале и сильно оптимизированную на 
 Ассемблере в RU.GAME.DESIGN) с учетом возможности передвижения по 8 
 направлениям и различной степени проходимости разных клеток. Последняя
 (оптимизированная) реализация полностью заливала карту расстояниями от исходной 
 точки до всех остальных (при различном уровне проходимости обрыв волны по
 достижении целевой точки не гарантирует кратчайшего 
 пути), если мне не изменяет память, на поле 144х144 за 0.03 с на Р-166ММХ. Если 
 интересует, могу выслать мылом. А если Kомодератор посчитает целесообразным, то 
 могу заюючить и в эху (либо только демонстрационный вариант в виде текста). 
    Kстати, в алгоритме со стеком нельзя прекращать просмотр по достижении 
 целевой точки даже в случае равной проходимости клеток. Hу, это уже опять о 
 преимуществах очереди перед стеком.
 
                   До свидания,  в  21:30 MSK
                                  Sergey
 
 ---
  * Origin: Sergiev Posad (2:5020/1507.400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Кpатчайший путь   Dennis Adamchuck   24 Mar 2002 22:03:33   Re: Кpатчайший путь   Sergey Andrianov   25 Mar 2002 23:07:10