Factorials

[whitefox]

1    240    Wes Sampson    La Jolla, California, United States    1 May 2013 14:11
2    243    Jarek Wroblewski    Wroclaw, Poland    1 May 2013 20:06

Страсти накаляются

[Nataly-Mak]

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

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

Всё, я тушу свет и ухожу спать
Какие ещё делители, если я не использовала вообще никакие эвристики по делителям (первоначально)?!!!
Только в последний момент провела эксперимент, чтобы получить время работы с этой эвристикой и сравнить его с вашим временем.

(Оффтоп)

Если ... очень сильно упорствует, не старайся его переупорствовать, сам козлёночком станешь
Спокойной ночи!

[whitefox]

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

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

Вот здесь-то делители и выскочили
Не зависимо от Вашего желания, программа выполнила это автоматически.

[Nataly-Mak]

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

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

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

Вот здесь-то делители и выскочили
Не зависимо от Вашего желания, программа выполнила это автоматически.

Вы издеваетесь, да?
Они выскочили потому, что я включила эвристику Non-Factor.
Когда я её не включала (при первом запуске этого поиска), никакие делители у меня не выскакивали. И программа работала медленнее, но она нашла эти же три решения!!!

С делителями или без делителей --- мне это абсолютно безразлично, так как я не включала это ограничение вообще нигде, ни на одном этапе поиска.

Это вы в самом начале заявили, что вот в этом примере не обойтись без эвристики Non-Factor. Я это ваше заявление полностью опровергла, обошлась вообще безо всяких эвристик.
Вы продолжаете упорстововать. Ладно. Я ставлю точку.

Да, важное замечание: включение любой эвристики чревато потерей решений.
Поэтому лучше обходиться без эвристик, так больше шансов найти решение, если оно существует.

[mertz]

You can prune by number being searched AND/OR a number you supply. Number you supply is 256-bit ( up to 57! ). The shorthand 12! will only work up to 37! The modulus of a 256-bit number takes some time. You can see the chain search pruning actually ran longer than the non-pruning.

326876 normal search, no pruning                         187 solutions, 20s
326876 normal search, non-factor of 28! pruning   87 solutions, 19s
326876 chain search, no pruning                            73 solutions, 2s
326876 chain search, non-factor of 28! pruning      17 solutions, 3s

Same links as before.

[Gerbicz]

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

1    240    Wes Sampson    La Jolla, California, United States    1 May 2013 14:11
2    243    Jarek Wroblewski    Wroclaw, Poland    1 May 2013 20:06

Страсти накаляются

cheetah (Acinonyx jubatus)

[whitefox]

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

Это вы в самом начале заявили, что вот в этом примере не обойтись без эвристики Non-Factor. Я это ваше заявление полностью опровергла, обошлась вообще безо всяких эвристик.

Это ложный посыл.
Такого заявления я не делал.
Вот моё подлинное заявление:

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

Но эвристика чётных чисел его не найдёт, так как в решение присутствует число 899.

Так, что Вы зря ломаете копья.
Я ведь с Вами согласен, в данном примере можно обойтись без эвристик.
Что я и сделал, и даже картинку привёл.

Это был всего лишь эксперимент в котором исследовался вопрос -- насколько может быть эффективной эвристика делителей N!
Естественно, что эксперимент проводился на примере, на котором можно получить решение без эвристики за приемлемое время.
Затем он был повторён, но уже с эвристикой.

-- 02 май 2013, 07:39 --

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

Да, важное замечание: включение любой эвристики чревато потерей решений.
Поэтому лучше обходиться без эвристик, так больше шансов найти решение, если оно существует.

С этим я тоже не спорю.

Просто заметил, что в случае 36! эвристика чётных чисел оптимальное решение не найдёт, а эвристика делителей -- найдёт и сделает это существенно быстрее чем без этой эвристики.

Жаль, что мои слова Вы поняли превратно.

-- 02 май 2013, 07:43 --

mertz
Большое спасибо
Сейчас поэкспериментирую с новой программой.

-- 02 май 2013, 07:54 --

(Gerbicz)

Гепард тоже спринтер, как и Вы

WikipediA писал(а):

The cheetah can run faster than any other land animal— as fast as 112 to 120 km/h (70 to 75 mph) in short bursts covering distances up to 500 m (1,600 ft), and has the ability to accelerate from 0 to over 100 km/h (62 mph) in five seconds.

http://en.wikipedia.org/wiki/Cheetah

[whitefox]

Эксперимент не удался

[Nataly-Mak]

mertz в сообщении #718553 писал(а):

326876 normal search, no pruning                         187 solutions, 20s
326876 normal search, non-factor of 28! pruning   87 solutions, 19s
...

Ускорение поиска на 1 секунду, с использованием non-factor of 28!, и... 100 потерянных последовательностей, среди которых могут быть последовательности, дающие решения.

-- Чт май 02, 2013 09:12:59 --

mertz в сообщении #718553 писал(а):

...
326876 chain search, no pruning                            73 solutions, 2s
326876 chain search, non-factor of 28! pruning      17 solutions, 3s

