2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 5, 6, 7, 8, 9, 10, 11 ... 25  След.
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение22.11.2014, 14:35 


22/11/14

43
Разве для $ a = 1$ эти значения должны меняться:
$$\Psi'_x(a)=\Psi_x(a)+(x_b-x_a)a$$ $$\Psi'_y(a)=\Psi_y(a)+(y_b-y_a)a$$

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


29/04/13
7124
Богородский
Именно в эту формулу я не вникал. whitefox появится — надеюсь, расскажет :-)

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


19/12/10
1546
Уточняю:$$\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))$$ Для всех $m$ таких, что $\gcd(m,a)\ne\gcd(m,b).$

Также должно быть:$$B=\left((x_b-x_a)^2+(y_b-y_a)^2\right)(a+b-2\gcd(a,b))$$

Ради удобства внёс исправления в исходный пост.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение22.11.2014, 15:24 


22/11/14

43
whitefox в сообщении #934630 писал(а):
Уточняю:$$\Psi'_x(a)=\Psi_x(a)+(x_b-x_a)(a-\gcd(a,b))$$Другие формулы изменяются аналогично.

Теперь претензий нет: спасибо.

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


25/08/12
171
Germany
whitefox в сообщении #934218 писал(а):
Сложность такого рассчета $O(1)$, что существенно меньше $O(n^4)$ при первом методе и $O(n^2)$ при втором.


I am not sure if this is true. The reason is that I think it is not sufficient to update only \Psi_x() and \Psi_y() for a and b but also you have to update it for all divisors of a and b. So I think it is still O(Log(n)).

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


16/08/05
1146
Yadryara в сообщении #934528 писал(а):
Рассмотрим простейший пример:

$\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} $$


Можно чуть подробнее объяснить как считаются $w_x$ и $w_y$?

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение22.11.2014, 16:06 


22/11/14

43
А в формуле $$B=\left((x_b-x_a)^2+(y_b-y_a)^2\right)(a+b)$$ ничего не нужно изменить? Например, если мы меняем местами в матрице два на два единицу и тройку, то ничего не меняется, но вклад от данного члена не исчезает.

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


19/12/10
1546
sevir в сообщении #934667 писал(а):
$$B=\left((x_b-x_a)^2+(y_b-y_a)^2\right)(a+b)$$

Эту формулу уточнил: $$B=\left((x_b-x_a)^2+(y_b-y_a)^2\right)(a+b-2\gcd(a,b))$$

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


29/04/13
7124
Богородский
dmd в сообщении #934662 писал(а):
Можно чуть подробнее объяснить как считаются $w_x$ и $w_y$?

Объяснение не очень простое. Вот формула имени whitefox:

whitefox в сообщении #930921 писал(а):
$$D'=\sum\limits_{k=2}^{\frac{n^2}2}\varphi(k)\cdot D_k$$Вычислять $D_k$ удобнее по следующей формуле:$$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)$$

Я подсчитал конкретные значения для 5-го порядка, но даже после сокращения в формуле для $D'$ оказалось $242$ члена. Формула делится на две симметричные половины по координатам $x$ и $y$. Вот одна половина этой формулы:

$D'(x) =53a^2 - 2a(11b + 5c + 3d + 5e + 7f + g + 7h + 3i + 2j + k + 2l + 2m + n + o + 2p) +
45b^2 - 2b(5c + 3d + 5e + 3f + g + 3h + 3i + 2j + k + 2l + 2m + n + o + 2p) +
37c^2 - 2c(d + 5e + f + g + h + i + 8j + k + 2l + 2m + n + o + 2p) +
41d^2 - 2d(e + 3f + 9g + 3h + 3i + k + 4l + n + o + 4q + 4t) +
31e^2 - 2e(f + g + h + i + 2j + k + 2l + 2m + n + o + 2p) +
29f^2 - 2f(g + 7h + 3i + k + n + o) +
31g^2 - 2g(h + i + k + 4l + n + o + 4q + 4t) +
29h^2 - 2h(3i + k + n + o) +
21i^2 - 2i(k + n + o) +
20j^2 - 2j(2l + 2m + 2p) +
23k^2 - 2k(6m + n + o + 6r) +
30l^2 - 2l(2m + 2p + 4q + 4t) +
26m^2 - 2m(2p + 6r) +
21n^2 - 2n(o + 10s) +
11o^2 +
14p^2 +
16q^2 - 2q * 4t +
12r^2 +
10s^2 +
16t^2$

