Al Zimmermann: Reversing Nearness

[dimkadimon]

Стартовало новое соревнование Al Zimmermann. Задачу можно обсуждать тут, но нельзя показывать конкретные решения. Желаю всем удачи!

http://azspcs.com/Contest/Nearness

[dimkadimon]

Забавная задача. Пока оптимальные решения тяжело даются, нашел только $n=6$. Подсчет оценки решения занимает много времени так как он $O(n^4)$. Надо как то ускорить.

Уже появились сильные Россияне (Александр и Сеня). Надеюсь они присоединятся к нашей беседе.

[dimkadimon]

Гмм... никто не пишет...

Нашел первые 11 оптимальных решений. Суть метода это быстрый подсчет оценки решения. Посмотрим как пойдет дальше.

[ctac]

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

Гмм... никто не пишет...

Нашел первые 11 оптимальных решений. Суть метода это быстрый подсчет оценки решения. Посмотрим как пойдет дальше.

Быстрая оценка это конечно важно. Но для того чтобы найти оптимальное решение вы делаете полный перебор?

[dimkadimon]

ctac, нет полный перебор я не делаю. Оптимальность только в смысле что это лучшее решение на данный момент.

[12d3]

Пока удалось получить только 5 оптимальных решений. Как-то очень туго процесс идет, в голову не приходит никаких идей, кроме как менять местами фишки, по две, по три, по четыре, пока не свалишься в локальный минимум. И даже то, что на подсчет оценки одного решения тратится $O(1)$ времени, не сильно помогает.

[ctac]

12d3 в сообщении #1408763 писал(а):

Пока удалось получить только 5 оптимальных решений. Как-то очень туго процесс идет, в голову не приходит никаких идей, кроме как менять местами фишки, по две, по три, по четыре, пока не свалишься в локальный минимум. И даже то, что на подсчет оценки одного решения тратится $O(1)$ времени, не сильно помогает.

Перебор дал мне тоже только 5 оптимальных решений. dimkadimon применяет, наверное, метод имитации отжига, но я еще не просек как это применить в данной задаче

[jcmeyrignac]

The contest is difficult, because the solutions seem unique.

Is it possible to find two different grids that have the same score ?

[dimkadimon]

12d3 в сообщении #1408763 писал(а):

что на подсчет оценки одного решения тратится $O(1)$ времени, не сильно помогает

Круто! Это точно должно помочь, если конечно вы не тратите много времени на обновление решения.

jcmeyrignac в сообщении #1408933 писал(а):

dimkadimon применяет, наверное, метод имитации отжига, но я еще не просек как это применить в данной задаче

Абсолютно верно. Метод отжига можно легко применить к любой задаче и я почти всегда им пользуюсь.

-- 06.08.2019, 21:39 --

jcmeyrignac в сообщении #1408933 писал(а):

Is it possible to find two different grids that have the same score ?

Yes. I was able to produce two optimal 6x6 grids that have a different normalised representation when submitted to the site.

[12d3]

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

Круто! Это точно должно помочь, если конечно вы не тратите много времени на обновление решения.

Это если не использовать отжиг. Тогда я пачку из $N^4$ позиций обсчитываю за $N^4$ времени. С отжигом позиции приходится по одной обсчитывать, и тогда получается $O(N)$ на одну позицию, быстрее не выходит.

[dimkadimon]

12d3 в сообщении #1408957 писал(а):

Это если не использовать отжиг. Тогда я пачку из $N^4$ позиций обсчитываю за $N^4$ времени. С отжигом позиции приходится по одной обсчитывать, и тогда получается $O(N)$ на одну позицию, быстрее не выходит.

Так это тоже быстро! С отжигом меняется только то что надо обновлять решетку. Если я вас правильно понял, то $N$ это ширина решетки, а $N^4$ это например все возможные позиции после обмена двух клеток? У меня с отжигом только $O(N^2)$ для одной позиции. Был вариант с проверкой в $О(1)$, но там обновление стоило $O(N^6)$, поэтому не было смысла. Мне ваша скорость даже не снилась!

