Al Zimmerman - Delacorte Numbers

[Pavlovsky]

Одномерное число Делакорта

Вариант 1
Дана полоса из N ячеек. Заполнить ячейки числами от 1 до N. Правила вычисления числа Делакорта такие же как в конкурсной задаче.

Вариант 2
Дана полоса из N ячеек. Заполнить ячейки числами от 1 до N*N. В каждую ячейку помещаем N чисел. Правила вычисления числа Делакорта такие же как в конкурсной задаче.

[Pavlovsky]

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

Простые числа которые больше floor(N*N/2) можно ставить в середину квадрата.

В центр квадрата нужно ставить все простые числа. В самый центр 1 и больше floor(N*N/2). Остальные, чем меньше простое число тем ближе к центру.

Обоснование эвристики. Простые числа образуют группу для которых gcd(a,b)=1. Чем более плотную группу они образуют, тем больше больших расстояний останется для других чисел.

[Toucan]

Pavlovsky, предупреждение за неиспользование $\TeX$ при записи формул.

[dmd]

(немножко офтопа)

Пока идеи для алгоритма не хотят посещать, решил по-изучать, можно ли описать задачу на AMPL-языке. Оказалось можно! Даже удалось решить N3 солвером gecode. Попутно выяснилось, что данный язык матмоделирования жутко убог. В нём нет блока операторов, циклов for и while, не возможно описать собственную функцию. GCD описал как индексированный параметр, и чтоб его суметь применить пришлось по-изворачиваться.

[dimkadimon]

А у меня идеи кончились. Похоже что для следующего прогреса надо оптимизировать код (не знаю как) и гонять компьютер сутками чтобы увеличить бал хотя бы на 0.001. Это мне не хочется делать и поэтому задача надоела. Оставляю её пока не появятся хорошие идеи...

[Pavlovsky]

Возникли еще вспомогательные задачи.

Задача. Разбить числа из интервала [1...2k] на два подмножества по k чисел в каждом, так чтобы число Делакорта было максимальным. Если числа принадлежат разным подмножествам будем считать, что расстояние между ними 1. В противном случае растояние будет 0.

Задача. Дан квадрат сторона которого равна 1. В каждую вершину квадрата необходимо поместить k чисел из интервала [1...4k]. Найти решение с максимальным числом Делакорта.

[dmd]

(ещё о матмоделировании)

В AMPL кроме gecode задача решилась для N3 и N4 солвером localsolver. Но это не самое интересное. Я открыл для себя MiniZinc - свободный аналог AMPL. У него есть удобная среда моделирования MiniZinc IDE, и к нему также могут подключаться внешние солверы типа gecode.

[dimkadimon]

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

Возникли еще вспомогательные задачи.

Задача. Разбить числа из интервала [1...2k] на два подмножества по k чисел в каждом, так чтобы число Делакорта было максимальным. Если числа принадлежат разным подмножествам будем считать, что расстояние между ними 1. В противном случае растояние будет 0.

Задача. Дан квадрат сторона которого равна 1. В каждую вершину квадрата необходимо поместить k чисел из интервала [1...4k]. Найти решение с максимальным числом Делакорта.

Я не пробовал, но думаю смогу решить первую задачу почти оптимально для $2k<27^2$ методом отжига. Но я не вижу как это нам поможет решить оригинальную задачу. То есть, я вижу связь между задачами - первая задача как 1D аналог оригинальной задачи. Но решение упрощеного 1D варианта мало помогает решению 2D варианта имено потому что в 2D гораздо больше похожих вариантов расстоновки. Для 1D можно составить неплохое приблежение, ставим числа так: $(2k, k-1, 2k-4, ... ) (k, 2k-2, k-2, ... )$. Для каждого $2m$, $m$ лучше всего поставить в другое подмножество.

[Pavlovsky]

Наличие в формуле числа Делакорта квадрата расстояния, делает задачу нелинейной. Максимальная сумма достигается когда числа размещаются в вершинах квадрата. Соответственно оригинальную задачу можно решать в два этапа.
Этап 1. Сначала решаем задачу

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

Задача. Дан квадрат сторона которого равна 1. В каждую вершину квадрата необходимо поместить k чисел из интервала [1...4k]. Найти решение с максимальным числом Делакорта

Этап 2. Квадрат разбиваем на 4 зоны, в каждую входит одна вершина квадрата и ее окрестности. В каждой зоне размещаем числа одного из 4-х множеств полученных на первом этапе. Максимизируем число Делакорта.

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

Задача. Разбить числа из интервала [1...2k] на два подмножества по k чисел в каждом, так чтобы число Делакорта было максимальным. Если числа принадлежат разным подмножествам будем считать, что расстояние между ними 1. В противном случае растояние будет 0.

