Prime Sums

[Nataly-Mak]

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

Получется схем 1798 больше тысячи, распределений чисел по группам 14, наборов простых чисел для каждой схемы разное, но в среднем штук 20. 1000*14*20 примерно 200 000. Только начальная подготовка займет дня два-три. Сколько будет работать основной алгоритм, посчитать на пальцах невозможно.

Ну, в таком случае проще отказаться вообще от поиска решений.
Логично

Цитата:

1000*14*20 примерно 200 000

Это уже примерно 280 000

[Pavlovsky]

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

На выходе получил все канонические схемы с оценкой не выше 1816.

Искал схемы с оценкой до 1810 (максимум 3090). Как то сразу решил не размениваться на промежуточные результаты, а искать только рекорды. К тому же алгоритмы поиска по заданным схемам принимают искомую сумму в качестве входных данных.

[whitefox]

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

Единственоое отличие. Я перебор делал с ограничениями:
1) Количество линий каждого типа примерно одинаково. То есть для N=7 равно 3 или 4. Реализовать это ограничение при переборе не трудно.
2) Есть хотя бы одна ячейка, где пересекаются 4 линии.

Эти ограничения я добавил во второй версии программы, когда проверял Ваши результаты. Для схем с оценкой меньше 1806 эта версия выдала результаты аналогичные результатам первой версии.

-- 20 дек 2012, 12:46 --

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

То есть перебираю схемы, где всегда есть линии 1,5,8,22

Может Вы имели ввиду 1,8,15,22 ?

[Pavlovsky]

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

Ну, вот и разберитесь, кто напутал, а то сразу и заняться нечем

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

-- Чт дек 20, 2012 13:50:04 --

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

Может Вы имели ввиду 1,8,15,22

Блин конечно да. Это была учебная ошибка, проверка на понимание.

[Nataly-Mak]

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

Подумаешь потерял пару десятков неизоморфных схем.

Ну, да, если ещё потерянные схемы добавить, то и в 200 000 не уложитесь

Цитата:

Того что есть вполне достаточно.

Достаточно для чего?

Цитата:

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

Пора уже выдавать рекорды

[Pavlovsky]

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

Пора уже выдавать рекорды

На моем домашнем компьютере 4 ядра. Три копии программы ищут рекорды. Перспективы нахождения рекорда близки к нулю.

[Nataly-Mak]

У меня 2 ядра. Одновременно работают 4 программы. При этом свободно пишу сюда, пишу письма. Вот только кино смотреть уже нельзя
Так что вам надо запускть не 3 копии, а по крайней мере 7 копий. Попробуйте.
Мой компьютер вполне тянет. А программы-то, похоже, не сильно отличаются.
Сейчас вот уже почти 7 часов крутится поиск решений 1800 и 3098 (отдельно две копии программы). Конечно, я не жду полных решений, но полуфабрикатов много, в том числе с 12 выставленными зачётными линиями. Насчёт 13 пока не знаю, может есть, а может нет. Скорее всего, нет.
С 14 линиями, наверное, есть, но опять не из той оперы

[Pavlovsky]

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

Готовое решение с 12 выставленными зачётными линиями могу показать, если никто не возражает
Выставленные зачётные линии имеют значения:


Код:
233,239,227,251,229,197,241,211,193,191,223,199

Не выставленные зачётные линии имеют значения 232 и 236.

232+236=468

79,389
89,379
101,367
109,359
131,337
137,331
151,317
157,311

В этих парах одно число слишком маленькое другое слишком большое.

191,277
197,271
199,269
211,257
227,241
229,239

В этих парах присутствут уже использованные числа

-- Чт дек 20, 2012 16:34:17 --

Когда выбрана схема и задано распределение чисел по группам, легко посчитать минимально (максимально) возможную сумму которую можно выставить в зачетных линиях. Для маленьких N (в т.ч. для N=7) эти пределы существенно сокращают количество допустимых наборов простых чисел.

[Nataly-Mak]

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

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

Так вот поэтому полное решение и не получилось.
Я понимаю, что тут плохое разложение Q на 14 простых.
Увы, я не могу сама изменить программу whitefox. На мой взгляд главная беда его очень хорошей программы - это то, что он не привязал поиск к конкретному разложению Q на простые числа.
Поэтому программа и ищет всё, кроме того, что нужно

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