Замедление поиска на 1 секунду, с использованием non-factor of 28!, и... 56 потерянных последовательностей, среди которых могут быть последовательности, дающие решения.

-- Чт май 02, 2013 09:28:16 --

Вот уже и 230 шагов совсем близко

Цитата:

1 237 Wes Sampson La Jolla, California, United States 2 May 2013 04:14

[whitefox]

Что-то не так с реализацией новой фичи.




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

-- 02 май 2013, 10:04 --

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

Ускорение поиска на 1 секунду, с использованием non-factor of 28!, и... 100 потерянных последовательностей, среди которых могут быть последовательности, дающие решения.

Увы, ускорение не существенно.
Среди 100 обрезанных ветвей действительно могут быть последовательности дающие решение, а могут и не быть.
Зато среди 87 оставшихся такая последовательность заведомо существует.

[Nataly-Mak]

Работаю по предыдущей версии программы --- от 1 мая (обрезка non-factor есть, но реализована не корректно, по утверждению whitefox).

Эксперимент

Поиск начальных последовательностей для числа 6652800 в 10 шагов;
ставлю галочку в "non-factor".
Программа работает меньше одной минуты, найдено 557 последовательностей
[напомню: без использования эвристики последовательностей было найдено 924, время работы программы - 23 мин. 20 сек. Да, ускорение значительное, но! 367 потерянных последовательностей, среди которых могут быть последовательности, дающие решение].

Второй этап. Ищу от найденных 557 последовательностей число 39970374732288000, добавляя к последовательности 4 шага. Снова ставлю галочку в "non-factor"
Программа работала 1 мин. 26 сек. Найдены всё те же три решения, которые были найдены безо всяких эвристик.

Таким образом, не корректно реализованная эвристика нормально сработала.
"Повезло" - говорит whitefox

Вот то-то и оно, что повезло: потерянные последовательности с не-делителями не сказались пагубно на поиске окончательного решения.

А в случае, когда эвристика не была использована, были найдены все начальные последовательности и "везение" уже не требовалось.

[whitefox]

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

Вот то-то и оно, что повезло: потерянные последовательности с не-делителями не сказались пагубно на поиске окончательного решения.

А в случае, когда эвристика не была использована, были найдены все начальные последовательности и "везение" уже не требовалось.

Раньше Вы были ярой противницей брутфорса

[Nataly-Mak]

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

Среди 100 обрезанных ветвей действительно могут быть последовательности дающие решение, а могут и не быть.
Зато среди 87 оставшихся такая последовательность заведомо существует.

Это уже интересно.
А откуда априори известно, что если последовательности строить только из делителей N!, то для любого разложения (на основе которого строится решение) будет существовать оптимальное решение?

Это доказанный факт

-- Чт май 02, 2013 10:32:26 --

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

Раньше Вы были ярой противницей брутфорса

Не поняла. Переведите, пожалуйста, на русский язык.
...противницей чего?

[whitefox]

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

Это уже интересно.
А откуда априори известно, что если последовательности строить только из делителей N!, то для любого разложения (на основе которого строится решение) будет существовать оптимальное решение?

Это доказанный факт

Нет, это всего-лишь экспериментальный факт.

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

Не поняла. Переведите, пожалуйста, на русский язык.

ВикипедиЯ писал(а):

Полный перебор (или метод «грубой силы», англ. brute force) — метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.

http://ru.wikipedia.org/wiki/%CF%EE%EB%ED%FB%E9_%EF%E5%F0%E5%E1%EE%F0

[Nataly-Mak]

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

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

Это уже интересно.
А откуда априори известно, что если последовательности строить только из делителей N!, то для любого разложения (на основе которого строится решение) будет существовать оптимальное решение?

Это доказанный факт

Нет, это всего-лишь экспериментальный факт.

Тогда почему же вы пишете: "заведомо существует"?

По поводу методов решения задач и полного перебора...
Есть полный тупой перебор, который на много лет. Есть полный тупой перебор, который является неизбежностью, и даже если он занимал у меня несколько суток, я его делала (пример: поиск диагональных раскрасок для C=5; вы это забыли? Почему я в этом случае не была противницей полного перебора? Потому что в данном случае решить задачу другими методами невозможно и полный перебор - неизбежность).
Далее, есть полный перебор, который незначительно проигрывает по времени перебору с отсечением вариантов, но зато гарантирует, что мы не потеряем решения при отсечении (это как раз пример с поиском начальных последовательностей для решения 36! и других оптимальных решений).
Есть, наконец, оптимизации полного перебора, которые гарантируют, что мы не потеряем решение.

Видите, сколько нюансов у полного перебора. Я на этом переборе собаку съела, работая с магическими квадратами. И до сих пор работаю, сейчас уже с антимагическими квадратами Стенли (которые самым тесным образом связаны с магическими квадратами).
И передо мной стоит сейчас задача, которую решить мне, наверное, не хватит жизни. Но... всё равно я её решаю. Посмотрите тему "Антимагические квадраты".

Проверку наименьшего пандиагонального квадрата 6-го порядка из чисел Смита я выполняла несколько месяцев. И ничего другого тут сделать было невозможно.
И при этом вы называете меня противницей полного перебора.
Несколько странно это слышать.