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

From

Oleg I. Khovayko ()

To

Andrey Dashkovsky

Date

2002-11-07T19:48:45Z

Area

RU.ALGORITHMS

From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov>

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

????????

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

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

Какие???

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



-- 
#include <best/regards.hpp>
Oleg I. KHOVAYKO  
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
 * Origin: National Center for Biotechnology Information (2:5020/400)