Re^2: Обход доски шахматным конем

From

Vitaly Slobodskoy (2:5015/128.22)

To

"Dmitriy K."

Date

2002-07-23T22:08:51Z

Area

RU.ALGORITHMS

Так ВЫ, //Dmitriy K //, 22.07.2002 изволили //флиртовать// с //Roman Zhelnov//, заводя разговор о *"Re: Обход доски шахматным конем"*?? Так я тут _подумал_ немножко и решил напомнить вам, что...

 U> Естественно, можно оптимизировать. Например, конь сделает только 64 хода,
 U> так что можно избежать рекурсии, а сделать итерацию; посмотреть, как он
 U> обходит и т.д.
 Аналог этого алгоритма без рекурсии (чистая итерация) - алгоритм возвратом, но
там нужно хранить историю пути, что в рекурсии происходит "само собой" :))

 U> Еще можно использовать факт симметрии доски и ходов - например, за один
 U> шаг рекурсии делать не один шаг конем а все восемь в доступных
 U> направлениях.
 Кол-во клеток шахматной доски в ширину - 8 - чётное число => о симметрии
забудь! А моделирование за один шаг сразу 8-и ходов у тебя не получится -
подумай, какое это деревце и сколько там нужно лишней памяти!! А если размеры
доски увеличить??

Всего хорошего ..

Slobodskoy Vitaly
e-mail: vital@mail.nnov.ru
fido: 2:5015/128.22

--- WP/95 Rel 1.78E (215.0) Reg.
 * Origin: Делай FORMAT и спи спокойно! (2:5015/128.22)