2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 75, 76, 77, 78, 79, 80, 81 ... 88  След.
 
 Re: Factorials
Сообщение02.05.2013, 00:02 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Код:
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
Страсти накаляются :D

 Профиль  
                  
 
 Re: Factorials
Сообщение02.05.2013, 00:03 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #718538 писал(а):
Здесь нам повезло, что числа 899, 6683040, 44460928512000 являются делителями 39970374732288000.
Иначе бы решение мы не получили.

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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Factorials
Сообщение02.05.2013, 00:06 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #718547 писал(а):
Только в последний момент провела эксперимент, чтобы получить время работы с этой эвристикой и сравнить его с вашим временем.

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

 Профиль  
                  
 
 Re: Factorials
Сообщение02.05.2013, 00:13 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #718549 писал(а):
Nataly-Mak в сообщении #718547 писал(а):
Только в последний момент провела эксперимент, чтобы получить время работы с этой эвристикой и сравнить его с вашим временем.

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

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

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

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

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

 Профиль  
                  
 
 Re: Factorials
Сообщение02.05.2013, 00:35 


02/11/12
141
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.

 Профиль  
                  
 
 Re: Factorials
Сообщение02.05.2013, 02:24 
Заблокирован


20/10/12

85
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
Страсти накаляются :D


cheetah (Acinonyx jubatus)

Изображение

 Профиль  
                  
 
 Re: Factorials
Сообщение02.05.2013, 06:30 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #718550 писал(а):
Это вы в самом начале заявили, что вот в этом примере не обойтись без эвристики Non-Factor. Я это ваше заявление полностью опровергла, обошлась вообще безо всяких эвристик.

Это ложный посыл.
Такого заявления я не делал.
Вот моё подлинное заявление:
whitefox в сообщении #718444 писал(а):
Но эвристика чётных чисел его не найдёт, так как в решение присутствует число 899.

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

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

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

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

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

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

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

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

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

-- 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

 Профиль  
                  
 
 Re: Factorials
Сообщение02.05.2013, 08:03 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Эксперимент не удался :-(

Изображение

 Профиль  
                  
 
 Re: Factorials
Сообщение02.05.2013, 08:09 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
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 шагов совсем близко :D

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

 Профиль  
                  
 
 Re: Factorials
Сообщение02.05.2013, 08:55 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Что-то не так с реализацией новой фичи.

Изображение
Изображение

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

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

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

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

 Профиль  
                  
 
 Re: Factorials
Сообщение02.05.2013, 09:08 
Заблокирован
Аватара пользователя


22/03/08

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

Эксперимент

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

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

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

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

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

 Профиль  
                  
 
 Re: Factorials
Сообщение02.05.2013, 09:16 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #718585 писал(а):
Вот то-то и оно, что повезло: потерянные последовательности с не-делителями не сказались пагубно на поиске окончательного решения.

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


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

 Профиль  
                  
 
 Re: Factorials
Сообщение02.05.2013, 09:29 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

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

whitefox в сообщении #718587 писал(а):
Раньше Вы были ярой противницей брутфорса :wink:

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

 Профиль  
                  
 
 Re: Factorials
Сообщение02.05.2013, 09:41 
Заслуженный участник
Аватара пользователя


19/12/10
1546
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

 Профиль  
                  
 
 Re: Factorials
Сообщение02.05.2013, 09:53 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #718591 писал(а):
Nataly-Mak в сообщении #718588 писал(а):
Это уже интересно.
А откуда априори известно, что если последовательности строить только из делителей N!, то для любого разложения (на основе которого строится решение) будет существовать оптимальное решение?

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

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

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

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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1310 ]  На страницу Пред.  1 ... 75, 76, 77, 78, 79, 80, 81 ... 88  След.

Модераторы: maxal, Toucan, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group