AZsPCs: Hexagonal Neighbors

[grizzly]

FomaNeverov в сообщении #1354973 писал(а):

хотя я проблем не вижу

Проблема с английским: problem здесь переводится как "задача" (для $n=4$).

[FomaNeverov]

66 место.

[dimkadimon]

FomaNeverov в сообщении #1355100 писал(а):

66 место.

Поздравляю это хороший результат!

[Herbert Kociemba]

Does anyone else has results up to which N the scores are *really* optimal? Up to N=7 they are if my program logic is correct. N=8 may already take too long to show - but I did not try yet.

[dimkadimon]

Добрался до 48ого места, а вот что дальше делать не понятно. Пока что использовал достаточно стандартные методы: метод отжига и наращивание меньших решеток.

[dimkadimon]

Как я ожидал Tomas Rokicki занял первое место - настоящий гений!

[Herbert Kociemba]

Stuck for almost a week I yesterday gave simulated annealing a try and it works quite well for N=11 and 12. Still far from giving the best known solutions I could push my results from 888 to 896 (N=11) and from 1070 to 1081 (N=12). It is fascinating to observe how at least the "1" magically arrange into a hexagonal pattern, here a small section from a N=12 result when cooling to temperature T=0.

[dimkadimon]

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

Stuck for almost a week I yesterday gave simulated annealing a try and it works quite well for N=11 and 12. Still far from giving the best known solutions I could push my results from 888 to 896 (N=11) and from 1070 to 1081 (N=12). It is fascinating to observe how at least the "1" magically arrange into a hexagonal pattern, here a small section from a N=12 result when cooling to temperature T=0.

Oh I didn't realise that there were any other approaches possible other than simulated annealing? For N=11 I can almost reach the optimal, but for N=12 my score is the same.

[Herbert Kociemba]

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

Oh I didn't realise that there were any other approaches possible other than simulated annealing? For N=11 I can almost reach the optimal, but for N=12 my score is the same.

Yes, my previous approach for N>10 was a semiconstructional approach with an "ideal" borderless grid (dobrichev gives an example) as model. In this way you can get more than 24.7 points without extensive computation.

But yes, I think simulated annealing is a good path to follow and I will see how it works for larger grids. Meanwhile I reached 1084 for N=12 in this way. A central role is the definition of the "energy" of the grid and how "energy" changes if two cells are swapped. I suppose there are different possibilities here and the method used may have an impact on the quality of the solutions.

[dimkadimon]

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

Yes, my previous approach for N>10 was a semiconstructional approach with an "ideal" borderless grid (dobrichev gives an example) as model. In this way you can get more than 24.7 points without extensive computation.

This is very impressive Herbert. I wasn't able to achieve anything as good as that using dobrichev's grid.

[dimkadimon]

А кто нибудь пробовал использовать симметричные решения? Я думал что это идея даст мне хорошие результаты (в районе 24.9), но когда попробовал был сильно расстроен. Результаты хуже обычных несимметричных решений. Хотя теоретически идея хорошая и должна ускорить поиск во много раз. Возможно надо найти правильную симметрию? Пока я пробовал только зеркально отображение.

[ctac]

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

А кто нибудь пробовал использовать симметричные решения?

А что именно имеется ввиду?

[dimkadimon]

ctac в сообщении #1359668 писал(а):

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

А кто нибудь пробовал использовать симметричные решения?

А что именно имеется ввиду?

Это такие решения где есть четкая симметрия. Например можно вот так сделать для N=3:

..a b c
.d e f g
i j k j i
.g f e d
..c b a

Размер поиска сокращается от $7^{19}$ до $7^{10}$.

[ctac]

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

ctac в сообщении #1359668 писал(а):

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

А кто нибудь пробовал использовать симметричные решения?

А что именно имеется ввиду?

Это такие решения где есть четкая симметрия. Например можно вот так сделать для N=3:

..a b c
.d e f g
i j k j i
.g f e d
..c b a

Размер поиска сокращается от $7^{19}$ до $7^{10}$.

Это симметрия относительно центра в "к" или все же зеркальная? По идее все хорошие решения действительно должны быть симметричны, но почему-то так не получается.

[dimkadimon]

ctac в сообщении #1359751 писал(а):

Это симметрия относительно центра в "к" или все же зеркальная? По идее все хорошие решения действительно должны быть симметричны, но почему-то так не получается.

Симметрия зеркальная, а к центр симметрии. Можно было и по другому сделать, например

..a b c
.d e f g
i j k l m
.d e f g
..a b c