Обозначения:

1. Обозначил координату $x$ для числа $24$ через $a$. У этого числа 6 нужных(2-12) делителей: 2, 3, 4, 6, 8, 12.
2. Обозначил координату $x$ для числа $12$ через $b$. У этого числа 5 нужных делителей: 2, 3, 4, 6, 12.
3. Обозначил координату $x$ для числа $18$ через $c$. У этого числа 4 нужных делителя: 2, 3, 6, 9.
4. Обозначил координату $x$ для числа $20$ через $d$. У этого числа 4 нужных делителя: 2, 4, 5, 10.
5. Обозначил координату $x$ для числа $6$ через $e$. У этого числа 3 нужных делителя: 2, 3, 6.
6. Обозначил координату $x$ для числа $8$ через $f$. У этого числа 3 нужных делителя: 2, 4, 8.
7. Обозначил координату $x$ для числа $10$ через $g$. У этого числа 3 нужных делителя: 2, 5, 10.
8. Обозначил координату $x$ для числа $16$ через $h$. У этого числа 3 нужных делителя: 2, 4, 8.
9. Обозначил координату $x$ для числа $4$ через $i$. У этого числа 2 нужных делителя: 2, 4.
10. Обозначил координату $x$ для числа $9$ через $j$. У этого числа 2 нужных делителя: 3, 9.
11. Обозначил координату $x$ для числа $14$ через $k$. У этого числа 2 нужных делителя: 2, 7.
12. Обозначил координату $x$ для числа $15$ через $l$. У этого числа 2 нужных делителя: 3, 5.
13. Обозначил координату $x$ для числа $21$ через $m$. У этого числа 2 нужных делителя: 3, 7.
14. Обозначил координату $x$ для числа $22$ через $n$. У этого числа 2 нужных делителя: 2, 11.
15. Обозначил координату $x$ для числа $2$ через $o$. У этого числа 1 нужный делитель: 2.
16. Обозначил координату $x$ для числа $3$ через $p$. У этого числа 1 нужный делитель: 3.
17. Обозначил координату $x$ для числа $5$ через $q$. У этого числа 1 нужный делитель: 5.
18. Обозначил координату $x$ для числа $7$ через $r$. У этого числа 1 нужный делитель: 7.
19. Обозначил координату $x$ для числа $11$ через $s$. У этого числа 1 нужный делитель: 11.
20. Обозначил координату $x$ для числа $25$ через $t$. У этого числа 1 нужный делитель: 5.

Всего играют 20 чисел из 25. Не играющие числа указал в теме чуть выше.

Дальше я взял из формулы все члены, содержащие $r$ и $s$, и выполнил нехитрые вычисления.

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


22/11/14

43
whitefox в сообщении #934705 писал(а):
sevir в сообщении #934667 писал(а):
$$B=\left((x_b-x_a)^2+(y_b-y_a)^2\right)(a+b)$$

Эту формулу уточнил: $$B=\left((x_b-x_a)^2+(y_b-y_a)^2\right)(a+b-2\gcd(a,b))$$

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

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение22.11.2014, 20:10 


16/08/05
1146
Как то не понятно получается. Допустим у нас есть случайный стартовый квадрат и мы для него посчитали две стартовые же таблицы $\Psi_x$ и $\Psi_y$ по формулам

$\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$

Видно, что это достаточно тяжёлый расчет.



