2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2, 3, 4  След.
 
 Al Zimmermann: Reversing Nearness
Сообщение28.07.2019, 04:43 
Аватара пользователя
Стартовало новое соревнование Al Zimmermann. Задачу можно обсуждать тут, но нельзя показывать конкретные решения. Желаю всем удачи!

http://azspcs.com/Contest/Nearness

 
 
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение28.07.2019, 16:20 
Аватара пользователя
Забавная задача. Пока оптимальные решения тяжело даются, нашел только $n=6$. Подсчет оценки решения занимает много времени так как он $O(n^4)$. Надо как то ускорить.

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

 
 
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение03.08.2019, 17:15 
Аватара пользователя
Гмм... никто не пишет...

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

 
 
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение03.08.2019, 19:51 
dimkadimon в сообщении #1408514 писал(а):
Гмм... никто не пишет...

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


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

 
 
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение04.08.2019, 03:27 
Аватара пользователя
ctac, нет полный перебор я не делаю. Оптимальность только в смысле что это лучшее решение на данный момент.

 
 
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение05.08.2019, 00:53 
Пока удалось получить только 5 оптимальных решений. Как-то очень туго процесс идет, в голову не приходит никаких идей, кроме как менять местами фишки, по две, по три, по четыре, пока не свалишься в локальный минимум. И даже то, что на подсчет оценки одного решения тратится $O(1)$ времени, не сильно помогает.

 
 
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение05.08.2019, 12:58 
12d3 в сообщении #1408763 писал(а):
Пока удалось получить только 5 оптимальных решений. Как-то очень туго процесс идет, в голову не приходит никаких идей, кроме как менять местами фишки, по две, по три, по четыре, пока не свалишься в локальный минимум. И даже то, что на подсчет оценки одного решения тратится $O(1)$ времени, не сильно помогает.


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

 
 
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение06.08.2019, 10:23 
The contest is difficult, because the solutions seem unique.

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

 
 
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение06.08.2019, 15:50 
Аватара пользователя
12d3 в сообщении #1408763 писал(а):
что на подсчет оценки одного решения тратится $O(1)$ времени, не сильно помогает

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

jcmeyrignac в сообщении #1408933 писал(а):
dimkadimon применяет, наверное, метод имитации отжига, но я еще не просек как это применить в данной задаче :cry:

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

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

 
 
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение06.08.2019, 16:24 
dimkadimon в сообщении #1408956 писал(а):
Круто! Это точно должно помочь, если конечно вы не тратите много времени на обновление решения.

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

 
 
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение07.08.2019, 14:13 
Аватара пользователя
12d3 в сообщении #1408957 писал(а):
Это если не использовать отжиг. Тогда я пачку из $N^4$ позиций обсчитываю за $N^4$ времени. С отжигом позиции приходится по одной обсчитывать, и тогда получается $O(N)$ на одну позицию, быстрее не выходит.

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

 
 
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение08.08.2019, 17:38 
Аватара пользователя
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.

 
 
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение08.08.2019, 18:29 
Пусть $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)$.

 
 
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение09.08.2019, 01:17 
Аватара пользователя
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.

 
 
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение09.08.2019, 01:30 
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$, а не в трехмерном, и при обновлении этого массива изменяются только две строки.

 
 
 [ Сообщений: 50 ]  На страницу 1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group