2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 57, 58, 59, 60, 61, 62, 63 ... 67  След.
 
 Re: Prime Sums
Сообщение07.01.2013, 20:26 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #668534 писал(а):
А их почему не проверили?


Проблема как у svb

Скажем берем схему с оценкой 482 и строим решение 500. Сколько будет распределений чисел по группам? Море и еще одно!

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


22/03/08

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

Эта ветка не для средних умов :D
Я пробовала читать, у меня ничего не получилось. Для меня это слишком заумно. Ну, очень "наукообразно" что ли. Это только для студентов годится, ИМХО. Им, бедным, всегда такими заумностями голову морочат :D

А вы-то как же, ветку читали, хорошо разобрались в теории, любезно преподнесённой Светланой, а утверждение сделали неверное, как вы говорите?

Теория - это, конечно, хорошо. Но что теория без применения к практическим задачам?
"Суха теория, мой друг, а древо жизни вечно зеленеет!" (c)

А я вот задала вопрос на этом форуме: как оценить сложность алгоритма построения наименьшего (или хотя бы любого!) пандиагонального магического квадрата 17-го порядка из простых чисел? Но ответа что-то не получила. Никто не знает? Или наоборот: все знают, но не хотят сказать? :D

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


21/02/10
1594
Екатеринбург
Стандартное введение. :D Давным-давно когдая я был МНСом в Институте математики УрО РАН. NP- полные задачи входили в сферу моих интереосв. Так что оставалось только вспомнить.

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


22/03/08

7154
Саратов
Ну вот для НС-ов оно, конечно, годится :D

-- Пн янв 07, 2013 21:38:09 --

svb в сообщении #668532 писал(а):
Рекордные решения всем интересны, раньше всегда выкладывали, тут язык не важен. А описания алгоритмов возможно будут - было обещано :-)

Рекордные решения, разумеется, интересны всем.
Но я не заметила особого беспокойства из-за отсутствия рекордных решений, а заметила беспокойство по поводу отстутствия описания алгоритмов победителей на английском языке (впрочем, я далеко не всё там перевожу).

Интересно, а почему главный рекордсмен конкурса не опишет свой алгоритм? :wink:

-- Пн янв 07, 2013 21:49:08 --

Pavlovsky в сообщении #668536 писал(а):
Nataly-Mak в сообщении #668534 писал(а):
А их почему не проверили?


Проблема как у svb

Скажем берем схему с оценкой 482 и строим решение 500. Сколько будет распределений чисел по группам? Море и еще одно!

А-а! Так значит, надо не с "шестёрки" даже начинать доказывать оптимальность решений, а с "пятёрки" :D
Я думала, что с "пятёркой" уж точно разобрались.

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


20/01/10
766
Нижний Новгород
Pavlovsky
Цитата:
О псевдополинмиальных алгоритмах можно почитать ветку Светланы.
http://e-science.ru/forum/index.php?showtopic=40500
Смотрел по диагонали, но может сразу Кормена читать? Он у меня и бумажный и электронный имеется. Но дело не в определениях.

Ваша задача в частном случае $m=1$ и без требования $K_m$ (можно нулей насовать) это знаменитая "задача о рюкзаке". На практике выгодно начинать с максимальных весов (вспоминается шахматный конь).

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


22/03/08

7154
Саратов
svb в сообщении #668557 писал(а):
Но дело не в определениях.

Вот и я о том же :-)
Для меня всегда важна практическая сторона вопроса. Вот берём конкретную задачу и начинаем решать. Да, согласна, без минимального знания теории далеко не уедешь. Но! Прочитать ветку о полиномиальных алгоритмах ещё не достаточно для того, чтобы решить, скажем, мою задачу о построении пандиагонального квадрата 17-го порядка из простых чисел.

Ещё пример. Когда я строила много-много разных магических квадратов, применяла на практике алгоритм, который называется "перебор с возвратом", но даже и не знала, что он так называется :-) Узнала об этом совсем недавно.

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


20/01/10
766
Нижний Новгород
Nataly-Mak
Цитата:
как оценить сложность алгоритма построения наименьшего (или хотя бы любого!) пандиагонального магического квадрата 17-го порядка из простых чисел? Но ответа что-то не получила. Никто не знает? Или наоборот: все знают, но не хотят сказать? :D
Мы слишком мало знаем о свойствах простых чисел, чтобы решать такую задачу. Для начала неплохо бы гипотезу Римана доказать :D

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


22/03/08

7154
Саратов
Ну, задачу для порядков 11 и 13 я решила, однако :-)
Думаю, что и для порядка 17 задача вполне решается (речь пока не о наименьшем, а о любом пандиагональном квадрате).

А что касается наименьших... Даже для порядка 7 минимальность квадрата не доказана. Я сейчас бьюсь над этой задачей, одна, никто не хочет помочь. Уже привлекла к решению этой задачи квадраты Стенли. Очень любопытные, кстати, квадратики :-)
Хочу статью в OEIS сделать об этих квадратах.

