Prime Sums

[whitefox]

dimkadimon в сообщении #656869 писал(а):

Он превратился в троля. Я потерял почти всё уважение к нему,

И это печально.
Грустно наблюдать как талантливый человек губит свою репутацию.
Ведь его первоначальные результаты заслуживали всяческого уважения.
Очень жаль.

[Pavlovsky]

Третьи сутки программа ищет результаты для N=6. Ежедневно совершенствую программу на уровне микро идей.
Кстати убеждаюсь что распределение чисел по группам, когда у нас схема имеет оценку не равную искомой сумме, оказывает незначительное влияние. Для N=5,7 распределял числа по группам первым понравившимся способом и это дало результат. Для N=6 задаю все возможные варианты распределения чисел по группам. Промежуточные результаты показывают, что выбрать правильную схему гораздо важнее чем задать правильное распределение чисел по группам.

[svb]

Pavlovsky

Цитата:

Для N=5,7 распределял числа по группам первым понравившимся способом и это дало результат.

При N=5 для данного распределения чисел по группам (и выбранной схеме) возможен полный перебор и он показывает, что это не так. Я использую N=5,6 для тестирования. Сложности возникают только для 1758. Последние "усовершенствования" привели к отрицательному результату - даже найденные раньше результаты перестали находиться

[Pavlovsky]

Не могу понять причину трудностей при поиске решения для N=6. Считал, что для четных N у меня огромный потенциал у существующих алгоритмов. Добавил к ним еще алгоритм который нашел рекорды для N=7. Причем рекорды для N=7 были найдены очень легко. Написание программы заняло гораздо больше времени чем собственно само выполнение программы. Оба рекорда для N=7 были найдены меньше чем за час работы программы.

Казалось бы результаты для N=6 должны появиться мгонвенно. Идут третьи сутки молотилова, а лучший результат все тот же 9 выставленных линий. А надо 11( 12-я линия получится автоматически). Где то ошибка?! То ли в программе, то ли в рассуждениях. В программе вроде не должно быть ошибок, большинство модулей учавствовало в поиске предыдущих решений. Да и судя по отладочным сообщениям работает программа адекватно. Значит, что то упустил в своих рассуждениях. Ладно пусть программа молотит до выходных. А там посмотрю промежуточные результаты, прикину где проблемы.

К тому же, что то никто не торопиться занять второе место.

[svb]

Pavlovsky

Цитата:

Не могу понять причину трудностей при поиске решения для N=6.

Мне это тоже кажется удивительным Особенно 890. При случайных схемах этот результат постоянно вылезает. Вот в отношении N=7 я не исключаю, что ваш выбор схемы был удачным.

[Pavlovsky]

svb в сообщении #657417 писал(а):

Мне это тоже кажется удивительным

Не забывайте, что я кодю на платформе 1С 7.7. Поэтому, при переборе, шаг влево, шаг вправо и улетаешь в годы расчетов.

-- Ср дек 12, 2012 15:49:57 --

svb в сообщении #657417 писал(а):

Вот в отношении N=7 я не исключаю, что ваш выбор схемы был удачным.

При поиске результата 1802 действительно повезло, нужная схема оказалась третьей или четвертой. А когда искал 3090, тут уже никакого везения. Написал алгоритм, который перебирал схемы по порядку. Правда, оказалось, что неизоморфные схемы я сформировал неверно. У меня получилось их меньше чем должно быть. Так что тоже немного повезло, что нужная схема оказалась в моем списке.

Чем случайный выбор лучше полного перебора. Я могу задавать количество иттераций! Сначала перебираю все схемы с небольшим количеством иттераций. Оставляю переспективные схемы. Увеличиваю количество иттераций и повторяю случайный перебор по оставшимся схемам. Когда схем осталось немного, делаю количество иттераций достаточно большим.
Вариант алгоритма Монте-Карло?!

-- Ср дек 12, 2012 16:07:59 --

А еще есть секретная идея! Она впрочем достаточно очевидна, но почему то не обсуждалась в этой теме.
Она позволяет:
1) Кардинально уменьшить коэффициент ветвления при переборе.
2) Обеспечить хорошие шансы заполнения квадрата на завершающих стадиях перебора.

[svb]

Pavlovsky

Цитата:

Не забывайте, что я кодю на платформе 1С 7.7.

Вы с Наталией мазохисты Еще ее можно понять, нравится basic, но для него существуют компиляторы не уступающие по быстродействию всяким "современным" языкам. Я люблю алгоритмы, поэтому мне очень удобен pascal. Для картинок существует delphi, но он явно перегружен для наших задач. Уэзерел писал, что язык вторичен, но мне бы не хотелось переучиваться на китайский .

