Prime Sums

[Pavlovsky]

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

А их почему не проверили?

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

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

[Nataly-Mak]

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

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

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

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

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

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

[Pavlovsky]

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

[Nataly-Mak]

Ну вот для НС-ов оно, конечно, годится

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

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

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

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

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

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

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

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

А их почему не проверили?

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

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

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

[svb]

Pavlovsky

Цитата:

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

Смотрел по диагонали, но может сразу Кормена читать? Он у меня и бумажный и электронный имеется. Но дело не в определениях.

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

[Nataly-Mak]

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

Но дело не в определениях.

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

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

[svb]

Nataly-Mak

Цитата:

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

Мы слишком мало знаем о свойствах простых чисел, чтобы решать такую задачу. Для начала неплохо бы гипотезу Римана доказать

[Nataly-Mak]

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

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

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

[dimkadimon]

Вот решение 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

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

[dimkadimon]

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

[whitefox]

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$.
Это и есть число разбиений.

[Vovka17]

Недостающее в БД:

(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% ...

[Nataly-Mak]

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

[mertz]

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

[Pavlovsky]

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

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

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