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
765
Нижний Новгород
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
765
Нижний Новгород
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
862
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
862
Adelaide, Australia
Я на сайт конкурса загрузил рейтинг всех участников и стран. Прошу проверить и сообщить если есть ошибки. Россия впереди! Смотрите тут: http://infinitesearchspace.dyndns.org/content/global

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


19/12/10
1539
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
119
Бобруйск
Недостающее в БД:
Код:
(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, PAV, Toucan, maxal, Супермодераторы



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

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


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

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