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

From

Oleg Khovayko ()

To

Andrew Ezhguroff

Date

2002-11-06T11:56:53Z

Area

RU.ALGORITHMS

From: Oleg Khovayko <olegh@hotpop.com>

Andrew Ezhguroff wrote:
 > Тем более, что требовалось не найти путь, а
> определить его наличие.

Одно другому не мешает. Мой рекурсивный алгоритм может и путь
при желании выдать - на возвратах из успешной рекурсии.
Другое дело, что этот путь будет абы-каким и явно не кратчайшим.
А вот действительно, если бы надо было найти именно
кратчайший путь - тогда только волна.
> 
>  OIK> Да еще очередь
>  OIK> должна быть не простая, а состоящая из кортеджей типа { x, y,
>  OIK> cube_status }.
> 
> Гоним, например, "объемную" волну в трехмерном массиве N*M*6.

Ну дык и я о том же!!!
Но чтобы гнать волну - очередь иметь надобно! О чем я и писал выше.
Иначе для каждого шага волны придется весь массив N*M*6
перелопачивать, как это обьяснил Андрей Дашковский
в своем описании волнового алгоритма.
Он хорошо обьяснил общую идею и принцип действия алгоритма,
но никак не практический способ реального написания более-менее
эффективной программы.
Если сделать именно так как он описал - получится жутко медленная
и неэффективная реализация.
А правильная реализация волнового алгоритма делается именно через
очередь. Тогда для каждого шага волны перелопачивается не вся
матрица, а только ее элементы, составляющие фронт волны.
Именно это я и имел ввиду ранее, когда писал, что для волны
очередь нужна.




--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)