Почему при перестановке двух чисел в квадрате оказалось не нужным полностью пересчитать таблицы $\Psi_x$ и $\Psi_y$, а достаточно только в них пересчитать по паре чисел формулами

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

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

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

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


Ну т.е. хорошо если это так. Но на первый взгляд выглядит неправдоподобно легко.

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


21/02/10
1594
Екатеринбург
sevir в сообщении #934565 писал(а):
Но не в этом суть: Herbert Kociemba пишет, что от всего этого мало толку.


Кажется понял о чем вы. Для конкурсной задачи, где $N \le 27$. Алгоритм с оценкой O(1) может оказаться даже хуже алгоритма с оценкой $O(\log N^2)$. По крайней мере выигрыш будет незначительным.

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


22/11/14

43
whitefox в сообщении #934218 писал(а):
Если поменять местами числа $a$ и $b$, то изменение числа Делакорта вычисляется по формуле: ...

Во всех формулах, приведенных Вами, координаты переставляемых чисел относятся к дообменной стадии? Скорее всего, вопрос относится к последним 4-м формулам.

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


25/08/12
171
Germany
Pavlovsky в сообщении #934815 писал(а):
sevir в сообщении #934565 писал(а):
Но не в этом суть: Herbert Kociemba пишет, что от всего этого мало толку.


Кажется понял о чем вы. Для конкурсной задачи, где $N \le 27$. Алгоритм с оценкой O(1) может оказаться даже хуже алгоритма с оценкой $O(\log N^2)$. По крайней мере выигрыш будет незначительным.


No. For n=27 the program runs 50x faster than before. So the the algorithm of whitefox is really a big progress. But I did not get better solutions.
But I claim that the algorithm of whitefox is not O(1) but O(Log(N))=O(Log(N^2)) as I wrote before.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение23.11.2014, 03:45 


20/01/13
62
Herbert Kociemba писал(а):
No. For n=27 the program runs 50x faster than before. So the the algorithm of whitefox is really a big progress. But I did not get better solutions.
But I claim that the algorithm of whitefox is not O(1) but O(Log(N))=O(Log(N^2)) as I wrote before.

In fact, Whitefox' algorithm is O(1) for computing the score of swapping a pair.

But the swapping requires to update at most 29+23 products, for example when swapping 720 and 672 on a 27x27 grid.
So the algorithm is indeed O(1+log(n))

Here are the worst values to swap:
(23)360: 2 3 4 5 6 8 9 10 12 15 18 20 24 30 36 40 45 60 72 90 120 180 360
(23)420: 2 3 4 5 6 7 10 12 14 15 20 21 28 30 35 42 60 70 84 105 140 210 420
(23)480: 2 3 4 5 6 8 10 12 15 16 20 24 30 32 40 48 60 80 96 120 160 240 480
(23)504: 2 3 4 6 7 8 9 12 14 18 21 24 28 36 42 56 63 72 84 126 168 252 504
(23)540: 2 3 4 5 6 9 10 12 15 18 20 27 30 36 45 54 60 90 108 135 180 270 540
(23)600: 2 3 4 5 6 8 10 12 15 20 24 25 30 40 50 60 75 100 120 150 200 300 600
(23)630: 2 3 5 6 7 9 10 14 15 18 21 30 35 42 45 63 70 90 105 126 210 315 630
(23)660: 2 3 4 5 6 10 11 12 15 20 22 30 33 44 55 60 66 110 132 165 220 330 660
(23)672: 2 3 4 6 7 8 12 14 16 21 24 28 32 42 48 56 84 96 112 168 224 336 672
(29)720: 2 3 4 5 6 8 9 10 12 15 16 18 20 24 30 36 40 45 48 60 72 80 90 120 144 180 240 360 720

Also, Herbert, the algorithm you use is called "Threshold Accepting".

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 373 ]  На страницу Пред.  1 ... 5, 6, 7, 8, 9, 10, 11 ... 25  След.

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



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

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


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

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