2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 14, 15, 16, 17, 18, 19, 20 ... 25  След.
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение08.12.2014, 16:35 


22/11/14

43
dimkadimon в сообщении #942290 писал(а):
sevir в сообщении #941714 писал(а):
Как я понял, это уже устаревшие данные: у меня максимум перевалил в четвертую сотню со сдвигом на несколько десятков.


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

Отличие моего результата от результата Herbert Kociemba - менее пяти единиц.

-- 08.12.2014, 16:50 --

sevir в сообщении #942477 писал(а):
dimkadimon в сообщении #942290 писал(а):
sevir в сообщении #941714 писал(а):
Как я понял, это уже устаревшие данные: у меня максимум перевалил в четвертую сотню со сдвигом на несколько десятков.


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

Отличие моего результата от результата Herbert Kociemba - менее пяти единиц.

Уже превзошел результат Herbert Kociemba: счет продолжается - попытаюсь еще увеличить разрыв.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение08.12.2014, 22:07 


20/01/13
62
dimkadimon в сообщении #942337 писал(а):
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...

No, the circles are different because I use the "uniqueness".

About the circles, I use them for generating seeds, but there is probably other uses.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение08.12.2014, 23:26 


22/11/14

43
jcmeyrignac в сообщении #942687 писал(а):
dimkadimon в сообщении #942337 писал(а):
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...

No, the circles are different because I use the "uniqueness".

About the circles, I use them for generating seeds, but there is probably other uses.

Не надо ломать копья: даже самый грубый расчет, не требующий времени и ресурсов, расставит все числа по ранжиру: и после одного этого самого расчета все можно проиндексировать для всех последующих расчетов. Эта индексация очень полезна для сокращения времени расчетов: вкупе с формулами whitefox'а она дает громадное ускорение. Я тут уже выкладывал решение, которое получил мгновенно, для $n = 27$ и из которого без труда можно извлечь индексный массив. Хочу заметить, что можно вести более тонкую градацию, используя дроби. Например, для нахождения максимума в случае $n = 10$, который превышает значение 593350, я затратил не более часа времени на 20 ядрах.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение09.12.2014, 00:23 


20/01/13
62
sevir в сообщении #942737 писал(а):
Например, для нахождения максимума в случае $n = 10$, который превышает значение 593350, я затратил не более часа времени на 20 ядрах.

I got it in 10 minutes on a quadcore, but I use a completely different method.
Also, there are several solutions above 593350, you'll be surprised !

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение09.12.2014, 01:05 


22/11/14

43
jcmeyrignac в сообщении #942771 писал(а):
sevir в сообщении #942737 писал(а):
Например, для нахождения максимума в случае $n = 10$, который превышает значение 593350, я затратил не более часа времени на 20 ядрах.

I got it in 10 minutes on a quadcore, but I use a completely different method.
Also, there are several solutions above 593350, you'll be surprised !
И какое место Вы занимаете? И какой максимум у Вас для $n = 15$? Вы обгоняете Herbert Kociemba'у? Пока я от Вас не услышал ни одного конкретного предложения: одни общие слова.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение09.12.2014, 02:25 


20/01/13
62
sevir в сообщении #942801 писал(а):
И какой максимум у Вас для $n = 15$?

$Max15 >= 8109168$

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение09.12.2014, 02:30 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
sevir в сообщении #942801 писал(а):
И какое место Вы занимаете?


Он обгоняет всех на этом форуме (6ое место!)

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение09.12.2014, 06:09 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
sevir в сообщении #942801 писал(а):
И какое место Вы занимаете? И какой максимум у Вас для $n = 15$? Вы обгоняете Herbert Kociemba'у?

Вопрос совершенно некорректный. Мне стыдно за форум!

sevir
а у вас, я полагаю, место 263.
Угадала? :mrgreen:

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение09.12.2014, 07:37 
Аватара пользователя


21/02/10
1594
Екатеринбург
Чего то мой пост про теоретические максимумы общество проигнорировало. Осмелюсь еще раз поднять эту тему.

Рассмотрим формулу whitefox:
$$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)$$

Пусть $med=\frac{n+1}{2}$ середина квадрата.

Гипотеза. D достигает максимума, если для всех k $\bar x_k = \bar y_k = med$. Тогда формулу можно переписать:

$$D=\frac{n^4(n^2-1)}6+\sum\limits_{i=1}^{n^2}\Phi(i)\cdot D(i)$$, где
Квадрат расстояния от ячейки с числом i до центра квадрата:
$$D(i)=\left((x(i)-med)^2+(y(i)-med)^2)$$
Весовая функция числа i:
$$\Phi(i)=\sum\limits_{k\mid i, k\ge 2}\varphi(k)\left\lfloor\frac{n^2}k\right\rfloor$$

