|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 07 Nov 2002 20:48:45
To : Andrey Dashkovsky
Subject : Re: Вот вам и кyбик.. .
--------------------------------------------------------------------------------
Andrey Dashkovsky wrote:
>
>
> Только очередь надо грамотную, т.е. например бинарное дерево, или как минимум
> какойнь-дь быстрый поиск реальзовать,
????????
Зачем!?!?!?
Я же говорил именно ОЧЕРЕДЬ, а не бинарное дерево!!!
> а то на добавлении в очередь будут
> тормоза.
Какие???
Очередь ведь неприоритетна! В конец вставин - из начала вынул.
И все. Линейный динамической список в памяти или кольцевой
буфер - вот тебе и вся очередь. И вставка, и удаление, делаются
ОЧЕHЬ быстро. И такой очереди вполне достаточно для реализации
классического волнового алгоритма.
А приоритетная очередь (типа дерева и тп) нужна только тогда,
когда ты хочешь гнать волну в пространстве с разной ценой
"шага на соседнюю клетку". Тогда действительно, волновой алгоритм
с приоритетной очередью будет тебе гарантировать, что клетка [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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