Эта задача имеет очень важное теоретическое значение. Меня прежде всего интересует, является ли она NP-полной?

[dmd]

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

Задача. Дан квадрат сторона которого равна 1. В каждую вершину квадрата необходимо поместить k чисел из интервала [1...4k]. Найти решение с максимальным числом Делакорта.

(MiniZinc модель)

include "globals.mzn";

int: k = 7;
set of int: I = 1..4;
set of int: J = 1..k;
set of int: N = 1..4*k;
array[I,J] of var N: X;

function var int: gcd(var int: x, var int: y) =
  let {
    int: p = min(ub(x),ub(y));
    var 1..p: g;
    constraint
      exists(i in 1..p)
        (x mod i = 0 /\ y mod i = 0 /\
          forall(j in i+1..p) (not(x mod j = 0 /\ y mod j = 0)) /\ g = i);
  } in g;

constraint alldifferent (i in I, j in J) (X[i,j]);

var int: DN =
  sum(ia,ib in I, ja,jb in J)
    (gcd(X[ia,ja],X[ib,jb])*(if (ia=1 /\ ib=4) \/ (ia=2 /\ ib=3) then 2 else 1 endif));

solve maximize DN;

output 
["k = ", show(k), "\n"] ++
["Delacorte Number = ", show(DN), "\n"] ++
["X = \n"] ++
[if j = 1 then "(" else "" endif ++
 show(X[i,j]) ++ if j = k then ")\n" else ", " endif | i in I, j in J] ++
[ "\n" ];

(решения)

k = 1
Delacorte Number = 27
X = 
(3)
(4)
(2)
(1)


k = 2
Delacorte Number = 126
X = 
(1, 3)
(2, 8)
(4, 7)
(6, 5)


k = 3
Delacorte Number = 325
X = 
(5, 3, 2)
(4, 12, 9)
(8, 11, 6)
(10, 1, 7)


k = 4
Delacorte Number = 614
X = 
(3, 6, 4, 8)
(2, 13, 1, 15)
(10, 5, 11, 9)
(7, 14, 16, 12)


k = 5
Delacorte Number = 983
X = 
(16, 3, 20, 14, 2)
(18, 17, 1, 11, 5)
(4, 10, 9, 13, 6)
(15, 19, 7, 8, 12)


k = 6
Delacorte Number = 1504
X = 
(19, 4, 16, 22, 17, 7)
(13, 10, 15, 18, 3, 14)
(20, 9, 5, 21, 2, 12)
(8, 11, 23, 6, 24, 1)


k = 7
Delacorte Number = 2066
X = 
(17, 19, 5, 10, 23, 7, 20)
(2, 18, 24, 3, 4, 6, 12)
(13, 1, 28, 11, 16, 14, 27)
(15, 8, 9, 26, 25, 22, 21)

Не факт, конечно, что решения полностью оптимальны. Решалось в версии 2.0.b4 внутренним солвером G12_lazyfd

-- Вт ноя 04, 2014 00:26:55 --

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

Задача. Разбить числа из интервала [1...2k] на два подмножества по k чисел в каждом, так чтобы число Делакорта было максимальным. Если числа принадлежат разным подмножествам будем считать, что расстояние между ними 1. В противном случае растояние будет 0.

(модель)

include "globals.mzn";

int: k = 8;
set of int: I = 1..2;
set of int: J = 1..k;
set of int: N = 1..2*k;
array[I,J] of var N: X;

function var int: gcd(var int: x, var int: y) =
  let {
    int: p = min(ub(x),ub(y));
    var 1..p: g;
    constraint
      exists(i in 1..p)
        (x mod i = 0 /\ y mod i = 0 /\
          forall(j in i+1..p) (not(x mod j = 0 /\ y mod j = 0)) /\ g = i);
  } in g;

constraint alldifferent (i in I, j in J) (X[i,j]);

var int: DN =
  sum(ia,ib in I, ja,jb in J)
    (gcd(X[ia,ja],X[ib,jb])*(if (ia!=ib) then 1 else 0 endif));

solve maximize DN;

output 
["k = ", show(k), "\n"] ++
["Delacorte Number = ", show(DN), "\n"] ++
["X = \n"] ++
[if j = 1 then "(" else "" endif ++
 show(X[i,j]) ++ if j = k then ")\n" else ", " endif | i in I, j in J] ++
[ "\n" ];

(решения)

k = 1
Delacorte Number = 2
X = 
(2)
(1)


k = 2
Delacorte Number = 10
X = 
(4, 3)
(2, 1)


