Al Zimmermann: Primorial Soup

[as73251]

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

as73251 в сообщении #1252958 писал(а):

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

Нашел первые 4 оптимальных решения...

Для 4-го оптимального (в смысле: наилучшего) решения (7 вершин в графе) даже хорошо оптимизированный алгоритм потребует несколько часов работы на 1000 ядрах для полного перебора возникающих варинтов. В связи с этим у меня к Вам нескромный вопрос: какова "мощность" железа, которое Вы используете? Я думаю, что Jarek Wroblewski и не искал оптимальное решение для 7 вершин, но при этом с громадным отрывом занимает первое место: я имею в виду, что большинство конкурсов Al нивелирует мощность железа и на первое место выходит оригинальный алгоритмический подход.

У меня один 5ти-летний компьютер quad-core. Сила в алгоритме. Правда 8 вершин никак не могу решить...

Тогда объясните, что Вы подразумеваете под "оптимальным решением". Судя по Вашему Score (4.0000000000000), Вами для 7-ми вершин найдено одно из 7! точных решений. Т.е. без отсечения части решений из соображений здравого смысла (даже выделив алгоритмически только нахождение одного точного решения) не обойтись, а это уже не будет полной переборной задачей. И мне не совсем понятно, что Вы подразумеваете под словами: "8 вершин никак не могу решить...". Т.е. каков критерий истины для 8 вершин?

[Herbert Kociemba]

I use a about three years old DELL Precision Tower 5810. The as it seems optimal values for N=4 to 7 I got with some simple edge swapping algorithm in the complete graph (swapping two edges with a common vertex), but for N=8 I only managed to find the as it seems optimal solution with some additional heuristic for when to swap two edges and when not. This took maybe 24 CPU hours for N=8.

I realized after some time that in principle this method is not suited for larger N. So I completeley changed the method for N=9. I With this new method my solution appeared within a few minutes and I can prove that there is no better solution (I could not prove this with the old method for N=4 to 8, because it was a random search). For N=10 this new method again must be improved in some way, I did not find the optimal solution yet within 7 hours, the raw score still is above 3.5 millions.

[dimkadimon]

as73251 в сообщении #1253245 писал(а):

огда объясните, что Вы подразумеваете под "оптимальным решением". Судя по Вашему Score (4.0000000000000), Вами для 7-ми вершин найдено одно из 7! точных решений. Т.е. без отсечения части решений из соображений здравого смысла (даже выделив алгоритмически только нахождение одного точного решения) не обойтись, а это уже не будет полной переборной задачей. И мне не совсем понятно, что Вы подразумеваете под словами: "8 вершин никак не могу решить...". Т.е. каков критерий истины для 8 вершин?

Да вы правы у меня нет доказательств что мои решения оптимальные - они всего лишь лучшие из найденых. Для 8 вершин лучшее решение ещё не нашёл.

-- 05.10.2017, 20:16 --

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

I use a about three years old DELL Precision Tower 5810. The as it seems optimal values for N=4 to 7 I got with some simple edge swapping algorithm in the complete graph (swapping two edges with a common vertex), but for N=8 I only managed to find the as it seems optimal solution with some additional heuristic for when to swap two edges and when not. This took maybe 24 CPU hours for N=8.

I realized after some time that in principle this method is not suited for larger N. So I completeley changed the method for N=9. I With this new method my solution appeared within a few minutes and I can prove that there is no better solution (I could not prove this with the old method for N=4 to 8, because it was a random search). For N=10 this new method again must be improved in some way, I did not find the optimal solution yet within 7 hours, the raw score still is above 3.5 millions.

This is fascinating on so many levels. I am surprised that you can prove the optimality of your n=9. Also interesting that the strategy for 8 doesn't work for 9.

[Herbert Kociemba]

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

Also interesting that the strategy for 8 doesn't work for 9.

The problem is that any algorithm which tries to improve the result by small changes (for example by interchanging the prime 29 with prime 31) will not work since even such small changes have dramatic impact on the raw score and will transform a low raw score to the high raw score of a random configuration. So essentially I obtained the results for N= 4 to 8 by just hopping around by random in the seach space even though I did only small incremental changes. And for N=9 and above the chance to find the minimum is almost zero with this method.

[Herbert Kociemba]

For N=10 for example the vertex V1={13, 23, 41, 43, 59, 73, 127, 149, 193} would contribute only with ~68580 to the target energy, but V2={13, 23, 41, 43, 59, 73, 127, 149, 197} would contribute with ~1.7439*10^12. Since the lowest targest energy found for N=10 is 2229731 in the moment, V2 would totally destroy the configuration.

[dimkadimon]

Thank you Herbert. Your comments really help me to focus on the right algorithm for higher N.

[12d3]

