Prime Sums

[Nataly-Mak]

Vovka17
помнится, вы писали, что для "шестёрки" убедились в том, что ничего нет лучше найденных рекордов 890 и 1758.
Насчёт максимума уверены? Или это 99,99% ?
Если строго несуществование другого максимума не доказано, можно и поискать

[svb]

Nataly-Mak

Цитата:

Стоп! Если я не ошибаюсь, Pavlovsky говорил прямо противоположное

Это все равно, что искать под фонарем. Вот сейчас крутится программа - проверено 20 распределений, для каждого из них найдено по 11 простых линий. И что думать? А вот для схем с близкими оценками к решению ситуация много хуже. За что хвататься?

[Nataly-Mak]

Я предпочитаю "хвататься" за конкретные структуры-схемы-разбиения. Подозреваю, что для "шестёрки" их не запредельное количество.

-- Пн янв 07, 2013 14:32:07 --

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

Если по этим схемам искать решение 1760. Для схемы со структурой 2,14,8,6,6 нет допустимых наборов простых чисел. Для схемы со структурой 6,6,8,14,2 существует 4 допустимых набора простых чисел. Основной алгоритм максимум чего выжал это 6 выставленных линий.

То есть однозначно для этих двух классов схем решения нет?

[svb]

Nataly-Mak

Цитата:

Подозреваю, что для "шестёрки" их не запредельное количество.

Оценка схемы = 1777, ищется решение 1760. top=1777-1760=17 сколько таких распределений существует? Кстати, сама эта задача очень интересна.
Теперь это умножаем на количество схем.

[Nataly-Mak]

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

Оценка схемы = 1777, ищется решение 1760. top=1777-1760=17 сколько таких распределений существует? Кстати, сама эта задача очень интересна.
Теперь это умножаем на количество схем.

У меня другой подход.
Ищется решение 1760. Сначала проверяем уникальные схемы точно с такой оценкой.
Как утверждает whitefox, таких схем всего две (с точностью до изоморфизма).
Вот Pavlovsky уже говорит, что обе эти схемы решения не дали.
Нужна независимая проверка, чтобы исключить ошибки. А проверить всего две схемы с естественным разбиением, как вы утверждаете, для вашей программы дело "минут-секунд". Вот и проверьте
Вдруг Pavlovsky ошибся.
maxal учил, что в решении любой задачи необходимо иметь два независимых исследования, чтобы исключить возможные ошибки.

Затем берём схемы с оценкой 1768 (по-прежнему ищем решение 1760; можно заодно и 1762, 1764, 1766, 1768 поискать). Здесь уже разбиений будет побольше, не одно на каждую схему, а несколько. Но, думаю, не жутко много.
Ну и так далее. Со всем этим, конечно, много возни. Но с хорошей программой можно справиться.

Вот Vovka17 придёт расскажет, как он со всем этим справился
Он писал, что ему потребовался всего один день, чтобы убедиться, что для "шестёрки" больше ничего нет.

-- Пн янв 07, 2013 15:49:40 --

Сейчас запустила свою программу на поиск решения 1760 (по приведённой выше схеме, она у меня конкретно запрограммирована). Ну, для начала убрала проверку 12-ой зачётной линии на различность. При таком условии решение нашлось мгновенно

149 
 151 
 167 
 163 
 173 
 179 
 113 
 137 
 139 
 131 
 127 
 131 

 21  22  23  24  27  32  25  17  35  29  18  30  28  36  31  26  33  34  7  14  15  16  19  20  13  9  8  10  11  12 
 1760 

 0  18  0  21  0  33 
 30  7  25  14  22  15 
 0  17  0  31  0  23 
 24  9  34  16  28  20 
 10  27  11  36  12  35 
 26  8  32  19  29  13

Запустить что ли полный перебор с нормальными условиями для всех зачётных линий?

[svb]

Nataly-Mak

Цитата:

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

Все верно, но ... у меня сейчас такой бардак с программами! Случайная генерация схемы 1760 не проходит, было сделано небольшое "усовершенствование" программы, которое, видимо, повлияло на работу - постоянно попадаю в локальный минимум, но не в тот . Вариант с загрузкой конкретной схемы имеется только для специальной версии $N=7$, там же и генерация схем перебором. Теперь собираюсь все перепроверить и собрать в очередную версию программы.