[Herbert Kociemba]

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

У меня с отжигом только $O(N^2)$ для одной позиции.

And I would be very surprised if swapping of two entries would cause less than $O(N^2)$ operations for the update of the rawscore. I use annealing just by swapping random pairs and till now it gives pretty good results.

[12d3]

Пусть $N$ - размер решетки, $x_{ij}$ и $y_{ij}$ - исходные координаты фишки, стоящей на позиции $(i,j)$, и обозначим $d(a, b) = min(|a-b|, N-|a-b|)^2$.
Тогда оценка для фишки с координатами $(i_0,j_0)$ равна $\displaystyle F(i_0,j_0) = \sum\limits_{i=1}^N \sum\limits_{j=1}^N\left( d(i_0,i) + d(j_0,j)\right)\left( d(x_{i_0j_0},x_{i,j}) + d(y_{i_0j_0},y_{i,j}) \right) = \sum\limits_{i=1}^N \sum\limits_{j=1}^N d(i_0i) d(x_{i_0j_0},x_{ij}) + \sum\limits_{i=1}^N \sum\limits_{j=1}^N d(j_0j) d(x_{i_0j_0},x_{ij}) + \sum\limits_{i=1}^N \sum\limits_{j=1}^N d(i_0i) d(y_{i_0j_0},y_{ij}) + \sum\limits_{i=1}^N \sum\limits_{j=1}^N d(j_0j) d(y_{i_0j_0},y_{ij}) $
Рассмотрим первое слагаемое $\displaystyle \sum\limits_{i=1}^N \sum\limits_{j=1}^N d(i_0,i) d(x_{i_0j_0},x_{i,j}) = \sum\limits_{i=1}^N d(i_0,i) \sum\limits_{j=1}^N d(x_{i_0j_0},x_{ij}) $
Если мы заранее вычислим суммы $\displaystyle \sum\limits_{j=1}^N d(x_{i_0j_0},x_{ij}) $ для всех возможных значений $i$ и для всех возможных значений $x_{i_0 j_0}$ (это можно сделать за $O(N^3)$), то для вычисления $\displaystyle \sum\limits_{i=1}^N \sum\limits_{j=1}^N d(i_0,i) d(x_{i_0j_0},x_{i,j}) $ нам понадобится всего $O(N)$ времени. То же самое можно сделать и с остальными тремя слагаемыми. Итого, для подсчета оценки после обмена двух фишек нам потребуется $O(N)$ времени.
Дальше, если мы поменяли две фишки местами, то нужно обновить значения сумм $\displaystyle \sum\limits_{j=1}^N d(x_{i_0j_0},x_{ij}) $. И это тоже можно сделать за $O(N)$.
Итого, перед началом отжига нам нужно потратить $O(N^3)$ времени, а потом на каждый шаг тратится $O(N)$. Ну и кроме того, такой метод позволяет найти оценку произвольной расстановки тоже за $O(N^3)$.

[Herbert Kociemba]

12d3 в сообщении #1409284 писал(а):

Дальше, если мы поменяли две фишки местами, то нужно обновить значения сумм $\displaystyle \sum\limits_{j=1}^N d(x_{i_0j_0},x_{ij}) $. И это тоже можно сделать за $O(N)$.

Thank you for your detailed explanation. I agree with most of it but am not sure about the update of the sums. If you swap for example the entries in (1,2) and (3,4) the above sums change for i=1and i=3 and for all $i_0$ and $j_0$. So you would have to update 2*N^2 sums.

[12d3]

Herbert Kociemba в сообщении #1409372 писал(а):

If you swap for example the entries in (1,2) and (3,4) the above sums change for i=1and i=3 and for all $i_0$ and $j_0$.

Пара $(i_0,j_0)$ может принимать $N^2$ различных значений, но $x_{i_0j_0}$ принимает только $N$ различных значений. То есть все значения сумм $\displaystyle \sum\limits_{j=1}^N d(x_{i_0j_0},x_{ij}) $ можно хранить двумерном массиве $N\times N$, а не в трехмерном, и при обновлении этого массива изменяются только две строки.