Prime Sums

[Nataly-Mak]

Vovka17 в сообщении #668219 писал(а):

Наверное пропустили. Вот было:

Vovka17 в сообщении #666068 писал(а):

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

Итоги по БД:
для "пятёрки" не найдено решение 506; для "шестёрки" не найдено решение 1752; для "семёрки" БД полная.

Решение 1752 для N=6 существует - 100%. Можете считать БД для шестерки тоже полной.
Решения 506 для N=5 не существует с вероятностью $\approx100$%.

Я, после ответов на вопросы по алгоритму, не заходил на форум и не видел вашего сообщения в личке. Это решение (1752 для N=6) я находил раньше, но не сохранял, как, впрочем, и решение 3088 для N=7. Но без проблем найду их снова, если надо для БД. Только моя программа на работе, смогу найти для вас эти решения и выложить здесь 8-го января.

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

Хорошо, что решение 1752 существует, люблю полноту БД
То, что решение 3088 вы находили, я хорошо помню, это был один из ваших первых рекордов по "семёрке".

-- Пн янв 07, 2013 07:58:20 --

Роюсь в черновиках. Вот и струкутуру 3,12,19,12,3 тоже пробовала. Но! схема у меня выбрана не такая, как у Pavlovsky (схемы и структуры мне присылал whitefox):

0 0 0 1 3 3 3
2 1 1 2 4 4 3
1 1 1 1 2 2 2
1 2 2 1 1 1 2
3 3 3 2 2 2 2
2 3 2 2 3 2 3
2 1 2 2 3 4 3

Это схема Pavlovsky:

4 4 2 2 3 1 1
3 3 3 3 1 2 2
2 2 4 3 1 2 3
3 3 2 3 3 2 1
2 2 1 2 2 1 0
1 1 3 2 0 1 2
2 2 2 2 0 1 1

На мой интуитивный взгляд эти две схемы неизоморфны. Что скажут специалисты по схемам?

[Pavlovsky]

Когда искал рекорды для N=7, в качестве теста запускал поиск решения 1802 по всем схемам с оценкой 1802. Найдено решение для 12 различных схем.
Все найденные решения имеют набор простых чисел

97,101,103,107,109,113,127,131,137,139,151,157,163,167

100% подтверждение гипотезы о последнем наборе в списке.
Забавно, все схемы для которых найдено решение имеют структуру 3,12,19,12,3.

[whitefox]

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

whitefox
как я поняла, у вас пропал интерес к задаче напрочь.
Очень жаль!
Теперь, когда точно известна схема, дающая результат, можно было бы проверить на ней вашу программу. Почему она так и не даёт результат? Чего в ней не хватает? Или чтобы получить результат, программу надо покрутить сутки-двое?

Моя программа реализует алгоритм уже описанный dimkadimon.
Причина провала этого алгоритма на N=7 вот в этом:

dimkadimon в сообщении #666018 писал(а):

Главное: переставляем только те елементы которые зачитываются одинаковое количество раз (смотрите пункт 2) - ведь при етом есть гарантия что сумма решения не поменяется.

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

[svb]

Покрутил вчера по своей программе схему Pavlovsky 1802, больше 12 простых линий она не выдала. Выбранный мною перебор явно не проходит для $N=7$. Конечно, можно было бы подключить ее величество "случайность", но в таком случае это будет заведомо хуже отжига. Но меня пока не оставляет надежда, что существует алгоритм с лучшим отсечением вариантов.

Предпосылки думать так имеются. Последовательно просматриваю $2N$ линий, явно нарушаю "однородность" их вхождения в перебор, а отката на другой порядок просмотра линий нет (с использованием уже полученной информации). В результате наблюдается явный повтор уже исследованных путей.

Когда проводил перебор схем 1798, то получал большое количество 13 простых линий (для 1802), что и подталкивает меня к мысли о существовании решений для этих схем. Но там добавляется выбор распределений $M_i$, при отклонении на 4 он небольшой, но резко возрастает для больших значений отклонений.

[Pavlovsky]

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

Конечно, можно было бы подключить ее величество "случайность", но в таком случае это будет заведомо хуже отжига.

Хм. У меня ведь не отжиг. Учитывая 100-кратную фору по производительности платформы. Решения находятся мгновенно.

-- Пн янв 07, 2013 12:33:22 --

svb
Может я где то пропустил. Опишите, плиз, свой алгоритм перебора.

[svb]

Pavlovsky

Цитата:

Хм. У меня ведь не отжиг. Учитывая 100-кратную фору по производительности платформы. Решения находятся мгновенно.

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

Но ... "100-кратная фора" лишила вас возможности рассматривать полный перебор

[Pavlovsky]

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

Интуитивно было понятно, что чем больше на линии точек, для которых $met=1$, тем позднее ее можно рассматривать при переборе. Странно, но этого простого соображения оказалось достаточно, хотя и планировался более глубокий анализ.

