Factorials

[Nataly-Mak]

whitefox в сообщении #718444 писал(а):

Интересно ещё то, что оптимальное решение для 6652800 имеет 9 шагов.
Но при построении решения 36! используется решение для 6652800 из 11 шагов, на 2 шага больше оптимального.

Ну, это уже не удивительно.
Число 4200 имеет оптимальное решение в 7 шагов; однако в построении решения для 22! используются решения для числа 4200 в 9 шагов, на 2 шага больше оптимального.

-- Ср май 01, 2013 22:53:43 --

whitefox в сообщении #718462 писал(а):

Nataly-Mak в сообщении #718459 писал(а):

А почему нельзя использовать, например, такое решение в 10 шагов:

Число 6652800 нужно не само по себе, а как часть решения для 36!

Это мне понятно

Цитата:

Кстати Ваша последовательность тоже отвечает эвристике делителей.

Она не моя, она ваша; просто я выбросила из неё не нужное число 899, которое в составлении числа 6652800 совсем не участвует.
Если я буду строить все решения в 10 шагов, в них будут все решения: и отвечающие, и не отвечающее эвристике делителей.

[whitefox]

Nataly-Mak в сообщении #718465 писал(а):

Ну, это уже не удивительно.
Число 4200 имеет оптимальное решение в 7 шагов; однако в построении решения для 22! используются решения для числа 4200 в 9 шагов, на 2 шага больше оптимального.

Вы правы.
Вспомнил об этом когда уже написал сообщение, но исправлять не стал.

-- 01 май 2013, 23:08 --

Nataly-Mak в сообщении #718465 писал(а):

Если я буду строить все решения в 10 шагов, в них будут все решения: и отвечающие, и не отвечающее эвристике делителей.

Проверено, всех решений менее тысячи.
Но ни одно из них не продолжается до решения 39970374732288000 в 13 шагов. Решение в 14 шагов существует (приведено выше), но чтобы получить его нужно исходную последовательность расширить на 4 шага.

[Nataly-Mak]

Я тоже проверила.
Решений в 10 шагов для числа 6652800 безо всяких эвристик найдено 924
(мой тихоход справился с этой задачей за 23 мин. 20 сек.; работала самая последняя версия программы mertz.)

Цитата:

Но ни одно из них не продолжается до решения 39970374732288000 в 13 шагов. Решение в 14 шагов существует (приведено выше), но чтобы получить его нужно исходную последовательность расширить на 4 шага.

Не поняла. Так всё-таки решение можно найти от всех начальных последовательностей в 10 шагов?
Я думаю, что можно, так как выброшенное число 899 - оно же легко порождается решением в 10 шагов. Какая разница --- было ли это число до числа 6652800 или оно будет после него?
У вас следующий этап вот эта последовательность:

1, 2, 4, 6, 36, 35, 216, 220, 864, 899, 30240, 6652800, 6683040, 44460928512000, 39970374732288000

Ну и что? Разве от всех решений в 10 шагов нельзя найти число 39970374732288000 за 4 шага? Уверена, что можно.
Просто от вашей последовательности это число составляется за 3 шага, но у вас и последовательность на 1 шаг длиннее моих последовательностей.
У меня решение будет выглядеть, например, так:

1, 2, 4, 6, 36, 35, 216, 220, 864, 30240, 6652800, 899, 6683040, 44460928512000, 39970374732288000

[whitefox]

Сейчас программа Эда ищет расширение на 4 шага для 39970374732288000 от всех 10-шаговых последовательностей для 6652800.
За 36 минут выполнено 80% работы, найдено 3 решения:

found 3 solutions for 39970374732288000 in 14 steps
1,2,4,6,36,35,216,220,864,30240,6652800,899,6683040,44460928512000,39970374732288000
1,2,4,6,36,35,216,220,864,30240,6652800,899,6683040,5980867200,39970374732288000
1,2,4,6,36,35,216,220,864,30240,6652800,899,6683040,6008052960,39970374732288000

[Nataly-Mak]

Ага, и у меня ищет
Так мы с вами после конкурса найдём все оптимальные решения

Ну вот, как я и сказала, решения есть, и не могло не быть.
Зато искать решения в 10 шагов можно безо всяких эвристик, и на это уходят считанные минуты; у меня всего 23 минуты потребовалось. У вас будет ещё меньше, а у Эда вообще за секунды это выполнится.

found 3 solutions for 39970374732288000 in 14 steps
1,2,4,6,36,35,216,220,864,30240,6652800,899,6683040,44460928512000,39970374732288000

Вот и решение я угадала Прорицательница?

[whitefox]

[Nataly-Mak]

У вас слова кончились?
Прекрасно, я и картинки понимаю

Тэк-с, почти 44 минуты программа работала, найдено 3 решения.
Отличный результат эксперимента

Мне прервать что ли программу или пусть отработает до конца?
Сравним время работы.

А у меня программа работает 23 минуты, выполнено 7% и... три решения уже найдены!
Вот как быстро они найдены.
Ну, не буду зря мучить машину, прерву программу.
Вот три решения:

found 3 solutions for 39970374732288000 in 14 steps
1,2,4,6,36,35,216,220,864,30240,6652800,899,6683040,44460928512000,39970374732288000
1,2,4,6,36,35,216,220,864,30240,6652800,899,6683040,5980867200,39970374732288000
1,2,4,6,36,35,216,220,864,30240,6652800,899,6683040,6008052960,39970374732288000

[whitefox]

От трёх предыдущих последовательностей мгновенно получено:

found 1 solutions for 1398918654701568000 in 16 steps
1,2,4,6,36,35,216,220,864,30240,6652800,899,6683040,44460928512000,39970374732288000,1398963115630080000,1398918654701568000

[Nataly-Mak]

Ну и? Вывод какой? Нужна эвристика с делителями N!
И в этом примере прекрасно обошлись без неё, и даже без эвристики для чётных чисел.

[whitefox]

Эвристика для чётных чисел это решение не нашла бы, так как в нём присутствуют нечётные.

А эвристика делителей N! позволила бы существенно сократить время поиска.

[Nataly-Mak]

whitefox в сообщении #718511 писал(а):

Эвристика для чётных чисел это решение не нашла бы, так как в нём присутствуют нечётные.

Вот ёлки-палки!
Да не нужны вообще никакие эвристики при поиске решений в 10 шагов!
Эти решения без эвристик находятся за считанные минуты.

Цитата:

А эвристика делителей N! позволила бы существенно сократить время поиска.

А вот в этом нисколько не уверена.
Писала уже своё мнение на этот счёт. Ещё не факт, что эвристика позволит сократить время поиска.
Вот когда докажете это экспериментально, тогда соглашусь
Вот на этом примере и докажите.

Ещё раз повторю: пусть мы ищем решения для числа 6652800 в 10 шагов.
Включаем эвристику в вашем понимании, то есть в решениях не должно быть чисел, не являющихся делителями 36!
Я правильно ваше требование поняла?
Так значит, программа должна проверять все члены последовательностей на соответствие этому условию. На это надо время, между прочим.
Итак, решения для числа 6652800 в 10 шагов безо всяких эвристик мной найдены за 23 минуты (924 решения).
Где ваша программа, которая ищет решения с этой эвристикой? Давайте её мне.
Буду экспериментировать

Да, ещё немаловажно. В программе Эда решения строятся от базовых последовательностей, состоящих из 7 членов (6 шагов). Это должно быть соблюдено.

[whitefox]

-- 02 май 2013, 00:31 --

Ускорение в 37 раз.

[Nataly-Mak]

whitefox
но... ведь здесь проверяются не делители 36!, а делители числа 39970374732288000
(вроде Эд ещё не добавил ваше требование по этой эвристике ?)
Это не совсем одно и то же.

[whitefox]

Nataly-Mak в сообщении #718515 писал(а):

Так значит, программа должна проверять все члены последовательностей на соответствие этому условию. На это надо время, между прочим.

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

-- 02 май 2013, 00:45 --

Nataly-Mak в сообщении #718531 писал(а):

но... ведь здесь проверяются не делители 36!, а делители числа 39970374732288000
(вроде Эд ещё не добавил ваше требование по этой эвристике ?)
Это не совсем одно и то же.

Любой делитель числа 39970374732288000 является и делителем 36!

Здесь нам повезло, что числа 899, 6683040, 44460928512000 являются делителями 39970374732288000.
Иначе бы решение мы не получили.

Конечно число делителей 36! больше числа делителей 39970374732288000, но не думаю чтобы время обработки одного узла возрасло из-за этого очень сильно.

[Nataly-Mak]

whitefox в сообщении #718528 писал(а):

Ускорение в 37 раз.

Ну вот, можем и время сравнить, у меня с этой эвристикой программа отработала за 9 мин. 12 сек.

Теперь ещё раз и последний.
Это похоже на мышиную возню: мышка, у которой хвост обрезан, быстрее бегает и поворачивается, нежели мышка с длинным хвостом
Меня не устраивает сама концепция такого поиска.
Вот берём некоторое разложение (откуда мы его берём? какой-то добрый волшебник нам сделал все эти разложения ).
Так, берём разложение... и начинаем строить решения --- сначала для первого числа (в 7-10 шагов), потом для второго числа, потом для третьего числа.
Это очень примитивный поиск, как я уже писала. Много так не проверить.
Да, Эд сделал очень хорошую программу! Я это уже не раз отмечала.
Но это не решатель в полном смысле этого слова, это только инструмент, помогающий искать решения. Инструмент отличный, да. Отдадим должное Эду!

Так, в рассмотренном выше примере какая разница мне, нашлось ли решение за полчаса или оно нашлось за 5 минут? Абсолютно никакой разницы. Мне надо проделать ряд ручных процедур с автоматическим их исполнением, но не с автоматическим выполнением всего поиска в целом!
Эд пытался автоматизировать одну из парадигм:

$N! = A^2B$
Вроде это у него получилось, он прислал мне решение для 25!, найденное по этому алгоритму.
Больше никаких автоматизаций я не видела.

А wanderers, между прочим, писал именно об автоматизации поиска по парадигмам.
Правда, он не раскрыл свой способ автоматизации, только намекнул о построении таблиц.
Как раз такие таблицы строил и Эд при автоматизации поиска решений по приведённой выше парадигме (о чём я рассказала выше).