Цитата:

Чем случайный выбор лучше полного перебора. Я могу задавать количество иттераций!

Ну, это неизбежное зло, уже при N>5 ни о каком полном переборе речи не может быть. Вот тут и начинаются отличия. По идее, это можно было исследовать, но времени не остается

[Pavlovsky]

svb в сообщении #657439 писал(а):

Вы с Наталией мазохисты

Платформа 1С - отличная платформа. Она меня кормит! А вот изучать язык (точнее вспоминать), скажем С++, только для участия в конкурсе - это действительно мазохизм.

[svb]

Pavlovsky

Цитата:

А вот изучать язык (точнее вспоминать), скажем С++, только для участия в конкурсе - это действительно мазохизм.

Раньше в ФИДО проживал очень талантливый программист, Луговский. Он от c++ камня на камне не оставил. c++ хоть и уродлив, но это можно было бы еще терпеть, но терпеть компилятор у меня никогда не хватало сил. Имеющиеся компиляторы для паскаля, тот же Free Pascal, просто невидимы. Набрал текст с использованием десятка операторов и все - настройки компилятора минимальны и делаются только при установке, потом о них можно забыть.

[Pavlovsky]

svb в сообщении #657453 писал(а):

Имеющиеся компиляторы для паскаля, тот же Free Pascal, просто невидимы

Уговорил. Если решу освоить транслируемый язык программирования, обращусь к вам за помощью.

[Pavlovsky]

27  Valery Pavlovsky 49.256300 12-13-2012 @ 08:56:57

Есть 49 рекордов из 50-ти! Остался минимум для N=6. Еще немного, еще чуть чуть. Последний бой он трудный самый...

-- Чт дек 13, 2012 08:33:07 --

Решение 1758 для N=6 далось трудно. Трое суток непрерывной работы программы. На успех повлияли, то ли последние микро улучшения программы или фортуна наконец оценила упорство и пожалела мой домашний компьютер.

[svb]

Pavlovsky

Цитата:

Решение 1758 для N=6 далось трудно.

890 - это уже полная ерунда Сочувствую, жалко расставаться с задачей?

[Pavlovsky]

Чем еще случайный выбор лучше полного перебора:
1) Программу в любой момент можно прервать. Скажем для внесения изменений в программу или задания новых параметров поиска. При полном переборе придется после прерывания все начинать заново.
2) Если в узле перебора мы разворачиваем сложную структуру данных, то при полном переборе должны ломать голову как эту структуру сохранять и восстанавливать. При случайном поиске этого делать не надо, ведь в случае неудачи мы начинаем все заново. А развернуть начальную структуру данных как правило легко.

-- Чт дек 13, 2012 14:17:35 --

svb в сообщении #657853 писал(а):

Сочувствую, жалко расставаться с задачей

Есть 50 баллов! Чем еще заняться? Когда искал решения для N=7, попробовал искать рекорды. Но ничего даже близко не было. Похоже все рекорды найдены.

[Nataly-Mak]

Pavlovsky в сообщении #657861 писал(а):

Есть 50 баллов!

Браво, Pavlovsky!
Вы вполне заслуженно заняли второе место. Ведь вся теория схем - это ваша теория.
В этом конкурсе вы большой молодец

Цитата:

Чем еще заняться? Когда искал решения для N=7, попробовал искать рекорды. Но ничего даже близко не было. Похоже все рекорды найдены.

Ну, это только "похоже" А точно? Например, Владимир в этом не уверен.
У вас есть шанс подняться ещё на одну позицию в случае, если всё-таки рекорды для "семёрки" ещё существуют. Докажите, что их нет

Цитата:

1) Программу в любой момент можно прервать. Скажем для внесения изменений в программу или задания новых параметров поиска. При полном переборе придется после прерывания все начинать заново.

Ну, тут вы, наверное, не правы.
whitefox написал программу полного перебора для поиска диагональных решений (N=5); он сделал в программе возможность прерывания в любой момент, и при этом ничего не терялось из уже проверенного, при новом запуске программы она продолжала работу с прерванного места.

(Оффтоп)

А у меня был небольшой тайм-аут, ездила к внукам в деревню. Эх, хорошо там!

[Pavlovsky]

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

при новом запуске программы она продолжала работу с прерванного места.

А если я вношу изменения в программу, меняющие порядок перебора? Я не говорю, что случайный поиск всегда лучше полного перебора. Скажем в предыдущем конкурсе, когда искал диагональные решения, у меня тоже был полный перебор. Напомню тогда у меня программа работала непрерывно целую неделю. И тоже приходилось придумывать возможность прервать программу и начинать с точки останова.