[svb]

Кажется понял, почему я никак не мог получить случайную схему 1760. Просто у меня распределение линий по типам (3,3,3,3):

(Оффтоп)

 9,28, 5,36,13,22,
20, 3,25,16,29, 6,
 7,23, 1,35, 8,17,
32,11,24,21,33,10,
14,30,12,34,18,31,
27, 4,19,15,26, 2,
C=12  C1=12  Count=1758

113:99 91 131:139:93 
109:99 86 157:127:88 
54 149:64 163:57 179:
60 151:58 173:57 167:

M0: 3 6 1 4 2
M1: 5 16 7 8 11 10 12 15
M2: 9 13 25 23 17 21 14 18 19
M3: 28 22 20 29 35 24 30 31 27 26
M4: 36 32 33 34

2 3 1 4 2 3 
3 0 2 1 3 0 
1 2 0 3 1 2 
4 1 3 2 4 1 
2 3 1 4 2 3 
3 0 2 1 3 0 

0:5 1:8 2:9 3:10 4:4  min=887  max=1777

12,24,11,32,17,31,
26, 2,18,13,30, 5,
 3,19, 4,29, 8,21,
33,16,36,22,35,15,
10,28, 7,34,14,20,
25, 1,23, 9,27, 6,
C=12  C1=12  Count=1758

127:94 84 157:113:91 
109:90 99 139:131:98 
60 173:57 167:58 151:
55 163:54 149:66 179:

M0: 2 5 4 1 6
M1: 11 13 3 8 16 15 7 9
M2: 12 17 18 19 21 22 10 14 23
M3: 24 31 26 30 29 36 28 20 25 27
M4: 32 33 35 34

2 3 1 4 2 3 
3 0 2 1 3 0 
1 2 0 3 1 2 
4 1 3 2 4 1 
2 3 1 4 2 3 
3 0 2 1 3 0 

0:5 1:8 2:9 3:10 4:4  min=887  max=1777

12,24,11,32,17,31,
26, 2,18, 9,30, 1,
 3,19, 4,29, 8,21,
33,16,36,22,35,15,
10,28, 7,34,14,20,
25, 5,23,13,27, 6,
C=12  C1=12  Count=1758

127:86 84 157:113:99 
109:94 99 139:131:94 
60 173:57 167:58 151:
55 163:58 149:62 179:

M0: 2 1 4 5 6
M1: 11 9 3 8 16 15 7 13
M2: 12 17 18 19 21 22 10 14 23
M3: 24 31 26 30 29 36 28 20 25 27
M4: 32 33 35 34

2 3 1 4 2 3 
3 0 2 1 3 0 
1 2 0 3 1 2 
4 1 3 2 4 1 
2 3 1 4 2 3 
3 0 2 1 3 0 

0:5 1:8 2:9 3:10 4:4  min=887  max=1777

12,24,11,32,17,31,
26, 5,18, 9,30, 2,
 3,19, 1,29, 8,21,
33,15,36,22,35,16,
10,28, 7,34,14,20,
25, 4,23,13,27, 6,
C=12  C1=12  Count=1758

127:90 81 157:113:98 
109:95 96 139:131:96 
60 173:57 167:58 151:
55 163:62 149:58 179:

M0: 5 2 1 4 6
M1: 11 9 3 8 15 16 7 13
M2: 12 17 18 19 21 22 10 14 23
M3: 24 31 26 30 29 36 28 20 25 27
M4: 32 33 35 34

2 3 1 4 2 3 
3 0 2 1 3 0 
1 2 0 3 1 2 
4 1 3 2 4 1 
2 3 1 4 2 3 
3 0 2 1 3 0 

0:5 1:8 2:9 3:10 4:4  min=887  max=1777

 8,19, 7,31,16,28,
26, 2,20,11,30, 4,
 6,25, 5,24,12,21,
36,13,35,22,34,17,
14,27, 9,33,15,29,
23, 1,18,10,32, 3,
C=12  C1=12  Count=1758

109:93 93 157:127:87 
113:87 94 131:139:102 
55 179:58 163:62 149:
56 151:57 173:62 167:

M0: 2 4 5 1 3
M1: 7 11 6 12 13 17 9 10
M2: 8 16 20 25 21 22 14 15 18
M3: 19 28 26 30 24 35 27 29 23 32
M4: 31 36 34 33

2 3 1 4 2 3 
3 0 2 1 3 0 
1 2 0 3 1 2 
4 1 3 2 4 1 
2 3 1 4 2 3 
3 0 2 1 3 0 

0:5 1:8 2:9 3:10 4:4  min=887  max=1777

[Pavlovsky]

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

Кажется понял, почему я никак не мог получить случайную схему 1760. Просто у меня распределение линий по типам (3,3,3,3)

А зачем генерировать случайно схемы 1760? Когда их всего две. Посмотрел эти схемы, действительно в обеих схемах распределение по типам (4,2,3,3). Когда перебирал схемы для N=6, убрал требование равномерного распределения зачетных линий по типам.

[Nataly-Mak]

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

Например, структура 2,14,8,6,6, оценка Q=1760 (при естественном разбиении).
Схема:

0 2 0 3 0 3
3 1 3 2 3 2
0 2 0 3 0 3
3 1 3 2 3 2
1 3 1 4 1 4
3 1 3 2 3 2

Не даёт решения 1760?

Не даёт.
Проверила по своей программе полного перебора.
Таким образом, вывод по этой схеме уже точный: получен двоими.

[svb]

Pavlovsky

Цитата:

А зачем генерировать случайно схемы 1760? Когда их всего две.

Могут и другие понадобиться. Никто же не знает где спрятано решение

Пока это вопрос чисто технический для доработки программы. Вот найти критерии оценки схем и распределений - это основной вопрос. Здесь компьютер может дать только проверку идей. Как влияет топология схемы на сходимость поисковых процессов?

Вы как-то писали, что нет решения 500 для $N=5$. Что вы имели в виду?

Давно хочется опробовать ваш любимый метод исследования "по модулю".

-- Пн янв 07, 2013 19:52:59 --

Вот и на основном форуме конкурса забеспокоились

[Nataly-Mak]

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

Вот и на основном форуме конкурса забеспокоились

Это вы о том, что публика просит описания алгоритмов победителей на английском языке?
Обойдутся!
Чуть выше я высказала своё мнение на этот счёт.
Всех русских конкурсантов на форуме конкурса обвинили в краже. Только вот непонятно: у кого украл свои рекорды Vovka17?

[Pavlovsky]

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

Вы как-то писали, что нет решения 500 для . Что вы имели в виду?

Ну это было давно. Проверил несколько схем, известных мне на тот момент. Для которых не было допустимого набора чисел. То есть общего доказательства, что нет решения 500 для N=5 у меня не было тогда, нет и сейчас.

-- Пн янв 07, 2013 22:16:16 --

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

Вот и на основном форуме конкурса забеспокоились

Блин да напишу я описание своего алгоритма на английском. Для начала хотелось обсудить его здесь на родном языке. Что то мало комментариев, неужели всем все понятно?!
Например.

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

Дано: m множеств A1,A2,...,Am. Элементами каждого множества Ai является некоторый набор натуральных чисел. Также задан вектор чисел K1,K2,...,Km. Еще задано число S.Необходимо: Из каждого множества Ai выбрать Ki чисел, так чтобы сумма выбранных чисел равнялась числу S.Задача является NP-полной. Причем NP-полной в сильном смысле, для нее не существует псевдополиномиального алгоритма.

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

О псевдополинмиальных алгоритмах можно почитать ветку Светланы.
http://e-science.ru/forum/index.php?showtopic=40500

[svb]

Nataly-Mak
Рекордные решения всем интересны, раньше всегда выкладывали, тут язык не важен. А описания алгоритмов возможно будут - было обещано

[Nataly-Mak]

Pavlovsky
Как?! Даже и для N=5 оптимальность решений не доказана?
Проверили все схемы, известные на тот момент. Но теперь-то вам известны все схемы (?)
А их почему не проверили?

[svb]

Pavlovsky

Цитата:

Что то мало комментариев, неужели всем все понятно?!

Это только одному венгру все сразу ясно