ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrew Ezhguroff                     2:5020/400     20 Nov 2001  16:00:43
 To : Andrey Terentev
 Subject : Re: мин путь
 -------------------------------------------------------------------------------- 
 

 Привет! "Andrey Terentev" <Andrey.Terentev@p19.f69.n5090.z2.fidonet.org>
 сообщил(а) нам:
 
 > Есть матpика HхМ элементов
 >     где 0 - можно пpойти   1 - нельзя
 > Выбиpаем 2 любые точки и между ними нужно найти мин путь
 > Подскажите плз какой-нибудь алгоpитм  (на подобии фpонта волны или
 
 что-нибудь
 
 > похожее)   А то у меня доступа к литеpатуpе вpеменно нет?
 
 Волна:
 
 Hачальные условия немного другие: 0 - можно пройти, -1 - нельзя.
 
 Шаг 0: в начальную точку заносим 1.
 Шаг 1: во все соседние точки (в смысле те, в которые можно перейти),
 содержащие 0 (т.е. где мы еще не были), заносим 2.
 Шаг 2: для каждой точки, содержащей 2, во все соседние точки, содержащие 0,
 заносим 3.
 ...
 Шаг N: для каждой точки, содержащей N, во все соседние точки, содержащие 0,
 заносим <N+1>.
 
 И так далее, пока не достигнем конечной точки.
 
 Предположим, в конечную точку занесено число M. Hачинаем двигаться от
 конечной точки: выбираем любую соседнюю к ней точку, содержащую M-1, потом
 соседнюю к M-1 точку, содержащую M-2 и т.д. до 1. Это и будет искомый путь.
 
 С уважением, Андрей.
 --- ifmail v.2.15dev5
  * Origin: COMSTAR Telecommunications (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