|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Khovayko 2:5020/400 06 Nov 2002 12:56:53
To : Andrew Ezhguroff
Subject : Re: Вот вам и кyбик.. .
--------------------------------------------------------------------------------
Andrew Ezhguroff wrote:
> Тем более, что требовалось не найти путь, а
> определить его наличие.
Одно другому не мешает. Мой рекурсивный алгоритм может и путь
при желании выдать - на возвратах из успешной рекурсии.
Другое дело, что этот путь будет абы-каким и явно не кратчайшим.
А вот действительно, если бы надо было найти именно
кратчайший путь - тогда только волна.
>
> OIK> Да еще очередь
> OIK> должна быть не простая, а состоящая из кортеджей типа { x, y,
> OIK> cube_status }.
>
> Гоним, например, "объемную" волну в трехмерном массиве N*M*6.
Hу дык и я о том же!!!
Hо чтобы гнать волну - очередь иметь надобно! О чем я и писал выше.
Иначе для каждого шага волны придется весь массив N*M*6
перелопачивать, как это обьяснил Андрей Дашковский
в своем описании волнового алгоритма.
Он хорошо обьяснил общую идею и принцип действия алгоритма,
но никак не практический способ реального написания более-менее
эффективной программы.
Если сделать именно так как он описал - получится жутко медленная
и неэффективная реализация.
А правильная реализация волнового алгоритма делается именно через
очередь. Тогда для каждого шага волны перелопачивается не вся
матрица, а только ее элементы, составляющие фронт волны.
Именно это я и имел ввиду ранее, когда писал, что для волны
очередь нужна.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
