Al Zimmermann - Sums and Products

[Pavlovsky]

Похоже ничего лучшего не придумать.
Линейка Голомба + adding an offset to the sequence

А при поиске линейки Голомба ничего лучшего чем finite affine planes и finite projective planes не найти. Хотя эти алгоритмы не дают оптимального результата.

[dimkadimon]

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

Похоже ничего лучшего не придумать.
Линейка Голомба + adding an offset to the sequence

А при поиске линейки Голомба ничего лучшего чем finite affine planes и finite projective planes не найти. Хотя эти алгоритмы не дают оптимального результата.

Ведь все таки есть лучше решения. Что если взять решение finite planes и его улучшить отжигом? У меня правда не получилось.

[whitefox]

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

Что если взять решение finite planes и его улучшить отжигом? У меня правда не получилось.

Каким образом вы выбираете соседей?

[dimkadimon]

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

Каким образом вы выбираете соседей?

Пробовал два метода:

1. Менять отметки на линейке.
2. Представить линейку в форме разниц между отметками. Каждая разница должна быть уникальна. Можно обменивать разницы или менять одну конкретную разницу.

[Pavlovsky]

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

взять решение finite planes и его улучшить отжигом?

Боюсь что это невозможно. В решениях полученных finite planes, все числа плотно подогнаны друг к другу. Частичная замена некоторых чисел ничего не даст, кроме исходного решения.

[whitefox]

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

Можно обменивать разницы или менять одну конкретную разницу.

Имхо, единственное что можно сделать — взять разности в обратном порядке. Все прочие перестановки разностей, а равно замена одной конкретной разности, ничего не дадут. По причине указанной Pavlovsky.

[Pavlovsky]

Может кто выложит оттранслированные exe файлы двух алгоритмов на конечных полях?

[dimkadimon]

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

Может кто выложит оттранслированные exe файлы двух алгоритмов на конечных полях?

Я компилировал через gfortran.

[Pavlovsky]

У меня нет gfortran. И если честно, нет желания разбираться как с ним работать.

[Pavlovsky]

A REVIEW OF THE AVAILABLE CONSTRUCTION METHODS FOR GOLOMB RULERS
http://eeme.ucd.ie/~kdrakaka/work/publi ... Rulers.pdf

Продолжаю изучение этой статьи.

Теорема 2. Доказательство. Не понимаю, как были выведены формулы (4) и (5). Может кто поможет?

[whitefox]

Разделим формулу (3)

$$2p(x+y) + (x^2\bmod p) + (y^2\bmod p) =a$$

на $2p$ и возьмём целую часть, получим

$$\left\lfloor x+y+\frac12\left(\frac{x^2\bmod p}p+\frac{y^2\bmod p}p\right)\right\rfloor=\left\lfloor\frac a{2p}\right\rfloor$$

Так как $x$ и $y$ целые, а выражение в круглых скобках меньше двух, то получаем формулу (4)

$$x+y=\left\lfloor\frac a{2p}\right\rfloor$$

То есть $x+y$ есть константа, которую обозначим как $A.$

Теперь приведём формулу (3) по модулю $p,$ получим

$$x^2+y^2\equiv a\pmod p$$

и так как $x^2+y^2=(x+y)^2-2xy,$ то

$$(x+y)^2-2xy\equiv a\pmod p$$

из чего следует формула (5)

$$xy\equiv b(A^2-a)\pmod p$$

где $b$ такое, что $2b\equiv1\pmod p.$ Такой выбор $b$ возможен так как $p$ по условию нечётное простое. Следовательно $xy\bmod p$ есть константа, обозначенная как $B.$

[Pavlovsky]

Спасибо. Ваше объяснение очень простое и понятное.

[Herbert Kociemba]

To get good results it is necessary to generate all possibilities. For p = 5 and the projective case there are for example 60 cases:

{{0,1,3,8,12,18},{0,1,3,10,14,26},{0,1,4,6,13,21},{0,1,4,10,12,17},{0,1,6,18,22,29},{0,1,8,11,13,17},{0,1,11,19,26,28},{0,1,14,20,24,29},{0,1,15,19,21,24},{0,1,15,20,22,28},{0,2,3,8,20,24},{0,2,3,16,22,26},{0,2,5,6,16,24},{0,2,5,12,13,27},{0,2,6,20,21,28},{0,2,7,11,17,30},{0,2,7,21,22,25},{0,2,8,11,12,26},{0,2,9,13,25,30},{0,2,9,17,27,28},{0,3,4,14,22,29},{0,3,4,18,23,25},{0,3,5,9,23,24},{0,3,5,12,20,30},{0,3,9,11,16,30},{0,3,10,11,25,29},{0,4,6,9,16,17},{0,4,9,11,12,25},{0,4,10,23,24,26},{0,4,11,13,14,19},{0,4,16,21,22,24},{0,4,18,19,26,29},{0,5,6,8,15,19},{0,5,7,8,21,27},{0,5,7,13,16,17},{0,5,9,15,28,29},{0,5,17,21,28,30},{0,5,19,20,23,29},{0,6,8,13,27,28},{0,6,9,10,24,29},{0,6,10,15,17,18},{0,6,19,20,22,27},{0,7,8,22,26,28},{0,7,9,10,15,27},{0,7,9,12,13,23},{0,7,10,12,16,30},{0,7,11,23,28,29},{0,7,15,25,26,29},{0,8,15,17,20,21},{0,8,18,19,22,24},{0,10,11,14,16,23},{0,10,18,25,27,30},{0,12,16,23,25,26},{0,12,17,18,20,27},{0,13,14,16,21,25},{0,13,19,23,28,30},{0,14,15,18,24,26},{0,14,15,22,25,27},{0,14,18,20,23,30},{0,14,19,21,27,30}}

I did not examine the cases with prime p a bit larger than the problem size N yet (for example for N=1009 also p=1013 and p=1019 should be examined), but I am quite sure that all the top solutions for the larger N can be found in this way.

[Pavlovsky]

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

To get good results it is necessary to generate all possibilities.

Этот подход даст в лучшем случае 30,0000 в текущем конкурсе. Чтобы удивить лидеров, надо искать линейку Голомба лучше чем дают алгоритмы на основе конечных полей.

-- Ср дек 09, 2015 10:03:58 --

Чего то вдруг возник вопрос. До сих пор считал, что алгоритмы affine plane construction и projective plane construction не дают теоретически минимальных результатов. Вдруг засомневался в этом.
Вот таблица рекордов:
http://www.research.ibm.com/people/s/shearer/grtab.html

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

[dimkadimon]

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

To get good results it is necessary to generate all possibilities. For p = 5 and the projective case there are for example 60 cases:

Yep I thought this was the case, but couldn't find an easy way to generate them all. I tried using the sub-optimal rulers generated by the fortran programs, but it wasn't enough.

-- 09.12.2015, 15:21 --

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

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

Ну это только первые 27, а дальше не известно что будет. Все таки хочется удивить лидеров.