Al Zimmerman - Delacorte Numbers

[whitefox]

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

Оказывается Ал поменял правила - теперь нельзя выкладывать баллы.

Информация об изменении появилась только в дискуссионной группе, а на сайте конкурса всё осталось по прежнему. Вот, например, сохранённая копия сайта за 3 ноября. И соответствующая цитата из правил:

Цитата:

There are two types of information that you are forbidden to post. The first is specific squares. The second is code. You may post scores, so if you want to tell everyone that you got a raw score of 1,598,259 for n = 20 (whether true or not), go right ahead. You may also discuss the algorithms you are using.

[Herbert Kociemba]

I greatly appreciate the way Whitefox proposed to compute the Delacorte number. My approach is the swapping of random pairs in the matrix and a very simple variation of simulated annealing (without using exponential functions etc.). I can do about 3 million pair swaps with Delacorte number computations per second with a 27x27 matrix now on a rather decent hardware without looking for optimizations yet. I also did some OpenCL experiments but the results were disappointing. I suppose I do not have enough knowhow to write a good OpenCL program.

[Pavlovsky]

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

удобнее по следующей формуле:

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

Класная формула! Пусть мы делаем перебор путем размещения очередного числа в свободную ячейку. Тогда для пересчета числа Делакорта нам достаточно для каждого k хранить следующие данные, расчитанные по предыдущим размещенным числам.
1) Количество уже размещенных чисел кратных k.
2) Для уже размещенных чисел кратных k хранить суммы:

$$\sum\limits_{i\in M_k}\left(x^2(i)+y^2(i)\right)$$

$$\sum\limits_{i\in M_k}x(i)$$

$$\sum\limits_{i\in M_k}y(i)$$

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

Надо попробовать, должно работать очень быстро!

[Pavlovsky]

Кто знает, чего с сайтом конкурса? Долгая недоступность сайта уже начинает напрягать.

-- Чт ноя 20, 2014 09:58:24 --

Формула от whitefox показала просто термоядерную силу. Пересчет числа Делакорта стал выполняться в сотни (может даже тысячи) раз быстрее! Специфика конкурса такова, что победит тот у кого быстрее выполняется функция пересчета числа Делакорта.

Забавное обсуждение
http://codegolf.stackexchange.com/quest ... f-a-square

Может дать им ссылку не текущую тему?!

[dmd]

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

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

Забавное обсуждение
http://codegolf.stackexchange.com/quest ... f-a-square

Пожалуй там отмечусь. У меня уже на 4-х языках мат.моделирования есть описание задачи. Оно ничего не даёт для получения рекордов выше N3 и N4, так что думаю это не будет нарушением правил. Код на pari/gp, в котором у меня реализован банальный "покоординатный спуск" обмена двух-трёх-четырёх ячеек квадрата, я выкладывать конечно не буду. Единственная малозначительная эвристика, которую нашёл - распрямил квадрат в вектор. Стало чуть быстрее, но не более. Формулы whitefox я к сожалению пока не догоняю.

[Pavlovsky]

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

обмена двух-трёх-четырёх ячеек квадрата

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

Задача. Сформулировать условия при которых делать обмен в выбраных 4-х ячейках бессмысленно. При условии, что мы знаем обмен чисел в любой двойке или тройке ячеек не улучшает результат.

[Pavlovsky]

Обсуждение задачи на сайте эсперантистов, организованное Наталией Макаровой.
http://www.e-novosti.info/forumo/viewto ... e6cb411536

[dimkadimon]

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

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

обмена двух-трёх-четырёх ячеек квадрата

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

Задача. Сформулировать условия при которых делать обмен в выбраных 4-х ячейках бессмысленно. При условии, что мы знаем обмен чисел в любой двойке или тройке ячеек не улучшает результат.