k = 3
Delacorte Number = 26
X = 
(6, 4, 5)
(3, 2, 1)


k = 4
Delacorte Number = 48
X = 
(5, 6, 7, 8)
(4, 3, 2, 1)


k = 5
Delacorte Number = 82
X = 
(8, 5, 9, 3, 2)
(4, 7, 10, 6, 1)


k = 6
Delacorte Number = 126
X = 
(10, 8, 3, 11, 7, 12)
(4, 2, 6, 5, 9, 1)


k = 7
Delacorte Number = 158
X = 
(10, 14, 8, 6, 9, 4, 2)
(1, 7, 11, 5, 3, 12, 13)


k = 8
Delacorte Number = 236
X = 
(3, 16, 5, 4, 2, 15, 1, 14)
(12, 10, 13, 6, 9, 7, 8, 11)

[dmd]

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

(ib > ia \/ (ia = ib /\ jb > ja))

[dimkadimon]

Не уверен что правильно понял условия задач, но вот мои лучшие результаты:

(Оффтоп)

2 подмножества:
k=1, score=1: (1) (2)
k=2, score=5: (4 1) (2 3)
k=3, score=13: (3 4 2) (6 5 1)
k=4, score=24: (2 4 7 3) (8 1 6 5)
k=5, score=41: (2 10 3 8 7) (4 1 5 9 6)
k=6, score=63: (12 1 3 8 5 2) (10 11 7 9 6 4)
k=7, score=85: (8 10 12 9 11 1 7) (14 4 2 5 13 6 3)
k=8, score=120: (13 3 4 14 6 8 5 1) (12 15 11 16 2 7 9 10)
k=9, score=155: (16 9 2 11 13 5 7 12 6) (8 15 4 17 1 3 18 14 10)
k=10, score=195: (9 16 12 2 17 15 11 19 14 20) (13 18 1 3 7 5 4 10 6 8)

(Оффтоп)

4 подмножества. Тут растояния между противоположными углами равно $1^2+1^2=2$, а между остальными 1.
k=2, score=48: (1 8) (2 3) (4 7) (6 5)
k=3, score=126: (8 5 9) (1 2 12) (10 3 7) (6 4 11)
k=4, score=240: (12 14 16 5) (1 9 3 10) (4 7 8 6) (11 2 15 13)
k=5, score=390: (18 8 11 14 19) (12 13 10 17 15) (9 16 4 2 7) (6 1 5 20 3)
k=6, score=596: (15 2 23 8 18 17) (20 3 19 7 22 24) (5 14 4 6 9 13) (1 11 21 12 16 10)
k=7, score=842: (1 18 15 4 7 24 20) (26 19 2 27 17 11 28) (6 3 12 16 10 21 5) (13 9 23 25 22 14 8)
k=8, score=1116: (1 30 24 4 11 9 31 32) (7 2 6 13 25 10 27 28) (16 3 8 15 12 19 23 22) (14 26 29 5 17 21 18 20)
k=9, score=1502: (24 13 10 1 32 19 21 2 28) (22 6 11 17 27 18 31 20 15) (29 8 7 14 35 26 12 16 3) (33 9 5 23 30 4 36 34 25)
k=10, score=1876: (40 26 37 27 25 2 32 39 30 1) (19 28 18 33 8 34 3 5 7 12) (22 23 16 10 31 9 13 15 6 20) (35 14 24 21 36 17 11 29 38 4)

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

[Pavlovsky]

У меня уже для N=6 не оптимальное решение. Поэтому экспериментально проверить гипотезу затруднительно. Но мое лучшее решение для N=6 имеет k=9, score=1502. Впрочем это понятно, оно было получено по алгоритму в два этапа.

Для N=4 лучшее решение (оптимальное) имеет k=4, score=240.

Так что доводы в пользу двух-этапного алгоритма есть!

[dmd]

(про LocalSolver)

Оказывается LocalSolver решает модели над бинарным полем переменных. Он может и обычные модели решать, но авторы настоятельно советуют перевести все переменные в булевы. Там на сайте есть то ли утверждение, то ли предположение (не сумел понять), что бинаризация модели линеаризует нелинейности! Количество переменных увеличивается кратно, но якобы трудность проблемы для солвера становится легче.

[dmd]

(Оффтоп)

Интересно. Перевёл модель в бинарную и N3 решилось. Действительно, бинарная модель выглядит гармоничнее числовой, особенно в данном случае ограничение alldifferent. К сожалению, дальше проверить не могу, т.к. триальный солвер ограничен сотней переменных. Для N4 уже нужно 256 переменных. Попробую аналогично модель задачи описать в MiniZinc.