Al Zimmerman - Delacorte Numbers

[whitefox]

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

Т.е. не стоит пытаться улучшать двойные перестановки большими? Надо применять только одну конкретную перестановку?

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

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

Также можно чередовать наискорейший спуск с отжигом. Сначала спуском находим локальный оптимум, затем отжигом его улучшаем, потом снова спуск, отжиг, и так далее. Мои эксперименты показали, что такой алгоритм эффективнее чем просто спуск или просто отжиг.

[dimkadimon]

whitefox в сообщении #934143 писал(а):

Также можно чередовать наискорейший спуск с отжигом. Сначала спуском находим локальный оптимум, затем отжигом его улучшаем, потом снова спуск, отжиг, и так далее. Мои эксперименты показали, что такой алгоритм эффективнее чем просто спуск или просто отжиг.

Есть много других вариантов. Например я отжиг вообще не использую. Я делаю спуск с генетических алгоритмом и это оказалось лучше всего.

-- 21.11.2014, 20:56 --

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

Решил более точно оценить ускорение пересчета числа Делакорта.

Число делителей, асимптотическая формула Дирихле: https://ru.wikipedia.org/wiki/%C4%E5%EB ... E%F1%F2%FC

Получилось по формуле whitefox пересчет выполняется в $O(\frac{N^2}{lnN^2})$ раз быстрее.

Допустим мы переставили числа i и k. Теперь нам надо пересчитать число Делакорта. Есть несколько вариантов:

1. Пересчитать все полностью заново. Для этого надо сложить для каждой пары чисел в NxN квадрате. Таких сумм $\frac{N^2*(N^2-1)}{2}$.
2. Пересчитать только те суммы в которых участвуют числа i и k. Таких будет $2*(N^2-1)$. Это примерно в $\frac{N^2}{4}$ быстрее первого метода.
3. Пересчитать только суммы которые имеют общий делитель с i или k. Таких будет $(|M^i|-1)+(|M^k|-1)$, где $i \in M^i,~k \in M^k$. В худшем случае i и k делятся на 2 и $|M^i|=|M^k|=\frac{N^2}{2}$. Это примерно в $\frac{N^2}{2}$ быстрее первого метода и в 2 раза быстрее второго метода.

[Pavlovsky]

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

Пересчитать все полностью заново. Для этого надо сложить для каждой пары чисел в NxN квадрате.

Совсем не обязательно перебирать все пары чисел в квадрате. Достаточно для каждого числа в квадрате, посчитать его вклад в число делакорта перебрав только его делители.

Получается количество операций
$\sum_{n=1}^{N^2}\tau(n)$, где $\tau(n)$ число делителей числа n.

[dimkadimon]

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

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

Пересчитать все полностью заново. Для этого надо сложить для каждой пары чисел в NxN квадрате.

Совсем не обязательно перебирать все пары чисел в квадрате. Достаточно для каждого числа в квадрате, посчитать его вклад в число делакорта перебрав только его делители.

Получается количество операций
$\sum_{n=1}^{N^2}\tau(n)$, где $\tau(n)$ число делителей числа n.

Это мой третий метод.

[whitefox]

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

3. Пересчитать только суммы которые имеют общий делитель с i или k. Таких будет $(|M^i|-1)+(|M^k|-1)$, где $i \in M^i,~k \in M^k$. В худшем случае i и k делятся на 2 и $|M^i|=|M^k|=\frac{N^2}{2}$. Это примерно в $\frac{N^2}{2}$ быстрее первого метода и в 2 раза быстрее второго метода.

Если поменять местами числа $a$ и $b$, то изменение числа Делакорта вычисляется по формуле:

