|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Dashkovsky 2:5002/46.4 07 Nov 2002 11:00:29
To : Oleg Khovayko
Subject : Вот вам и кyбик.. .
--------------------------------------------------------------------------------
06 Hоя 02 11:56, you wrote to Andrew Ezhguroff:
>> Тем более, что требовалось не найти путь, а
>> определить его наличие.
OK> Одно другому не мешает. Мой рекурсивный алгоритм может и путь
OK> при желании выдать - на возвратах из успешной рекурсии.
OK> Другое дело, что этот путь будет абы-каким и явно не кратчайшим.
OK> А вот действительно, если бы надо было найти именно
OK> кратчайший путь - тогда только волна.
>>
>> OIK> Да еще очередь
>> OIK> должна быть не простая, а состоящая из кортеджей типа { x, y,
>> OIK> cube_status }.
>>
>> Гоним, например, "объемную" волну в трехмерном массиве N*M*6.
OK> Hу дык и я о том же!!!
OK> Hо чтобы гнать волну - очередь иметь надобно! О чем я и писал выше.
OK> Иначе для каждого шага волны придется весь массив N*M*6
OK> перелопачивать, как это обьяснил Андрей Дашковский
OK> в своем описании волнового алгоритма.
OK> Он хорошо обьяснил общую идею и принцип действия алгоритма,
OK> но никак не практический способ реального написания более-менее
OK> эффективной программы.
OK> Если сделать именно так как он описал - получится жутко медленная
OK> и неэффективная реализация.
OK> А правильная реализация волнового алгоритма делается именно через
OK> очередь. Тогда для каждого шага волны перелопачивается не вся
OK> матрица, а только ее элементы, составляющие фронт волны.
OK> Именно это я и имел ввиду ранее, когда писал, что для волны
OK> очередь нужна.
Только очередь надо грамотную, т.е. например бинарное дерево, или как минимум
какойнь-дь быстрый поиск реальзовать, а то на добавлении в очередь будут
тормоза.
Andrey
... Туалет занят. Там Пpезидент мочится с теppоpисиами.
--- GoldED+/386 1.1.4.7
* Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
