2014 dxdy logo

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

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




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


25/08/12
171
Germany
Here is a table for 10^6 random pair swaps including update of the rawscore with 12d3's method. The first coordinate is N (<=100), the second the time in seconds. Its really $O(N)$.

{{5,0.45},{10,0.85},{15,1.27},{20,1.62},{30,2.40},{40,3.45},{50,4.00},{70, 5.57},{100,8.43}}

 Профиль  
                  
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение17.08.2019, 13:29 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Herbert Kociemba
Спасибо.

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


01/06/12
1016
Adelaide, Australia
Заканчиваются идеи. Думаю что еще новое можно придумать? Кто нибудь пробовал использовать маленькие оптимальные решения для нахождения больших решений. Допустим имеем решетку А=NхN, ее можно превратить в решетку B=(2N)x(2N) вот так:

Код:
4A[0][0]+0 4A[0][0]+1 | 4A[0][1]+0 4A[0][1]+1 ...
4A[0][0]+2 4A[0][0]+3 | 4A[0][1]+2 4A[0][1]+3 ...
-------------------------------------------------
4A[1][0]+0 4A[1][0]+1 | 4A[1][1]+0 4A[1][1]+1 ...
4A[1][0]+2 4A[1][0]+3 | 4A[1][1]+2 4A[1][1]+3 ...
...


Это даст решение но оно будет не очень хорошее, потому что 4A[0][0]+k (k=0..3) все слишком рядом. Поэтому можно например заменить 4A[0][0]+1 и 4A[0][0]+3 на противоположные 4(N*N-1-A[0][0])+1 и 4(N*N-1-A[0][0])+3. Теперь большая решетка выглядит так:

Код:
4A[0][0]+0 4(N*N-1-A[0][0])+1 | 4A[0][1]+0 4(N*N-1-A[0][1])+1 ...
4A[0][0]+2 4(N*N-1-A[0][0])+3 | 4A[0][1]+2 4(N*N-1-A[0][1])+3 ...
-------------------------------------------------
4A[1][0]+0 4(N*N-1-A[1][0])+1 | 4A[1][1]+0 4(N*N-1-A[1][1])+1 ...
4A[1][0]+2 4(N*N-1-A[1][0])+3 | 4A[1][1]+2 4(N*N-1-A[1][1])+3 ...
...


Это уже лучше. Но все равно 4A[0][0]+0 и 4A[0][0]+2 слишком рядом. Вот тут я застрял и не знаю как их красиво расставить подальше друг от друга?

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


04/03/09
906
У меня была идея такая. Если внимательно посмотреть на оптимальные решения, а точнее, отдельно на табличку из первых букв и табличку из вторых букв, то можно заметить, что почти всегда они представляют собой красивые регулярные паттерны. Почему так происходит - непонятно. Но тем не менее, можно сузить пространство позиций только до таких регулярных, и искать оптимальную тоже отжигом. Более того, если есть почти оптимальное решение, можно попробовать его "регуляризировать". Из небольших значений $N$ только $N=7$ немного выбивается из закономерности.

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


01/06/12
1016
Adelaide, Australia
12d3 в сообщении #1410932 писал(а):
Если внимательно посмотреть на оптимальные решения, а точнее, отдельно на табличку из первых букв и табличку из вторых букв, то можно заметить, что почти всегда они представляют собой красивые регулярные паттерны.

Хорошая идея. Какие то паттерны точно есть, но какие не пойму. Регулярность не всегда замечается особенно для больших $N$.

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


25/08/12
171
Germany
I also had some thoughts in this direction. If I set the points for example in the N=30 grid according to some structural rule I believe to observe - I do not use the evaluation function to set the points at all - it gives me a score > 0.95. Yet I am not sure if this is helpful.

 Профиль  
                  
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение21.08.2019, 17:07 


21/08/19
1
Germany
I wondered how Al Zimmermann calculated the table of lower bounds for the score, eg. for n=10: 902550.

If we calculate all n^2*(n^2-1)/2 distances and sort them, we get the row vector b.
b_rev is the same vector in reverse order, transposed. Then the lower bound is: b*b_rev.

This follows perfectly the rule, that high distances should be combined with low distances.
The lower bounds can be reached for n=2 and n=3. In these cases, the solutions have perfect symmetries.
For n>3, the lower bounds cannot be reached. We can observe some symmetries for n>3, but these
seem to be different for each n.

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


01/06/12
1016
Adelaide, Australia
sigi_s
I was wondering about the lower bounds too. Thank you for the clarification and welcome to our little discussion.

-- 22.08.2019, 20:59 --

Herbert Kociemba в сообщении #1411094 писал(а):
I do not use the evaluation function to set the points at all - it gives me a score > 0.95

That's a good starting point, but like you I am not sure that it will help you in finding the best solutions.

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


07/06/16
45
Омск
Что-то упал веб-сервер azspcs.com...

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


04/03/09
906
Due to temporary technical problems, the AZsPCs webiste cannot be reached via azspcs.com or azspcs.net. Until the technical problems are resolved, please use http://74.72.151.186 to reach the site.

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


07/06/16
45
Омск
12d3 в сообщении #1416154 писал(а):
please use http://74.72.151.186 to reach the site.

Thank you very much!

-- 20.09.2019, 16:00 --

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

 Профиль  
                  
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение25.09.2019, 11:36 


07/06/16
45
Омск
В оптимальных решениях есть абсолютная симметричность фигур, получающихся из преобразования строк и столбцов.
Другими словами, для оптимального решения существует преобразование поворота со сдвигом, совмещающее отображение строк с отображением столбцов исходной матрицы.

Например,
Изображение

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


07/06/16
45
Омск
На примере 5х5 ещё лучше видно:
Изображение
Если сдвинуть столбцы на 1 вправо и сделать поворот на 90° вправо, сдвинуть на один столбец вправо и отобразить вокруг вертикальной линии, то получим строки.
В решениях бóльшей размерности иногда нужно ещё сдвигать буквы по кругу A->B, B->C,..., E->A.

Это можно положить в основу алгоритма поиска...

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


25/08/12
171
Germany
In an "optimal" solution the coordinates of one cell uniquely determine the coordinates of three other cells. By starting the annealing process with a trivial default grid which has the desired symmetry and not swapping two points but two quadruples which respect the symmetry during the annealing process all grids generated have the desired symmetry of an "optimal solution". There is some increase in the perfomance proceeding in this way.

 Профиль  
                  
 
 Re: Al Zimmermann: Reversing Nearness
Сообщение18.10.2019, 13:59 


07/06/16
45
Омск
Чем больше копаюсь в задаче, тем больше удивляюсь. Казалось бы, причём тут число 17? Почему именно 17... :)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 50 ]  На страницу Пред.  1, 2, 3, 4  След.

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



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

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


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

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