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 
Заблокирован
Аватара пользователя


22/03/08

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 13:23 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 13:27 
Заблокирован
Аватара пользователя


22/03/08

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

-- Пн янв 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 
Аватара пользователя


20/01/10
766
Нижний Новгород
Nataly-Mak
Цитата:
Подозреваю, что для "шестёрки" их не запредельное количество.
Оценка схемы = 1777, ищется решение 1760. top=1777-1760=17 сколько таких распределений существует? Кстати, сама эта задача очень интересна.
Теперь это умножаем на количество схем.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 14:26 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
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 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 18:15 
Аватара пользователя


20/01/10
766
Нижний Новгород
Кажется понял, почему я никак не мог получить случайную схему 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 
Аватара пользователя


21/02/10
1594
Екатеринбург
svb в сообщении #668484 писал(а):
Кажется понял, почему я никак не мог получить случайную схему 1760. Просто у меня распределение линий по типам (3,3,3,3)


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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 18:56 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
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 
Аватара пользователя


20/01/10
766
Нижний Новгород
Pavlovsky
Цитата:
А зачем генерировать случайно схемы 1760? Когда их всего две.
Могут и другие понадобиться. Никто же не знает где спрятано решение :-)

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

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

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

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

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 20:08 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
svb в сообщении #668510 писал(а):
Вот и на основном форуме конкурса забеспокоились :-)

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 20:09 
Аватара пользователя


21/02/10
1594
Екатеринбург
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 
Аватара пользователя


20/01/10
766
Нижний Новгород
Nataly-Mak
Рекордные решения всем интересны, раньше всегда выкладывали, тут язык не важен. А описания алгоритмов возможно будут - было обещано :-)

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 20:21 
Заблокирован
Аватара пользователя


22/03/08

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 20:21 
Аватара пользователя


20/01/10
766
Нижний Новгород
Pavlovsky
Цитата:
Что то мало комментариев, неужели всем все понятно?!
Это только одному венгру все сразу ясно :-)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1 ... 56, 57, 58, 59, 60, 61, 62 ... 67  След.

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



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

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


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

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