$$\Delta D=A-B-2C_x-2C_y$$ $$A=\left(x^2_b-x^2_a+y^2_b-y^2_a\right)\left(\Phi(a)-\Phi(b)\right)$$ $$B=\left((x_b-x_a)^2+(y_b-y_a)^2\right)(a+b-2\gcd(a,b))$$ $$C_x=(x_b-x_a)\left(\Psi_x(a)-\Psi_x(b)\right)$$ $$C_y=(y_b-y_a)\left(\Psi_y(a)-\Psi_y(b)\right)$$ $$\Phi(m)=\sum\limits_{k\mid m}\varphi(k)\left\lfloor\frac{n^2}k\right\rfloor$$ $$\Psi_x(m)=\sum\limits_{k\mid m}\varphi(k)X_k$$ $$\Psi_y(m)=\sum\limits_{k\mid m}\varphi(k)Y_k$$ $$X_k=\sum\limits_{i\in M_k}x_i$$ $$Y_k=\sum\limits_{i\in M_k}y_i$$

Все числа $\Phi(m),\gcd(a,b)$ являются константами и вычислены заранее.

При вычислении $\Delta D$ используются текущие значения $\Psi_x(a),\Psi_y(a),\Psi_x(b),\Psi_y(b).$ После фактического выполнения обмена $a\leftrightarrow b$ новые значения $\Psi_x,\Psi_y$ для всех $m$ таких, что $\gcd(m,a)\ne\gcd(m,b)$ вычисляются по следующим формулам:

$$\Psi'_x(m)=\Psi_x(m)+(x_b-x_a)(\gcd(m,a)-\gcd(m,b))$$

$$\Psi'_y(m)=\Psi_y(m)+(y_b-y_a)(\gcd(m,a)-\gcd(m,b))$$

Сложность расчета $\Delta D$ есть $O(1)$, а сложность обновления всех $\Psi_x,\Psi_y$ есть $O(n^2).$ Ускорение получается за счёт того, что $\Delta D$ вычисляется значительно чаще чем выполняется обмен $a\leftrightarrow b.$

Но можно $\Psi_x,\Psi_y$ не хранить, а вычислять в процессе вычисления $\Delta D.$ При этом хранить $X_k,Y_k$ и обновлять их при фактическом выполнении обмена $a\leftrightarrow b.$ В этом случае сложность вычисления $\Delta D$ и сложность пересчёта $X_k,Y_k$ будет пропорциональна числу делителей $a$ и $b,$ то есть в среднем $O(\log n).$

UPD: Исправлены формулы.

[Pavlovsky]

Мда, это какая то феерия. Завтра начну кодить. Отмечу: любую перестановку можно представить в виде последовательности перестановок пар чисел.

[Herbert Kociemba]

I still wonder about the beautiful formula of whitefox. It only works if the following is true:

For any natural number n, if we add for all divisors d of n the count of numbers which are <=d and which are relatively prime to d, we get n.

Sounds complicated, so her an example for n=20:

Divisors of 20: 1,2,4,5,10,20

Relatively prime to
1: 1
2: 1
4: 1,3
5: 1,2,3,4
10: 1,3,7,9
20: 1,3,7,9,11,13,17,19

The count of these numbers is 20. But WHY is this true?

EDIT: I found a proof in chapter 4, Theorem 4.1 of http://www.math.wisc.edu/~josizemore/Notes11(phi).pdf . Nice!

[dimkadimon]

whitefox в сообщении #934218 писал(а):

Сложность такого рассчета $O(1)$, что существенно меньше $O(n^4)$ при первом методе и $O(n^2)$ при втором.

Ого! Если это так то я смогу ускорить свою программу в сотни раз! Спасибо, буду разбираться.

[whitefox]

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

The count of these numbers is 20. But WHY is this true?

Это свойство функции Эйлера установил ещё Гаусс.

[Herbert Kociemba]

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

Ого! Если это так то я смогу ускорить свою программу в сотни раз! Спасибо, буду разбираться.

I knew from another contestant that a very fast method must exist since about one month, but he did not give me any clue. I thought hard but I did not find an approach since then until whitefox came up with his formula on 14.11. I am quite sure that his and whitefox' method are equivalent and implemented it about 5 days ago. My program did about 100000 pairs swaps/s before and now 5000000 pair swaps/s, including the logic for deciding if to keep a swap etc.

