Re: Японский кpоссвоpд. Алгоpитм. [1/3]

From

akrivosheev@utc.ru ()

To

Viktor Karev

Date

2002-10-14T07:19:52Z

Area

RU.ALGORITHMS

From: akrivosheev@utc.ru

> Испытания показали:
> Рекурсивный алгоритм.

Вы считаете это недостатком?

> На больших задачах бывают очень большие
> задержки.

А на очень больших - очень большие задержки :)))

> При откате не учитываются предыдущие результаты.

А предыдущие результаты просто не нужны - решение получится только когда
перебор дойдёт до последней клетки (если дойдёт).

> Не анализируется конфигурация, а используется банальный перебор.

При решении по столбцам и строкам отдельно тоже используется перебор. Это
только вначале можно несколько ячеек как-то заполнить, а потом идёт просто
перебор. Это будет уже не банальный перебор? Если внимательно посмотреть
приведённый мною алгоритм, то можно заметить,что на каждом шаге анализируется
конфигурация для текущёго столбца и строки. Кроме того алгоритм приведён в
"чистом виде", т.е. в него можно добавить и начальный анализ клеток и прочие
элементы оптимизации.
И наконец последний аргумент: алгоритм быстро сходится - быстродействие на
порядки быстре метода решения по столбцам и строкам (я сравнивал на одной и
той же задаче) - именно это я и хотел показать.


--- ifmail v.2.15dev5
 * Origin: JV Izhcom Ltd. (2:5020/400)