2014 dxdy logo

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

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




На страницу Пред.  1 ... 56, 57, 58, 59, 60, 61, 62 ... 67  След.
 
 Re: Prime Sums
Сообщение07.01.2013, 13:22 
Аватара пользователя
Vovka17
помнится, вы писали, что для "шестёрки" убедились в том, что ничего нет лучше найденных рекордов 890 и 1758.
Насчёт максимума уверены? Или это 99,99% ? :-)
Если строго несуществование другого максимума не доказано, можно и поискать :wink:

 
 
 
 Re: Prime Sums
Сообщение07.01.2013, 13:23 
Аватара пользователя
Nataly-Mak
Цитата:
Стоп! Если я не ошибаюсь, Pavlovsky говорил прямо противоположное :-)
Это все равно, что искать под фонарем. Вот сейчас крутится программа - проверено 20 распределений, для каждого из них найдено по 11 простых линий. И что думать? А вот для схем с близкими оценками к решению ситуация много хуже. За что хвататься?

 
 
 
 Re: Prime Sums
Сообщение07.01.2013, 13:27 
Аватара пользователя
Я предпочитаю "хвататься" за конкретные структуры-схемы-разбиения. Подозреваю, что для "шестёрки" их не запредельное количество.

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

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

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

 
 
 
 Re: Prime Sums
Сообщение07.01.2013, 13:35 
Аватара пользователя
Nataly-Mak
Цитата:
Подозреваю, что для "шестёрки" их не запредельное количество.
Оценка схемы = 1777, ищется решение 1760. top=1777-1760=17 сколько таких распределений существует? Кстати, сама эта задача очень интересна.
Теперь это умножаем на количество схем.

 
 
 
 Re: Prime Sums
Сообщение07.01.2013, 14:26 
Аватара пользователя
svb в сообщении #668375 писал(а):
Оценка схемы = 1777, ищется решение 1760. top=1777-1760=17 сколько таких распределений существует? Кстати, сама эта задача очень интересна.
Теперь это умножаем на количество схем.

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

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

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

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

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

Код:
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

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

 
 
 
 Re: Prime Sums
Сообщение07.01.2013, 16:04 
Аватара пользователя
Nataly-Mak
Цитата:
Нужна независимая проверка, чтобы исключить ошибки. А проверить всего две схемы с естественным разбиением, как вы утверждаете, для вашей программы дело "минут-секунд". Вот и проверьте :-)
Все верно, но ... у меня сейчас такой бардак с программами! Случайная генерация схемы 1760 не проходит, было сделано небольшое "усовершенствование" программы, которое, видимо, повлияло на работу - постоянно попадаю в локальный минимум, но не в тот :-) . Вариант с загрузкой конкретной схемы имеется только для специальной версии $N=7$, там же и генерация схем перебором. Теперь собираюсь все перепроверить и собрать в очередную версию программы.

 
 
 
 Re: Prime Sums
Сообщение07.01.2013, 18:15 
Аватара пользователя
Кажется понял, почему я никак не мог получить случайную схему 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

 
 
 
 Re: Prime Sums
Сообщение07.01.2013, 18:31 
Аватара пользователя
svb в сообщении #668484 писал(а):
Кажется понял, почему я никак не мог получить случайную схему 1760. Просто у меня распределение линий по типам (3,3,3,3)


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

 
 
 
 Re: Prime Sums
Сообщение07.01.2013, 18:56 
Аватара пользователя
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?

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

 
 
 
 Re: Prime Sums
Сообщение07.01.2013, 19:27 
Аватара пользователя
Pavlovsky
Цитата:
А зачем генерировать случайно схемы 1760? Когда их всего две.
Могут и другие понадобиться. Никто же не знает где спрятано решение :-)

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

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

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

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

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

 
 
 
 Re: Prime Sums
Сообщение07.01.2013, 20:08 
Аватара пользователя
svb в сообщении #668510 писал(а):
Вот и на основном форуме конкурса забеспокоились :-)

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

 
 
 
 Re: Prime Sums
Сообщение07.01.2013, 20:09 
Аватара пользователя
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

 
 
 
 Re: Prime Sums
Сообщение07.01.2013, 20:18 
Аватара пользователя
Nataly-Mak
Рекордные решения всем интересны, раньше всегда выкладывали, тут язык не важен. А описания алгоритмов возможно будут - было обещано :-)

 
 
 
 Re: Prime Sums
Сообщение07.01.2013, 20:21 
Аватара пользователя
Pavlovsky
Как?! Даже и для N=5 оптимальность решений не доказана? :shock:
Проверили все схемы, известные на тот момент. Но теперь-то вам известны все схемы (?)
А их почему не проверили?

 
 
 
 Re: Prime Sums
Сообщение07.01.2013, 20:21 
Аватара пользователя
Pavlovsky
Цитата:
Что то мало комментариев, неужели всем все понятно?!
Это только одному венгру все сразу ясно :-)

 
 
 [ Сообщений: 1005 ]  На страницу Пред.  1 ... 56, 57, 58, 59, 60, 61, 62 ... 67  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group