Немножко математики.
Понятно, что у каждой вершины энергия должна мало отличаться от средней. Можно оценить, насколько.
Обозначим target energy через $T$, $t=\frac T n$ - это какая часть от нее приходится на одну вершину в среднем. Обозначим энергии вершин через $E_i,\, 1 \le i \le n$. Тогда $\prod\limits_{i=1}^{n}E_i = t^n$.
Введем $\alpha_i = \frac {E_i}{t} -1$. Для оптимальных решений $\alpha_i \ll 1$.
Тогда $\prod\limits_{i=1}^{n}t \left(1+\alpha_i \right) = t^n \Rightarrow \prod\limits_{i=1}^{n}\left(1+\alpha_i \right) = 1$
Т.к. $\alpha_i \ll 1$, то $1 = \prod\limits_{i=1}^{n}\left(1+\alpha_i \right) \approx 1 + \sum\limits_{i=1}^{n}\alpha_i + \sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n} \alpha_i \alpha_j$.
Обозначим $\sum\limits_{i=1}^{n}\alpha_i = A$. Тогда $\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n} \alpha_i \alpha_j \approx -A$.
Далее, $A^2 = \left( \sum\limits_{i=1}^{n}\alpha_i \right)^2 = \sum\limits_{i=1}^{n}\alpha_i^2 + 2 \sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n} \alpha_i \alpha_j \approx \sum\limits_{i=1}^{n}\alpha_i^2 -2A $
$ \sum\limits_{i=1}^{n}\alpha_i^2 \approx 2A + A^2 \approx 2A = 2 \sum\limits_{i=1}^{n}\alpha_i = 2 \sum\limits_{i=1}^{n}\frac{E_i - t}{t} = 2\frac{\left(\sum\limits_{i=1}^{n} E_i \right)- T}{t} = \frac{2R}{t}$, где $R$ - это rawscore.
Отсюда можно получить оценку на максимальное отличие энергии вершины от средней:
$\left| E_i - t \right| = t \left| \alpha_i \right|= t \sqrt{\alpha_i^2} \le t \sqrt{\sum\limits_{i=1}^{n}\alpha_i^2} \approx t \sqrt{\frac{2R}{t}} = \sqrt{2Rt}$.
Например, для $n=11$ будет $t\approx 5.8 \cdot 10^{18}$. Если мы хотим получить rawscore не больше $10^7$, то энергии вершин должны отличаться от средней не более, чем на $\sqrt{2Rt} \approx 10^{13}$

[lel0lel]

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

[dimkadimon]

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

Отсюда можно получить оценку на максимальное отличие энергии вершины от средней:
$\left| E_i - t \right| = t \left| \alpha_i \right|= t \sqrt{\alpha_i^2} \le t \sqrt{\sum\limits_{i=1}^{n}\alpha_i^2} \approx t \sqrt{\frac{2R}{t}} = \sqrt{2Rt}$.
Например, для $n=11$ будет $t\approx 5.8 \cdot 10^{18}$. Если мы хотим получить rawscore не больше $10^7$, то энергии вершин должны отличаться от средней не более, чем на $\sqrt{2Rt} \approx 10^{13}$

Отличная формула, спасибо! Правда $10^13$ еще большой диапазон, но лучше чем ничего.

[dmd]

Если $E_t$ - target energy (формула из описания задачи), а $E_i$ - энергия i-й вершины, то $E_i<E_t/(n-1)$. Но доказать не могу.

[as73251]

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

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

Отсюда можно получить оценку на максимальное отличие энергии вершины от средней:
$\left| E_i - t \right| = t \left| \alpha_i \right|= t \sqrt{\alpha_i^2} \le t \sqrt{\sum\limits_{i=1}^{n}\alpha_i^2} \approx t \sqrt{\frac{2R}{t}} = \sqrt{2Rt}$.
Например, для $n=11$ будет $t\approx 5.8 \cdot 10^{18}$. Если мы хотим получить rawscore не больше $10^7$, то энергии вершин должны отличаться от средней не более, чем на $\sqrt{2Rt} \approx 10^{13}$

Отличная формула, спасибо! Правда $10^13$ еще большой диапазон, но лучше чем ничего.

Отличные результаты вплоть до числа узлов 12 (всплывающая подсказка для Hans-Werner & Matthias Paulsen показывает ровно 9.00) говорят о том, что на практике этот диапазон с ростом числа узлов становится настолько узким, что позволяет добиться таких прекрасных результатов.

[dimkadimon]

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

Если $E_t$ - target energy (формула из описания задачи), а $E_i$ - энергия i-й вершины, то $E_i<E_t/(n-1)$. Но доказать не могу.

Так нам надо чтобы $E_i$ приближалось к $E_t/n$. Я думаю от сюда следует ваш результат.

[dmd]

Нам надо как-то уменьшить объёмы вычислений, введя какую-то ограничивающую эвристику, отбраковывающую заведомо невалидные энергии вершин. У каждого решения (не обязательно рекордного, но и рекордного в том числе) есть вершины с энергией $E_i<E_t/n$, и всегда есть как минимум одна вершина с энергией $E_i>E_t/n$, но всегда для всех вершин выполняется $E_i<E_t/(n-1)$. Но мне оно не сильно помогло, всё равно не получается добраться до рекорда n=8. Нужно что-то ещё более сильное.

[Herbert Kociemba]

I wonder for which N the results found so far are optimal. I can prove this for N<=10. For N=11 I found a solution with the current minimum R=8691987 but I did not try to prove optimality because I thought that Tom Sigerdas found a method for finding the optimal solution up to N=14 (11 points). But now it seems that Walter Trump (nomen not est omen) improved the R = 8932072159 solution for N=13 to R=6863373741! So I give N=11 another try. Within one day I should know if R=6863373741 is optimal. I am quite sure it is.
For N=12 my current method is too slow to find any solution at all. I hope I find some better way.

[dimkadimon]

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

У каждого решения (не обязательно рекордного, но и рекордного в том числе) есть вершины с энергией $E_i<E_t/n$, и всегда есть как минимум одна вершина с энергией $E_i>E_t/n$, но всегда для всех вершин выполняется $E_i<E_t/(n-1)$

12d3 доказал что всегда имеем $|E_i-E_t/n|<\sqrt{2R*E_t/n}$, значит имеем $E_i<E_t/n+\sqrt{2R*E_t/n}$. Осталось доказать что $E_t/n+\sqrt{2R*E_t/n}<E_t/(n-1)$. Тут $R$ это raw score. Мне интересно как оптимальная $R$ растет в зависимости от $n$?