Al Zimmerman - Delacorte Numbers

[Pavlovsky]

dmd в сообщении #940848 писал(а):

Две входные двумерные таблицы GCD и квадратов расстояний можно объединить в одну четырёх-мерную "таблицу"

Этот метод описан в статье

Цитата:

квадратичной задаче о назначениях

. Как я понял он не самый лучший.

Но whitefox говорит об использовании специфики задачи при лианеризации. Подождем, может расколется?!

[Yadryara]

Pavlovsky в сообщении #940575 писал(а):

Мои эксперименты с весовой функцией показывают, что каждое число, в соответствии с весом, может находиться в трех кругах с последовательными номерами. Причем три круга это с большим запасом. Например числа 48,42,36 могут находиться в кругах 9,8 (хотя у меня нет примеров хороших решений, где эти числа находятся в круге 8). То есть нахождение числа не в рекомендуемом круге это достаточно редкое исключение.

Я тоже занимался этими подсчётами. Правда, называл их не кругами, а областями. В этих областях, как правило, 4 или 8 клеток.

Каждая область имеет свой рейтинг. Посчитать его можно, например, через сумму квадратов дистанций от каждой отдельно взятой клетки до всех остальных клеток. Для упрощения все рейтинги каждого квадрата разделил на НОД всех чисел того же квадрата.

$\tikz[scale=.06]{ \draw(0,0)--(0,30)--(30,30)--(30,0)--(0,0); \draw(0,10)--(30,10); \draw(0,20)--(30,20); \draw(10,0)--(10,30); \draw(20,0)--(20,30); \node at (15,25)[green!40!brown!200]{\large \textbf{10\quad\, 10}}; \node at (15,25){\large \textbf{7}}; \node at (15,15){\large \textbf{7\qquad 7}}; \node at (15,15)[red!60!blue]{\large \textbf{4}}; \node at (15,5)[green!40!brown!200]{\large \textbf{10\quad\, 10}}; \node at (15,5){\large \textbf{7}}; \draw(50,0)--(50,40)--(90,40)--(90,0)--(50,0); \draw(50,10)--(90,10); \draw(50,20)--(90,20); \draw(50,30)--(90,30); \draw(60,0)--(60,40); \draw(70,0)--(70,40); \draw(80,0)--(80,40); \node at (70,35)[green!40!brown!200]{\large \textbf{7\qquad\quad\, 7}}; \node at (70,25){\large \textbf{5\qquad\quad\, 5}}; \node at (70,15){\large \textbf{5\qquad\quad\, 5}}; \node at (70,5)[green!40!brown!200]{\large \textbf{7\qquad\quad\, 7}}; \node at (70,35){\large \textbf{5\;\, 5}}; \node at (70,5){\large \textbf{5\;\, 5}}; \node at (70,25)[red!60!blue]{\large \textbf{3\;\, 3}}; \node at (70,15)[red!60!blue]{\large \textbf{3\;\, 3}}; \draw(110,0)--(110,50)--(160,50)--(160,0)--(110,0); \draw(110,10)--(160,10); \draw(110,20)--(160,20); \draw(110,30)--(160,30); \draw(110,40)--(160,40); \draw(120,0)--(120,50); \draw(130,0)--(130,50); \draw(140,0)--(140,50); \draw(150,0)--(150,50); \node at (135,45)[green!40!brown!200]{\large \textbf{12\qquad\qquad 12}}; \node at (135,45){\large \textbf{9\qquad 9}}; \node at (135,45)[orange!80!brown!140]{\large \textbf{8}}; \node at (135,35){\large \textbf{9\qquad\qquad\, 9}}; \node at (135,35)[blue]{\large \textbf{6\qquad 6}}; \node at (135,35)[brown!200]{\large \textbf{5}}; \node at (135,25)[red!60!blue]{\large \textbf{4}}; \node at (135,25)[orange!80!brown!140]{\large \textbf{8\qquad\qquad\, 8}}; \node at (135,25)[brown!200]{\large \textbf{5\qquad 5}}; \node at (135,15){\large \textbf{9\qquad\qquad\, 9}}; \node at (135,15)[blue]{\large \textbf{6\qquad 6}}; \node at (135,15)[brown!200]{\large \textbf{5}}; \node at (135,5)[green!40!brown!200]{\large \textbf{12\qquad\qquad 12}}; \node at (135,5){\large \textbf{9\qquad 9}}; \node at (135,5)[orange!80!brown!140]{\large \textbf{8}}; \draw(180,0)--(180,60)--(240,60)--(240,0)--(180,0); \draw(180,10)--(240,10); \draw(180,20)--(240,20); \draw(180,30)--(240,30); \draw(180,40)--(240,40); \draw(180,50)--(240,50); \draw(190,0)--(190,60); \draw(200,0)--(200,60); \draw(210,0)--(210,60); \draw(220,0)--(220,60); \draw(230,0)--(230,60); \node at (210,55)[green!40!brown!200]{\large \textbf{55\qquad\qquad\;\;\;\, 55}}; \node at (210,55){\large \textbf{43\quad\quad\;\, 43}}; \node at (210,55)[orange!80!brown!140]{\large \textbf{37 37}}; \node at (210,45){\large \textbf{43\qquad\qquad\;\;\;\, 43}}; \node at (210,45)[blue]{\large \textbf{31\quad\quad\;\, 31}}; \node at (210,45)[brown!200]{\large \textbf{25 25}}; \node at (210,35)[orange!80!brown!140]{\large \textbf{37\qquad\qquad\;\;\;\, 37}}; \node at (210,35)[brown!200]{\large \textbf{25\quad\quad\;\, 25}}; \node at (210,35)[red!60!blue]{\large \textbf{19 19}}; \node at (210,25)[orange!80!brown!140]{\large \textbf{37\qquad\qquad\;\;\;\, 37}}; \node at (210,25)[brown!200]{\large \textbf{25\quad\quad\;\, 25}}; \node at (210,25)[red!60!blue]{\large \textbf{19 19}}; \node at (210,15){\large \textbf{43\qquad\qquad\;\;\;\, 43}}; \node at (210,15)[blue]{\large \textbf{31\quad\quad\;\, 31}}; \node at (210,15)[brown!200]{\large \textbf{25 25}}; \node at (210,5)[green!40!brown!200]{\large \textbf{55\qquad\qquad\;\;\;\, 55}}; \node at (210,5){\large \textbf{43\quad\quad\;\, 43}}; \node at (210,5)[orange!80!brown!140]{\large \textbf{37 37}}; }$


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

