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

From

Andrey Dashkovsky (2:5002/46.4)

To

Oleg Khovayko

Date

2002-11-07T10:00:29Z

Area

RU.ALGORITHMS

Hello Oleg.

06 Ноя 02 11:56, you wrote to Andrew Ezhguroff:

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

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

 OK> Ну дык и я о том же!!!
 OK> Но чтобы гнать волну - очередь иметь надобно! О чем я и писал выше.
 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)