Неархитектурная задачка

[Губанов Сергей Юрьевич]

Изменил алгоритм. Что сделал - военная тайна  (правда исходник прилагаю).

Стало 0.047 секунды на весь in.txt.

Фактически это уже похоже на время ввода-вывода.

Кстати, всего 248K рекурсивных вызовов.

[Губанов Сергей Юрьевич]

Стало 0.047 секунды на весь in.txt.

Фактически это уже похоже на время ввода-вывода.

На вычисления расходуется 0.022 секунды, и 0.025 секунды уходят на ввод-вывод.

[albobin]

накропал на МАМПСе (MUMPS)
чтение и запись в файл
где то 0.01-0.04 сек
на Пентиуме Д 3Ггц  512М

[valexey]

накропал на МАМПСе (MUMPS)
чтение и запись в файл
где то 0.01-0.04 сек
на Пентиуме Д 3Ггц  512М

Афигеть.

[albobin]

не совсем афигеть.
это на исходной задаче.
а на файле in.txt не всё ok 
0.39 сек ,  но некоторые не решаются (пока), надо кумекать.
А алгоритм без перебора и рекурсий.(пока)

[vlad]

А раз лучше все равно не стало выдал "военную тайну" самого быстрого алгоритма 

Военной тайны не получилось - у меня такое же улучшение было сделано. Предварительная сортировка по количеству возможных вариантов.

[vlad]

На вычисления расходуется 0.022 секунды, и 0.025 секунды уходят на ввод-вывод.

Да, похоже на предел Новые варианты имеет смысл генерить?

[Губанов Сергей Юрьевич]

Новые варианты имеет смысл генерить?

Наверное нет.

[valexey]

Новые варианты имеет смысл генерить?

Наверное нет.

А мне кажется, что да. Потому как начальные условия сильно могут различаться по сложности.

[Илья Ермаков]

А я решил с обычного обхода дерева делать - и поскольку время меня устроило - никаких эвристик вводить не стал

[valexey]

А я решил с обычного обхода дерева делать - и поскольку время меня устроило - никаких эвристик вводить не стал

Гм. Я сильно сомневаюсь что на всех возможных (даже корректных, то есть у которых ровно одно решение) начальных условиях такое решение будет работать меньше секунды.

[Губанов Сергей Юрьевич]

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

В дереве поиска следующий шаг рекурсии делать в ветви с наименьшим количеством подветвей.

Эвристика а-ля "жадный алгоритм".

Такой алгоритм фатально обломится если правильный ответ каждый раз (на каждом шаге рекурсии) будет находиться в ветви с наибольшим количеством подветвей, правда такие случаи встречаются редко.

[Илья Ермаков]

Гм. Я сильно сомневаюсь что на всех возможных (даже корректных, то есть у которых ровно одно решение) начальных условиях такое решение будет работать меньше секунды.

Ну дык я и приводил время - 2с.
Для NP-полной задачи чем плохо, если учесть, что решал я раньше, чем все остальные участники, кроме Влада?

[valexey]

Гм. Я сильно сомневаюсь что на всех возможных (даже корректных, то есть у которых ровно одно решение) начальных условиях такое решение будет работать меньше секунды.

Ну дык я и приводил время - 2с.
Для NP-полной задачи чем плохо, если учесть, что решал я раньше, чем все остальные участники, кроме Влада?

В текущей постановке задача решается за O(1) :-) Но это мелочи.

Я к тому, что в случае разных начальных условий за 2 секунды ты вполне можешь вылезти. Ты пробовал свое решение погонять на других начальных условиях? Ну, например на том пакете из 12ти задач.

[Илья Ермаков]

Понятно дело, что могу вылезти..
Вот попробовал:

 2215 msec
 847 msec
 2735 msec
 3456 msec
 9265 msec
 681 msec
 19656 msec
...

Ну, у меня программа нерекурсивная (откат выполняется прямо на рабочем поле), поэтому к нему уже никакой эвристики не прикрутишь