Пробовал несколько вариантов реализации этой идеи. Пока не пришел к выводу, что:

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

Простые числа упорядочены по возрастанию (если ищем решение-минимум). На каждом шаге выбираем минимально возможное простое число. Такая простая эвристика позволяет на каждом шаге выбирать простое число, которое сложнее всего получить заполнением доступных чисел. Тем самым облегчить задачу заполнения линий на завершающих шагах перебора.

Пусть косвенно, зато очень просто решает эту задачу. Ведь линии где много ячеек с весом 1, должны давать большую сумму. А значит по выше описанной эвристике будут рассматриваться на поздних этапах перебора.

[svb]

Pavlovsky

Цитата:

Может я где то пропустил. Опишите, плиз, свой алгоритм перебора.

Сортирую линии, затем последовательно заполняю числами с проверкой на простоту. Набор простых чисел меня не интересовал (я его не использовал). Это позволяет быстро выходить на $2N-1$ простых линий. При $N<8$ я использовал случайное перемешивание $M_i$ и повторял поиск.

Предварительно я собирался сей простой алгоритм использовать только для знакомства с ситуацией, но так и "застрял". При фиксированной схеме и заданном распределении $M_i$ уже при $N=6$ идет полный перебор за несколько секунд-минут. При $N>7$ любая случайная схема сразу дает решение, только при $N=8$ иногда можно наблюдать небольшое замедление процесса. При этом я еще не дошел до чисто технической оптимизации алгоритма.

Даже сортировку линий оставил упрощенную, хотя один раз попробовал иную - время работы резко увеличилось (при $N>7$). Вот, используемый вес линий:

function ves(l:integer):longint;
const p:array[1..4] of integer=(27000,900,30,1);
var k:integer;v:longint;
begin
  v:=0;
  case line[l,1] of
    0:for k:=0 to n-1 do v:=v+p[met[line[l,0],k]];
    1:for k:=0 to n-1 do v:=v+p[met[k,line[l,0]]];
    2:for k:=0 to n-1 do v:=v+p[met[(line[l,0]+k)mod n,k]];
    3:for k:=0 to n-1 do v:=v+p[met[(n+line[l,0]-k)mod n,k]];
  end;
  ves:=v;
end;

Возможно, динамическая сортировка была бы лучше - не знаю.

Пока нахожусь в полной растерянности, нужно все переписывать заново.

[Pavlovsky]

(Оффтоп)

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

"100-кратная фора" лишила вас возможности рассматривать полный перебор

Иногда завидую исследователям жившим в эпоху без компьютеров. Скажем Россер смог бы написать свою статью по дъявольским квадратам, если бы у него был компьютер?!

[svb]

Pavlovsky
Использование компьютера не столь трагично, просто добавляются новые задачи и расширяется экспериментальная база.

[whitefox]

(Оффтоп)

А как без компьютера решить задачу четырёх красок?

[Pavlovsky]

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

Сортирую линии, затем последовательно заполняю числами с проверкой на простоту.

Пробовал такой подход. Признал его неудачным. В подобных переборных задачах, на каждом шаге перебора, надо выбирать объект, который труднее всего построить. Наглядный пример, алгоритм построения пути шахматного коня по всем клеткам шахматной доски.

Цитата:

Простые числа упорядочены по возрастанию (если ищем решение-минимум). На каждом шаге выбираем минимально возможное простое число. Такая простая эвристика позволяет на каждом шаге выбирать простое число, которое сложнее всего получить заполнением доступных чисел. Тем самым облегчить задачу заполнения линий на завершающих шагах перебора.

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

[Nataly-Mak]

А кто-нибудь доказал, что результат 1758 для N=6 неулучшаем
Ведь там ещё уйма вариантов!
Для минимума 890, кажется, это сделал Gerbicz (если я правильно перевела его сообщение).

[Pavlovsky]

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

А кто-нибудь доказал, что результат 1758 для N=6 неулучшаем

Пробовал немного. Выставлялось максимум половина линий. Поэтому быстро бросил эту затею.

[svb]

Pavlovsky

Пробовал такой подход. Признал его неудачным. В подобных переборных задачах, на каждом шаге перебора, надо выбирать объект, который труднее всего построить. Наглядный пример, алгоритм построения пути шахматного коня по всем клеткам шахматной доски.

Эвристику шахматного коня недавно вспоминал Все это и вызывает у меня чувство, что наличие "конкурса" влияет хуже компьютера.
Nataly-Mak

Цитата:

А кто-нибудь доказал, что результат 1758 для N=6 неулучшаем
Ведь там ещё уйма вариантов!
Для минимума 890, кажется, это сделал Gerbicz (если я правильно перевела его сообщение).

Для 888 перебора по схемам не делал, а на случайных схемах, действительно, идет быстрая проверка отсутствия решения. В отношении результата 1758 требуется побольше усилий, но прежде, чем заняться проверкой, необходимо "вылизать" используемые алгоритмы.