Вот вам и кyбик.. .

From

Andrey Dashkovsky (2:5002/46.4)

To

Oleg I. Khovayko

Date

2002-11-11T15:10:58Z

Area

RU.ALGORITHMS

Hello Oleg.

07 Ноя 02 19:48, you wrote to me:

 >> Только очередь надо грамотную, т.е. например бинарное дерево, или
 >> как минимум какойнь-дь быстрый поиск реальзовать,

 OK> ????????

 OK> Зачем!?!?!?
 OK> Я же говорил именно ОЧЕРЕДЬ, а не бинарное дерево!!!

 >> а то на добавлении в очередь будут
 >> тормоза.

 OK> Какие???

 OK> Очередь ведь неприоритетна! В конец вставин - из начала вынул.
 OK> И все. Линейный динамической список в памяти или кольцевой
 OK> буфер - вот тебе и вся очередь. И вставка, и удаление, делаются
 OK> ОЧЕНЬ быстро. И такой очереди вполне достаточно для реализации
 OK> классического волнового алгоритма.
 OK> А приоритетная очередь (типа дерева и тп) нужна только тогда,
 OK> когда ты хочешь гнать волну в пространстве с разной ценой
 OK> "шага на соседнюю клетку". Тогда действительно, волновой алгоритм
 OK> с приоритетной очередью будет тебе гарантировать, что клетка [i,j]
 OK> будет достигнута самым дешевым путем, а не самым коротким.
 OK> А если цена шага на соседнюю клетку всегда одинакова (как в
 OK> задаче с кубиком или с разводкой печатных плат), и самай дешевый
 OK> путь есть самый короткий, то все приоритеты
 OK> одинаковы, и очередь можно использовать бесприоритетную.

Просто я думал о исключении одинаковых вершин, дабы одну и ту же вершину по
несколько раз не обрабатывать, хотя я по времени не тестировал, может и без этих
наворотов нормально пройдёт.

Andrey

... Любишь кататься, люби и самочек возить!
--- GoldED+/386 1.1.4.7
 * Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)