Для 3-го порядка — 1 исключение.
Для 5-го порядка — 3 исключения. Но если считать вес по-старому, тогда 2 исключения.

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


$\tikz[scale=.06]{ \draw(0,0)--(0,30)--(30,30)--(30,0)--(0,0); \draw(0,10)--(30,10); \draw(0,20)--(30,20); \draw(10,0)--(10,30); \draw(20,0)--(20,30); \node at (15,25){\large \textbf{13\quad\, 11}}; \node at (25,15){\large \textbf{7}}; \node at (14,5){\large \textbf{11\quad\;\; 9}}; \node at (15,5){\large \textbf{7}}; \draw(50,0)--(50,40)--(90,40)--(90,0)--(50,0); \draw(50,10)--(90,10); \draw(50,20)--(90,20); \draw(50,30)--(90,30); \draw(60,0)--(60,40); \draw(70,0)--(70,40); \draw(80,0)--(80,40); \node at (70,35){\large \textbf{94 69 70 97}}; \node at (70,25){\large \textbf{69 44 \quad 72}}; \node at (70,15){\large \textbf{70\quad\quad\;\, 73}}; \node at (65,5){\large \textbf{97 72 73}}; \node at (85,5){\textbf{100}}; \draw(110,0)--(110,50)--(160,50)--(160,0)--(110,0); \draw(110,10)--(160,10); \draw(110,20)--(160,20); \draw(110,30)--(160,30); \draw(110,40)--(160,40); \draw(120,0)--(120,50); \draw(130,0)--(130,50); \draw(140,0)--(140,50); \draw(150,0)--(150,50); \node at (135,45){\large \textbf{64\qquad\qquad 64}}; \node at (135,45){\large \textbf{49 44 49}}; \node at (135,35){\large \textbf{49 34\quad\, 34 49}}; \node at (135,25){\large \textbf{44\qquad\qquad 44}}; \node at (135,15){\large \textbf{49 34\quad\, 34 49}}; \node at (135,5){\large \textbf{64\qquad\qquad 64}}; \node at (135,5){\large \textbf{49 44 49}}; \draw(180,0)--(180,60)--(240,60)--(240,0)--(180,0); \draw(180,10)--(240,10); \draw(180,20)--(240,20); \draw(180,30)--(240,30); \draw(180,40)--(240,40); \draw(180,50)--(240,50); \draw(190,0)--(190,60); \draw(200,0)--(200,60); \draw(210,0)--(210,60); \draw(220,0)--(220,60); \draw(230,0)--(230,60); \node at (210,55){\text{603\,478\,415\,414\,475\,598}}; \node at (210,45){\text{476\,351\qquad287\,348\,471}}; \node at (210,35){\text{411\,286 \qquad\quad\,283\,406}}; \node at (210,25){\text{408\,283 \qquad\quad\,280\,403}}; \node at (210,15){\text{467\,342\,279\,278\,339\,462}}; \node at (210,5){\text{588\,463\,400\,399\,460\,583}}; }$

Кстати, чем тяжелее число, тем оно, как правило, лучше соответствует рейтингу в максимальной расстановке.

Полагаю, вполне возможно качественное улучшение этого рейтинга.

[sevir]

alexBlack в сообщении #931334 писал(а):

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

Хорошо, вот мои лучшие результаты ...

У меня десятка чуть больше 238205/593283.

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

[dimkadimon]

sevir в сообщении #941714 писал(а):

alexBlack в сообщении #931334 писал(а):

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

Хорошо, вот мои лучшие результаты ...

