Al Zimmermann: Reversing Nearness : Олимпиадные задачи (CS) fixfix
2014 dxdy logo

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

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




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


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

http://azspcs.com/Contest/Nearness

 Профиль  
                  
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение28.07.2019, 16:20 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение03.08.2019, 17:15 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Гмм... никто не пишет...

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

 Профиль  
                  
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение03.08.2019, 19:51 


09/03/16
34
dimkadimon в сообщении #1408514 писал(а):
Гмм... никто не пишет...

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


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

 Профиль  
                  
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение04.08.2019, 03:27 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение05.08.2019, 00:53 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение05.08.2019, 12:58 


09/03/16
34
12d3 в сообщении #1408763 писал(а):
Пока удалось получить только 5 оптимальных решений. Как-то очень туго процесс идет, в голову не приходит никаких идей, кроме как менять местами фишки, по две, по три, по четыре, пока не свалишься в локальный минимум. И даже то, что на подсчет оценки одного решения тратится $O(1)$ времени, не сильно помогает.


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

 Профиль  
                  
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение06.08.2019, 10:23 


20/01/13
62
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 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
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 
Заслуженный участник


04/03/09
915
dimkadimon в сообщении #1408956 писал(а):
Круто! Это точно должно помочь, если конечно вы не тратите много времени на обновление решения.

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

 Профиль  
                  
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение07.08.2019, 14:13 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
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 
Аватара пользователя


25/08/12
171
Germany
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 
Заслуженный участник


04/03/09
915
Пусть $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 
Аватара пользователя


25/08/12
171
Germany
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 
Заслуженный участник


04/03/09
915
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  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group