Да, и... я не прошу решить задачу, а прошу оценить сложность алгоритма её решения. Это вроде не одно и то же (?)
Один из алгоритмов мне известен: это тот же самый алгоритм, какой я использовала для построения квадратов порядков 11 и 13.
Существуют ли другие алгоритмы? И насколько они сложные? Вот с точки зрения этой самой теории об NP-полных задачах и полиномиальных алгоритмах, в которой я ровным счётом ничего не поняла (в указанной Pavlovsky ветке) :?

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


01/06/12
1016
Adelaide, Australia
Вот решение N=5 с оптимальной оценкой 790. Решение забавное потому что в нём одна линия дупликат:

2,7,24,8,5,
3,14,12,18,1,
23,17,25,22,20,
11,10,15,16,21,
9,6,13,19,4

Есть ли ещё оптимальные решения с добавочными линиями?

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


01/06/12
1016
Adelaide, Australia
Я на сайт конкурса загрузил рейтинг всех участников и стран. Прошу проверить и сообщить если есть ошибки. Россия впереди! Смотрите тут: http://infinitesearchspace.dyndns.org/content/global

 Профиль  
                  
 
 Re: Prime Sums
Сообщение08.01.2013, 12:26 
Заслуженный участник
Аватара пользователя


19/12/10
1546
svb в сообщении #668375 писал(а):
Оценка схемы = 1777, ищется решение 1760. top=1777-1760=17 сколько таких распределений существует? Кстати, сама эта задача очень интересна.

Составим все возможные неупорядоченные пары из чисел $1 . . N^2$.
Каждой паре $(a,b)$ присвоим вес равный $|a-b|\cdot|v_a-v_b|$, где $v_a$ и $v_b$ веса соответствующих чисел в выбранной схеме при "естественном" разбиении.
Найдём все возможные множества не пересекающихся пар сумма весов которых равна $top$.
Это и есть число разбиений.

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


10/11/12
121
Бобруйск
Недостающее в БД:
Код:
(N=6,S=1752) 3,24,5,21,13,30,23,7,33,6,29,15,9,31,12,28,20,27,25,11,32,10,36,17,2,18,8,22,16,34,26,4,19,1,35,14
(N=7,S=3088) 33,7,10,38,15,5,16,40,34,37,35,29,21,27,3,45,41,11,2,39,1,42,43,47,46,31,28,32,49,19,20,48,23,18,22,8,24,26,9,17,36,12,4,25,30,6,13,44,14

Мои топы для N=5, 6, 7:
Код:
(N=5,S= 790) 22,8,21,6,10,13,7,11,25,15,14,12,19,24,20,18,9,17,2,3,16,23,5,4,1
(N=6,S=1758) 29,14,32,13,33,18,5,26,2,25,11,23,34,16,35,15,36,21,6,22,3,19,12,31,28,8,17,1,30,10,7,27,4,20,9,24
(N=7,S=3090) 47,44,49,19,6,5,21,42,48,43,40,15,31,22,30,4,26,28,29,9,7,16,3,10,36,27,23,11,13,8,25,17,24,32,14,45,41,38,39,35,34,37,46,33,20,18,2,1,12
(N=5,S= 502) 2,9,17,20,23,12,3,11,22,5,19,16,8,15,24,13,7,1,4,18,21,6,10,25,14
(N=6,S= 890) 3,22,7,32,12,31,14,5,21,6,26,11,2,17,1,24,10,25,23,9,29,16,34,18,4,28,13,35,19,36,27,8,30,20,33,15
(N=7,S=1802) 7,5,9,6,37,3,34,21,2,31,33,8,43,29,1,28,11,12,38,23,24,32,15,13,16,46,27,14,26,19,20,44,18,41,47,25,22,39,10,42,36,48,45,40,4,30,35,49,17

Nataly-Mak в сообщении #668366 писал(а):
помнится, вы писали, что для "шестёрки" убедились в том, что ничего нет лучше найденных рекордов 890 и 1758.
Насчёт максимума уверены? Или это 99,99% ? :-)

В моем алгоритме есть элемент случайности, следовательно о 100% справедливо говорить только в отношении уже найденных решений...
Поэтому уверен лишь на 99,99% :wink:...

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


22/03/08

7154
Саратов
Vovka17
спасибо за решения.
Меня особенно интересует решение 1752, сейчас посмотрю, какая в нём схема.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение08.01.2013, 16:22 


02/11/12
141
I tried to post the update to my program at the contest site. There was an error and it might not get fixed anytime soon. Any ideas?

ed

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #668863 писал(а):
Меня особенно интересует решение 1752, сейчас посмотрю, какая в нём схема.


Уже посмотрел. :D Этого решения мои алгоритмы не нашли. Да уж. Разница между теоретической оценкой схемы и искомым решением 25 баллов! Алгоритмы Vovka17 отжигают все!

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

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



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

Сейчас этот форум просматривают: Dmitriy40


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

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