Al Zimmermann: Reversing Nearness

[Herbert Kociemba]

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

[whitefox]

Herbert Kociemba
Спасибо.

[dimkadimon]

Заканчиваются идеи. Думаю что еще новое можно придумать? Кто нибудь пробовал использовать маленькие оптимальные решения для нахождения больших решений. Допустим имеем решетку А=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 слишком рядом. Вот тут я застрял и не знаю как их красиво расставить подальше друг от друга?

[12d3]

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

[dimkadimon]

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

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

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

[Herbert Kociemba]

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.

[sigi_s]

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.

[dimkadimon]

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.

[Archimedes]

Что-то упал веб-сервер azspcs.com...

[12d3]

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.

[Archimedes]

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

please use http://74.72.151.186 to reach the site.

Thank you very much!

-- 20.09.2019, 16:00 --

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

[Archimedes]

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

Например,

[Archimedes]

На примере 5х5 ещё лучше видно:

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

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

[Herbert Kociemba]

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.

[Archimedes]

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