Каждый обмен можно представить как перестановку. Например обмен а на b можно записать как (а,b) -> (b,a). Обмен а на b, b на c и c на a, записать как (a,b,c) -> (b,c,a). Каждую перестановку можно представить как композицию циклов. Например (1,2,3,4,5,6)->(5,1,6,4,2,3) = (1,5,2)(3,6) (циклы длиной один не записываются). Смотрите википедию, там лучше объяснено: https://ru.wikipedia.org/wiki/%D0%9F%D0 ... 0%BA%D0%B0

Теперь задачу можно записать так. Найти все перестановки порядка 4, которые состоят из одного цикла длиной 4 или двух циклов длиной 2. Если перестановка раскладывается на один цикл длиной 2 или один цикл длиной 3, значит мы ее уже проверили при обмене двух и трех ячеек. Таких перестановок 9 (показываю разложение на циклы): (a,b,c,d), (a,b,d,c), (a,c,d,b), (a,c,b,d), (a,d,c,b), (a,d,b,c), (a,b)(c,d), (a,c)(b,d), (a,d)(b,c). Иначе бы пришлось проверить 4!=24 перестановки.

[Pavlovsky]

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

Таких перестановок 9 (показываю разложение на циклы): (a,b,c,d), (a,b,d,c), (a,c,d,b), (a,c,b,d), (a,d,c,b), (a,d,b,c), (a,b)(c,d), (a,c)(b,d), (a,d)(b,c).

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

Но мне хотелось бы более изощреные свойства. Например.

Из формулы whitefox следует, что перестановка (a,b,c,d)->(b,a,d,c) не улчшает результат, если a,b находятся в одной строке, а c,d находятся в одной колонке.

Ну или a,b,c,d попарно взаимнопростые. Можно сформулировать более точное условие. Взамнопростыми должны быть числа:
$\frac{a}{gcd(a,b)},\frac{b}{gcd(a,b)},\frac{c}{gcd(c,d)},\frac{d}{gcd(c,d)}$

[dmd]

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

[whitefox]

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

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

Такие перестановки называются беспорядками. Беспорядок 5-го порядка может быть либо 5-циклом, либо произведением 2-цикла и 3-цикла.

Все 5-циклы получим записав в первой позиции 1 и справа все возможные перестановки остальных чисел. Всего будет $(5-1)!=24$ беспорядков данного вида.

Все произведения 2-цикла и 3-цикла получим рассмотрев все пары чисел, для каждой из которых перечислим все 3-циклы из оставшихся чисел. Например, для пары $(1,2)$ получим $(3,4,5)$ и $(3,5,4)$. Всего будет $\binom52(3-1)!=20$ беспорядков данного вида.

Общее число беспорядков порядка $n$ равно субфакториалу $!n$, который вычисляется по формуле:

$$!n=n!\sum\limits_{0\leqslant k\leqslant n}\frac{(-1)^k}{k!}$$

$$!n = \left\lfloor\frac{n!}{e}+\frac{1}{2}\right\rfloor , \quad n\geqslant 1$$

[dimkadimon]

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

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

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

[whitefox]

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

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

Если элементы квадрата выписать в строку, то мы, фактически, будем иметь дело с перестановками порядка $n^2.$ Тогда вопрос о близости квадратов можно рассматривать как вопрос о близости перестановок.

Меру близости двух перестановок можно определить как разность между порядком и числом общих элементов этих перестановок. Например, перестановки $(1,2,3,4,5)$ и $(2,1,3,4,5)$ пятого порядка имеют три общих элемента, поэтому мера их близости равна $5-3=2.$ Чем больше это число, тем дальше друг от друга находятся перестановки.

Процитированное утверждение, фактически, означает, что локальные оптимумы со значением числа Делакорта близким к оптимальному находятся далеко от глобального оптимума как перестановки (мера их близости больше четырёх).

[Pavlovsky]

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

Пересчет числа Делакорта стал выполняться в сотни (может даже тысячи) раз быстрее!

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

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

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

[dmd]

whitefox

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

Да, надо проверить сравнить результативность алгоритма только двойных перестановок с алгоритмом только тройных перестановок.