У меня десятка чуть больше 238205/593283.

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

Поздравляю, возможно это рекорд. Кстати спасибо за информацию.

[Herbert Kociemba]

sevir в сообщении #941714 писал(а):

alexBlack в сообщении #931334 писал(а):

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

Хорошо, вот мои лучшие результаты ...

У меня десятка чуть больше 238205/593283.

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

max 298861 for N=9 and max 593350 for N=10 is possible.

[sevir]

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

max 298861 for N=9 and max 593350 for N=10 is possible.

Спасибо: у меня близкие результаты, но у Вас лучше - я только что запустил новый алгоритм. А Вы минимумами не поделитесь: я за них еще и не брался.

[Yadryara]

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

max 298861 for N=9 and max 593350 for N=10 is possible.

Однако. Я-то думал, что вся борьба лидеров, в числе которых и Herbert Kociemba, идёт на уровне 27-го порядка.

Раз для 10-го порядка возможны улучшения, то, видимо, результаты для 27-го порядка тем более далеки от оптимальных.

[Herbert Kociemba]

Yadryara в сообщении #941775 писал(а):

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

max 298861 for N=9 and max 593350 for N=10 is possible.

Однако. Я-то думал, что вся борьба идёт на уровне 27-го порядка. Раз для 10-го порядка возможны улучшения, то, видимо, результаты для 27-го порядка тем более далеки от оптимальных.

And I have exactly the opposite opinion. For small N you get stuck in some bad local minimum/maximum most of the time. N=27 behaves much "smoother". The relative distance from the local minimum/maximum where you get stuck to the optimal solutions seems to be much smaller.

[sevir]

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

Yadryara в сообщении #941775 писал(а):

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

max 298861 for N=9 and max 593350 for N=10 is possible.

Однако. Я-то думал, что вся борьба идёт на уровне 27-го порядка. Раз для 10-го порядка возможны улучшения, то, видимо, результаты для 27-го порядка тем более далеки от оптимальных.

And I have exactly the opposite opinion. For small N you get stuck in some bad local minimum/maximum most of the time. N=27 behaves much "smoother". The relative distance from the local minimum/maximum where you get stuck to the optimal solutions seems to be much smaller.

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

[jcmeyrignac]

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

I thought a lot about these 5 circles. I think I found them, but not sure if I found the correct ones. Here are the circles I found for N=27 MAX:

Exactly !!!
Though your N=27 circles seem a little bit too perfect for me.
Mine have a few cells in the wrong circles.

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

max 298861 for N=9 and max 593350 for N=10 is possible.

Still not optimal !

[jcmeyrignac]

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

I thought a lot about these 5 circles. I think I found them, but not sure if I found the correct ones. Here are the circles I found for N=27 MAX:

In fact, my circles are a little bit different.
Here is our Max27:
333333332223333223222334334
333323323232323231233333433
343322332222222222333233342
233333332222222222213323343
323322222222222222222323332
233332222222222212222123332
332322221222212222222222233
333212222220000222222223223
322122222200000002122212233
321222221000000000022222232
332222220000000000022222232
322222201000000000022222223
222222200000000000002222233
222222200000000000002222222
312222200000000000002222223
222222200000000000002212222
332222220000000000022212233
232222210000000000022222323
222222222000000000222222222
323222222220000222222223332
322322222212222222222222333
233332222222222212222233322
432333222222122222222223223
333332322222221221223332333
233333333222222222323233234
334332331322222233323333334
433432333223333233223233333

[dimkadimon]

sevir в сообщении #941714 писал(а):

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

Как я понял у вас максимум 5934хх? Но потом вы говорите что "Спасибо: у меня близкие результаты, но у Вас лучше - я только что запустил новый алгоритм."...

[dmd]

(dimkadimon)

В русском языке "четвертая сотня" это 5933хх, девятнадцатый век это 18ХХ

[dimkadimon]

dmd в сообщении #942332 писал(а):

(dimkadimon)

В русском языке "четвертая сотня" это 5933хх, девятнадцатый век это 18ХХ

Спасибо, теперь понятно.

-- 08.12.2014, 16:08 --

jcmeyrignac в сообщении #941924 писал(а):

In fact, my circles are a little bit different.

I think your 0th circle is my 1st and 2nd circles combined. Your 1st and 2nd circles are perhaps my 3rd and 4th combined. Your 3rd and 4th circles are perhaps my 5th circle. I also have a few cells in the "wrong place". When I try to correct these errors I don't get any improvements in the score. I still don't really know how to use these circles...

[Pavlovsky]

Теоретический максимум для числа Делакорта.
Первая колонка - N. Вторая колонка - теоретический максимум.

Цитата:

3 182
4 1399
5 6192
6 21453
7 57400
8 138048
9 299686
10 594789
11 1104084
12 1940285
13 3221808
14 5197131
15 8122684
16 12257589
17 18096102
18 26089146
19 36813208
20 51155865
21 69682700
22 93686757
23 124276242
24 163434175
25 211147804
26 271140874
27 344240988

*Все теоретические максимумы, далеко не всегда достижимы.