|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Dashkovsky 2:5002/46.4 11 Nov 2002 16:10:58
To : Oleg I. Khovayko
Subject : Вот вам и кyбик.. .
--------------------------------------------------------------------------------
07 Hоя 02 19:48, you wrote to me:
>> Только очередь надо грамотную, т.е. например бинарное дерево, или
>> как минимум какойнь-дь быстрый поиск реальзовать,
OK> ????????
OK> Зачем!?!?!?
OK> Я же говорил именно ОЧЕРЕДЬ, а не бинарное дерево!!!
>> а то на добавлении в очередь будут
>> тормоза.
OK> Какие???
OK> Очередь ведь неприоритетна! В конец вставин - из начала вынул.
OK> И все. Линейный динамической список в памяти или кольцевой
OK> буфер - вот тебе и вся очередь. И вставка, и удаление, делаются
OK> ОЧЕHЬ быстро. И такой очереди вполне достаточно для реализации
OK> классического волнового алгоритма.
OK> А приоритетная очередь (типа дерева и тп) нужна только тогда,
OK> когда ты хочешь гнать волну в пространстве с разной ценой
OK> "шага на соседнюю клетку". Тогда действительно, волновой алгоритм
OK> с приоритетной очередью будет тебе гарантировать, что клетка [i,j]
OK> будет достигнута самым дешевым путем, а не самым коротким.
OK> А если цена шага на соседнюю клетку всегда одинакова (как в
OK> задаче с кубиком или с разводкой печатных плат), и самай дешевый
OK> путь есть самый короткий, то все приоритеты
OK> одинаковы, и очередь можно использовать бесприоритетную.
Просто я думал о исключении одинаковых вершин, дабы одну и ту же вершину по
несколько раз не обрабатывать, хотя я по времени не тестировал, может и без этих
наворотов нормально пройдёт.
Andrey
... Любишь кататься, люби и самочек возить!
--- GoldED+/386 1.1.4.7
* Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