[Nataly-Mak]

За 11 часов работы программа поиска решения с Q=3098 нашла 39 приближений к решению.
Загоняю все эти решения в программу проверки решений, получаю вот такие результаты:

(Оффтоп)

2910
0
0
2898
0
2892
2900
2910
0
0
0
0
0
2880
0
0
0
0
2892
2910
2922
0
2898
0
2898
0
2902
0
2880
0
0
0
2898
2892
0
2904
0
3018
0

Где нули, в этих решениях количество выставленных зачётных линий меньше или больше 14; а где их ровно 14, получены готовые решения.
Аналогично программа поиска решений с Q=1800 за те же 11 часов работы нашла 38 приближений к решению. При проверке сумм в этих квадратах примерно такая же картина, только результаты поменьше.

Сейчас собираюсь просмотреть все эти решения.

-- Пт дек 21, 2012 12:39:05 --

Просмотрела 39 квадратов.
Нашла интересные приближения к решению с Q=3098.

1. 18 выставленный зачётных линий, 17 различных; выставлены все столбцы:

29,19,13,24,1,15,45,
28,17,18,8,2,6,46,
48,49,11,42,27,21,31,
36,43,25,37,44,10,38,
5,7,26,40,3,20,16,
4,23,12,34,22,9,33,
47,35,14,41,39,30,32

2. выставлено 12 зачётных линий:

23,18,4,21,3,11,44,
24,16,29,13,1,14,38,
48,47,7,39,27,34,26,
36,43,32,40,45,15,46,
5,6,30,41,2,28,17,
8,19,10,22,20,12,31,
49,42,9,35,37,33,25

3. выставлены 13 зачётных линий



Значение 14-ой зачётной линии равно 207.
Такое вот близкое приближение к решению, всего одна зачётная линия немножко неправильная. Так, может, решение Q=3098 существует

[Nataly-Mak]

Для Q=1800 нашла два интересных приближения.

1. выставлено 12 зачётных линий:

3,21,19,4,33,8,9,
24,18,6,28,16,12,23,
30,46,32,11,36,22,37,
29,48,44,14,35,39,17,
31,40,41,47,34,15,20,
7,10,38,26,25,1,2,
13,49,45,27,43,42,5

2. выставлены все 14 зачётных линий, но... две одинаковые:



Почти готовое решение Ну, чуточку не так.

Сегодня у меня программа ищет решения для Q=3096 и Q=3094.
Кстати, не мешало бы собрать все готовые решения, выдаваемые программой - для базы данных всех решений.
dimkadimon уже начал эту работу.
У меня тоже есть очень много решений, можно все прогнать через программу проверки решений, посмотреть все результаты.

[Nataly-Mak]

Рассмотрела "почти решение" Q=1800 более подробно.
Очень красивое получилось решение. Прямо обидно, что две зачётные линии приняли одинаковое значение.



Структура решения: 2,16,13,16,2 - симметричная.
Схему писать не буду, её легко восстановить по решению.
Разбиение:

$M_0=(48,49) M_1=(32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47) M_2=(19,20,21,22,23,24,25,26,27,28,29,30,31) M_3=(2,3,5,6,7,8,9,10,11,12,13,14,15,16,17,18) M_4=(1,4)$
Перестановкой всего двух чисел в двух весовых классах легко получить разбиения с близкими оценками Q=1798 и Q=1802.

[Pavlovsky]

Как всегда, под конец конкурса в голову полезли супер идеи. Но уже нет времени их реализовывать. Да и негде их применять. Все места где были хорошие шансы найти рекорд, проверил. А молотить пустую породу нет стимула.

[Nataly-Mak]

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

Все места где были хорошие шансы найти рекорд, проверил.

Этого не может быть.
Мест таких очень и очень много. Не вы ли писали о 200 000?
Никто не доказал, что для "семёрки" невозможно найти улучшения.
Во всяком случае, я такого доказательства не видела.

[Pavlovsky]

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

Не вы ли писали о 200 000

Сегодня вечером запущу проверку. Но это все порожняк. Больше 9 выставленных линий не видел.