ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Roman Ilyin                          2:5020/400     20 Nov 2001  17:23:46
 To : Andrey Terentev
 Subject : Re: мин путь
 -------------------------------------------------------------------------------- 
 

 Доброе время суток, Andrey.
 
 AT> Есть матpика HхМ элементов     где 0 - можно пpойти   1 - нельзя
  AT> Выбиpаем 2 любые точки и между ними нужно найти мин путь
  AT> Подскажите плз какой-нибудь алгоpитм  (на подобии фpонта волны или
  AT> что-нибудь похожее)   А то у меня доступа к литеpатуpе вpеменно нет?
 
 Ходить можно в 4 направлениях?
 тогда ставишь с 4 сторон (где это возможно) стрелочки
 (вверх/вниз/влево/вправо - кодируется минимум 2 битами),
 указывающие на твою стартовую точку.
 
 Дальше в цикле проходишь все поле и смотришь, где
 есть "стрелочки". Ставишь на соседних клетках стрелки
 чтобы они указывали на клетку со стрелкой.
 
 Так пока не окажется стрелка на конечной клетке
 (их может быть несколько) или пока не кончатся свободные клетки.
 Если при очередном проходе ни одной стрелки не поставленно,
 то значит идти больше некуда.
 
 Hазывается это волновым алгоритмом поиска
 
 Существует также куча более умных/быстрых и т.д. алгоритмов.
 Поищи A* и т.п.
 
 Также можно оптимизировать данный алгоритм для уменьшения
 числа поворотов.
 ====================================================
 Удачи! Роман Ильин grisper@voronezh.net
 --- ifmail v.2.15dev5
  * Origin: Информсвязь-Черноземье (2:5020/400)
 
 

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

Тема:    Автор:    Дата:    мин путь   Andrey Terentev   20 Nov 2001 00:26:09   Re: мин путь   Andrew Ezhguroff   20 Nov 2001 16:00:43   Re: мин путь   Roman Ilyin   20 Nov 2001 17:23:46