Утверждение. D достигает максимума, если для любых a,b $$\Phi(a)\ge \Phi(b) => D(a) \ge D(b)$$

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение09.12.2014, 08:03 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #942860 писал(а):
Чего то мой пост про теоретические максимумы общество проигнорировало.

Скажу за себя.
Я и раньше-то совсем не вникала во все эти формулы. А сейчас и тем более, ибо давно вышла из конкурса.
Ваш пост с теоретическими максимумами видела и была восхищена (правда).

Вам с whitefox давно пора представить на защиту диссертацию "Числа Делакорта" :wink:

Нет, шутки шутками, а если серьёзно: написать статью в солидный журнал стоит.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение09.12.2014, 11:47 
Основатель
Аватара пользователя


11/05/05
4312
 !  sevir забанен как клон пользователей wanderers, Nik_Svan, y_nikolaenko, drozdov_mihail, ...

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение09.12.2014, 13:31 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Pavlovsky в сообщении #942860 писал(а):
Пусть $med=\frac{n+1}{2}$ середина квадрата.

Гипотеза. D достигает максимума, если для всех k $\bar x_k = \bar y_k = med$.

Замечу,что значение $\mathrm{med}$ зависит от расположения начала координат. Если начало координат поместить в центр квадрата, то $\mathrm{med} = 0.$

Число Делакорта от расположения начала координат не зависит, и выражается формулой: $$D=\sum\limits_{m=1}^{n^2}(x_m^2+y_m^2)\Phi(m)-\sum\limits_{m=1}^{n^2}\left(x_m\Psi_x(m)+y_m\Psi_y(m)\right)$$ Из которой выводится: $$D^*=\sum\limits_{m=1}^{n^2}\widetilde{\Phi}(m)\left((x_m-\mathrm{med})^2+(y_m-\mathrm{med})^2\right)-\sum\limits_{k=2}^{\frac{n^2}2}\varphi(k)\left\lfloor\frac{n^2}k\right\rfloor^2\left((\bar x_k-\mathrm{med})^2+(\bar y_k-\mathrm{med})^2\right)$$ где $$D^*=D-\frac{n^4(n^2-1)}6,\quad\widetilde{\Phi}(m)=\sum\limits_{k\mid m\atop{2\leqslant k\leqslant\frac{n^2}2}}\varphi(k)\left\lfloor\frac{n^2}k\right\rfloor$$ Из чего следует, что: $$D^*\leqslant\sum\limits_{m=1}^{n^2}\widetilde{\Phi}(m)\left((x_m-\mathrm{med})^2+(y_m-\mathrm{med})^2\right)$$ независимо от справедливости Гипотезы.

В частности, при расположении начала координат в центре квадрата: $$D^*\leqslant\sum\limits_{m=1}^{n^2}\widetilde{\Phi}(m)(x_m^2+y_m^2)$$

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение09.12.2014, 13:43 
Аватара пользователя


21/02/10
1594
Екатеринбург
whitefox спасибо. Я так понял гипотеза, с вашим уточнением (точнее моя гипотеза нафиг не нужна :D ), доказана?


Провел эксперименты с этой формулой. Взял решение для N=7 Dm=56849 (есть у меня и лучше). Рекорд для N=7 Dr=57192. Теоретический максимум Dt=57400.

Посчитал потери в своем решении от помещения чисел не в свой круг, получилось -276. То есть уже за счет неправильного размещения чисел по кругам, мне уже рекорда 57192 не достичь (57192-57400=-208). Потери от того, что не все центры масс находятся в центре квадрата получаются =56849-57400+276=-275.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение09.12.2014, 13:48 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Pavlovsky в сообщении #942929 писал(а):
whitefox спасибо. Я так понял гипотеза доказана?

К сожалению, нет. Доказана только независимость оценки верхней границы числа Делакорта от справедливости гипотезы. Ну и сама оценка, разумеется :-)

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение09.12.2014, 14:00 
Аватара пользователя


21/02/10
1594
Екатеринбург
whitefox в сообщении #942932 писал(а):
Нет, доказана только независимость оценки верхней границы числа Делакорта от справедливости гипотезы.


Чуток опередили, пока я редактировал свое сообщение. Моя гипотеза не нужна!

-- Вт дек 09, 2014 16:46:05 --

Получается такой алгоритм перебора.
1) Упорядочиваем список чисел по убыванию веса.
2) Размещаем очередное число из списка в свободную ячейку.
3) Считаем потери.
3.1) От нарушения условия $$\Phi(a)\ge \Phi(b) => D(a) \ge D(b)$$
3.2) Оцениваем $$\sum\limits_{m=1}^{n^2}\left(x_m\Psi_x(m)+y_m\Psi_y(m)\right)$$
4) Если потери превышают порог, возвращаем перебор назад.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 373 ]  На страницу Пред.  1 ... 14, 15, 16, 17, 18, 19, 20 ... 25  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group