|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Viktor Karev 2:5080/1003 14 Oct 2002 12:28:56
To : akrivosheev@utc.ru
Subject : Re: Японский кpоссвоpд. Алгоpитм. [1/3]
--------------------------------------------------------------------------------
Приветствия!
akrivosheev@utc.ru wrote:
> > Испытания показали:
> > Рекурсивный алгоритм.
> Вы считаете это недостатком?
Вообще-то, нет. Hо в данном случае рекурсия сделана "в лоб",
поэтому не очень эффективна.
Поясню на примере: Если программа нашла премлемое решение в
районе 20го-30го столбцов, но неверно разместила блоки, скажем, в
10м столбце, то она возвращается к 10му и ищет решение для
20го-30го столбцов заново. В итоге, на такой задаче, как японский
кроссворд, классический рекурсивный алгоритм "поиска с возвратом"
неэффективен.
> > Hа больших задачах бывают очень большие
> > задержки.
> А на очень больших - очень большие задержки :)))
Большие - это до 30х30. 40 мин на пентиуме-2 - это слишком много.
> > При откате не учитываются предыдущие результаты.
> А предыдущие результаты просто не нужны - решение получится только когда
> перебор дойдёт до последней клетки (если дойдёт).
См выше. При включенном выводе промежуточных результатов видно,
что решение на отдельных столбцах находится многократно, но потом
"забывается" и ищется снова.
> > Hе анализируется конфигурация, а используется банальный перебор.
>
> При решении по столбцам и строкам отдельно тоже используется перебор. Это
> только вначале можно несколько ячеек как-то заполнить, а потом идёт просто
Вот-вот. Вначале несколько ячеек можно заполнить. Hо с учетом
этих ячеек можно заполнить еще несколько и т.д. А вот когда уже
нет никакой возможности явно выставить ячейки, тогда и нужно
делать перебор.
> перебор. Это будет уже не банальный перебор? Если внимательно посмотреть
> приведённый мною алгоритм, то можно заметить,что на каждом шаге анализируется
> конфигурация для текущёго столбца и строки. Кроме того алгоритм приведён в
> "чистом виде", т.е. в него можно добавить и начальный анализ клеток и прочие
> элементы оптимизации.
> И наконец последний аргумент: алгоритм быстро сходится - быстродействие на
> порядки быстре метода решения по столбцам и строкам (я сравнивал на одной и
> той же задаче) - именно это я и хотел показать.
Подкинуть пример?
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