But do not expect too much: For me, the faster method did not give me any improvement of the score yet.

[Yadryara]

Рассмотрим простейший пример:

$\tikz[scale=.06]{ \draw(0,0)--(0,50)--(50,50)--(50,0)--(0,0); \draw(0,10)--(50,10); \draw(0,20)--(50,20); \draw(0,30)--(50,30); \draw(0,40)--(50,40); \draw(10,0)--(10,50); \draw(20,0)--(20,50); \draw(30,0)--(30,50); \draw(40,0)--(40,50); \draw[very thick][green!40!brown!200](43,48)--(47,48)(47,48)--(44,42); \draw[very thick][green!40!brown!200](12,36)--(14,38)--(14,32)(16,36)--(18,38)--(18,32); \node at (15,4){\large \textbf{14 21 22}}; }}$

Если нам необходимо поменять местами числа 7 и 11, то изменение числа Делакорта $\Delta D$ можно посчитать так:

$$\Delta D = 2(x_7(x_7 + w_x) - x_{11}(x_{11} + w_x) + y_7(y_7 + w_y) - y_{11}(y_{11} + w_y))$$

Здесь обозначения $w$ даны в честь whitefox'a:

$$w_x = 10x_{22} - 6x_{14} - 6x_{21} $$

$$w_y = 10y_{22} - 6y_{14} - 6y_{21} $$

[sevir]

Наверное, простейший пример - это матрица два на два:

$$\tikz[scale=.04]{ \draw(0,0)--(0,20)--(20,20)--(20,0)--(0,0); \draw(0,10)--(20,10); \draw(0,20)--(20,20); \draw(10,0)--(10,20); \draw(20,0)--(20,20); \node at (10,15){\large \textbf{1 2}}; \node at (10,5){\large \textbf{3 4}}; }}$$

Тогда в формулах

$$X_k=\sum\limits_{i\in M_k}x_i$$ $$Y_k=\sum\limits_{i\in M_k}y_i$$

для

$$k = 1$$

суммы не зависят от расположения элементов матрицы и всегда равны 6, т.к. множество, по которому ведется суммирование, состоит из всех элементов матрицы. Или я чего-то не так понял?

[Yadryara]

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

для

$$k = 1$$

Во-первых, $k = 1$ мы уже давным-давно не рассматриваем. Пожалуйста прочитайте тему внимательней.

whitefox в сообщении #930921 писал(а):

Обозначим через $M_k$ множество натуральных чисел не больших $n^2$ и кратных $k,$ и пусть $x(i),y(i)$ обозначают $x$ и $y$ координаты числа $i$ соответственно, а $\bar x_k,\bar y_k$ обозначают средние $x$ и $y$ координаты всех чисел множества $M_k.$ И пусть $\varphi(k),$ как обычно, обозначает функцию Эйлера.

Тогда число Делакорта равно:

$$D=\frac{n^4(n^2-1)}6+\sum\limits_{k=2}^{\frac{n^2}2}\varphi(k)\cdot D_k$$

$$D_k=\left\lfloor\frac{n^2}k\right\rfloor\sum\limits_{i\in M_k}\left((x(i)-\bar x_k)^2+(y(i)-\bar y_k)^2\right)$$

Видите, что суммирование по $k$ начинается с 2-х?

Для квадрата 5-го порядка числа 1, 13, 17, 19, 23 имеют нулевой вес, и поэтому их расположение совершенно неинтересно.

[sevir]

Я это понимаю: единица обрубается нижним индексом суммирования, а 13, 17, 19, 23 - верхним индексом суммирования. Я про то, что формулы пересчета для них неверны. Но не в этом суть: Herbert Kociemba пишет, что от всего этого мало толку.

[Yadryara]

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

Я про то, что формулы пересчета для них неверны.

Уточните Вашу мысль, пожалуйста. Какие именно формулы неверны?