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

From

Viktor Karev (2:5080/1003)

To

akrivosheev@utc.ru

Date

2002-10-14T12:28:56Z

Area

RU.ALGORITHMS

From: Viktor Karev <termar@narod.ru>
Reply-To: termar@narod.ru

Приветствия!

akrivosheev@utc.ru wrote:
> > Испытания показали:
> > Рекурсивный алгоритм.
> Вы считаете это недостатком?

Вообще-то, нет. Но в данном случае рекурсия сделана "в лоб",
поэтому не очень эффективна.
Поясню на примере: Если программа нашла премлемое решение в
районе 20го-30го столбцов, но неверно разместила блоки, скажем, в
10м столбце, то она возвращается к 10му и ищет решение для
20го-30го столбцов заново. В итоге, на такой задаче, как японский
кроссворд, классический рекурсивный алгоритм "поиска с возвратом"
неэффективен.

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

Большие - это до 30х30. 40 мин на пентиуме-2 - это слишком много.

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

См выше. При включенном выводе промежуточных результатов видно,
что решение на отдельных столбцах находится многократно, но потом
"забывается" и ищется снова.

> > Не анализируется конфигурация, а используется банальный перебор.
> 
> При решении по столбцам и строкам отдельно тоже используется перебор. Это
> только вначале можно несколько ячеек как-то заполнить, а потом идёт просто

Вот-вот. Вначале несколько ячеек можно заполнить. Но с учетом
этих ячеек можно заполнить еще несколько и т.д. А вот когда уже
нет никакой возможности явно выставить ячейки, тогда и нужно
делать перебор.

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

Подкинуть пример?

25
35
1 1 1 
3 1 1 3 
7 4 
1 2 6 
3 1 2 1 
3 1 1 2 
4 2 2 2 
1 2 8 4 
2 12 2 1 
2 13 1 
4 14 1 
1 18 3 
1 17 1 
2 8 9 1 
2 9 10 
1 10 9 1 
1 10 9 1 
11 11 
1 10 12 
1 4 4 1 13 
1 4 4 1 10 1
1 1 4 3 2 4 7
1 5 3 2 1 2 
5 4 2 1 3 
5 4 2 1 3 

1
1 1
3
1 2
4
2 
4 2 2 3 
3 2 1 3 
5 1 6 
3 2 7 
3 1 8 
6 9 
1 2 9 4 
1 17
2 17
4 14 2
19 2 1
1 13 4 
1 6 3 1 2
1 7 2 1
1 12 
1 14 
19 
5 16 
3 13 1
1 16 
1 2 14
5 9 2
3 1 8 1
5 1 5 
3 2 4 
3 
3 
1 1 
2 

Виктор.
--- ifmail v.2.15dev5
 * Origin: Urals State University for Railway Transport (2:5080/1003@fidonet)