2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 
Сообщение27.02.2009, 07:17 
Заслуженный участник


08/04/08
8462
Понятно :-)
Руст!
То есть $S(n) \sim a n^4$ и $a$ - трансцендентно?!
И еще: получается Вы строите перестановку (задаете для нее формулу), сумма на которой не минимальна, но минимальна асимптотически? Я правильно понял?

Коэффициенты численно такие: $b = 0,094541578, a=0,059713900$ (Excel).

 Профиль  
                  
 
 
Сообщение27.02.2009, 08:03 
Заслуженный участник


09/02/06
4342
Москва
Sonic86 писал(а):
Понятно :-)
Руст!
То есть $S(n) \sim a n^4$ и $a$ - трансцендентно?!
И еще: получается Вы строите перестановку (задаете для нее формулу), сумма на которой не минимальна, но минимальна асимптотически? Я правильно понял?

Коэффициенты численно такие: $b = 0,094541578,a=0,059713900$ (Excel).

Да, только расчёты с двойной точностью на Си дали $b=0.0945415777.., \ln(\frac 1b -2)=3-9b, a=b-5.5b^2+12b^3-9b^4=0.0548032...$. a выражается от b как многочлен четвёртой степени, я раньше ошибся в этих коэффициентах.

 Профиль  
                  
 
 
Сообщение27.02.2009, 12:55 
Заслуженный участник


08/04/08
8462
Так выглядит распределение $S$ для $n=4$ при всевозможных перестановках :D

(не получилось вставить диаграмму из Excel - научите :-( )

Для $S=44...100$ значения такие (по порядку):
8 24 24 6 12 6 45 2 24 15 12 45 6 9 12 12 45 9 18 9 6 12 9 9 12 15 30 12 0 8 9 12 15 6 0 6 12 3 2 9 3 12 0 3 0 3 15 0 0 3 0 3 0 3 0 0 1

Что это за распределение?

 Профиль  
                  
 
 
Сообщение02.03.2009, 06:56 
Заслуженный участник


08/04/08
8462
Ура! Мужики! Я прогу написал! Если научусь цитировать, то могу код выложить, на С++. Как и говорил, там тупо m раз локальная оптимизация со случайным поиском, так что значения не точные, а только с вероятностью, только вот не знаю, с какой :-( Я по нескольку сотен испытаний проводил (от 200 до 1000 с ростом n).
$n=1..10$ $S(n)=1; 6; 18; 44; 89; 271; 428; 642; 930$.
$n=11..20$ $S(n)=1304; 1781; 2377; 3111; 4002; 5073; 6345; 7842; 9588; 11610$.
$n=21..30$ $S(n)=13934; 16592; 19613; 23029; 26887; 31179; 35979; 41316; 47223; 53742$.
$n=31..40$ $S(n)=60912; 68776; 77379; 86764; 96979; 108069; 120083; 133075; 147091; 162185$.
$n=41..50$ $S(n)= 178406; 195819; 214472; 234433; 255753; 278496; 302720; 328491; 355878; 384940$.

Можно было бы сделать эмпирическую вероятностную оценку, но без знания распределения это равносильно огромному количеству испытаний, которое (для меня) просто подтвердит факт того, что $S(n)$ равно тому-то. Иначе, чтобы иметь хотя бы общую формулу от n, надо знать распределение $S(n)$, которое генерится алгоритмом, которое, увы, узнать сложнее, чем распределение $S(n)$ само по себе (а само по себе оно довольно сложное). Или надо хотя бы какое-то общее представление о пространстве сумм иметь...

Например, для $n=20$ у меня при 100 испытаниях получилось такое распределение суммы по значениям от 11610 до 11630:
1 4 5 11 11 8 14 6 11 9 8 4 1 0 3 1 1 1 0 1 0
Если 11610 - действительно минимум, то грубо обобщая, можно утверждать, что нескольких сотен испытаний должно хватать. Хотя, конечно, не знаю.
Распределение это, очевидно, не нормальное. Хи-квадрат с этим согласен.

 Профиль  
                  
 
 Re: по следам перестановочного неравенства
Сообщение25.11.2018, 09:55 
Модератор
Аватара пользователя


11/01/06
5419
Sonic86, текущие известные значения $S(17)=6344$ и $S(19)=9587$ меньше полученных вами.

 Профиль  
                  
 
 Re: по следам перестановочного неравенства
Сообщение26.11.2018, 09:05 


20/04/10
528
Русь
Для проверки написал прогу близкую к предложенной Sonic86. Сейчас железо помощнее нежели в девятом году - можно сделать больше оптимизаций на случайно сгенерированных данных. Для каждого $17\leqslant n\leqslant 34$ я делал по $20000$ проверок, вот результаты:
Код:
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17},{16,15,11,12,8,13,4,7,5,10,6,3,2,14,9,17,1},{17,13,12,8,10,5,14,7,9,4,6,11,15,2,3,1,16},6344}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18},{18,16,10,14,9,11,6,12,4,5,7,13,3,8,2,15,1,17},{17,14,15,8,10,7,11,5,13,9,6,3,12,4,16,2,18,1},7842}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19},{19,16,14,12,15,10,5,8,6,9,4,11,3,13,7,17,2,1,18},{18,17,13,11,7,9,15,8,10,6,12,4,14,3,5,2,16,19,1},9587}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20},{20,18,16,14,8,9,11,15,10,4,6,5,12,3,7,13,2,17,1,19},{19,17,13,11,15,12,8,5,7,16,9,10,4,14,6,3,18,2,20,1},11610}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21},{20,19,15,12,14,17,6,8,13,9,7,5,4,10,16,11,3,2,18,21,1},{21,18,16,15,10,7,17,11,6,8,9,12,13,5,3,4,14,19,2,1,20},13933}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22},{22,20,18,14,13,11,12,6,15,5,9,17,7,8,3,10,16,4,2,19,1,21},{21,19,15,14,13,12,10,17,6,16,8,4,9,7,18,5,3,11,20,2,22,1},16592}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23},{22,21,19,12,15,14,13,9,17,5,6,11,8,16,4,7,18,3,10,2,20,23,1},{23,20,16,19,12,11,10,13,6,18,14,7,9,4,15,8,3,17,5,21,2,1,22},19612}

{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24},{24,22,20,18,14,16,9,11,6,15,12,17,4,8,7,5,10,19,3,13,2,21,1,23},{23,21,17,14,15,11,16,12,19,7,8,5,20,9,10,13,6,3,18,4,22,2,24,1},23028}

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

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

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

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

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

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

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

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

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

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

 Профиль  
                  
 
 Re: по следам перестановочного неравенства
Сообщение08.12.2018, 16:44 


20/04/10
528
Русь
Приведу улучшенные результаты, может быть пригодятся. Увеличив для каждого $n$ число попыток отыскать оптимальное решение и, помимо $swap(a_i,b_j)$, где $a_i, b_j$ элементы одной перестановки, использовав $swap1(a_i, b_j, c_j, d_k)$, где $a_i, b_i$ и $c_j, d_k$ элементы двух различных перестановок, удалось найти решения у которых $S(22)=16591$, $S(26)=31177$, $S(27)=35976$, $S(28)=41314$, $S(29)=47221$, $S(31)=60908$, $S(32)=68774$, $S(33)=77375$, $S(34)=86762$.

Решения:

(Оффтоп)

Код:
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22},
{22,20,18,16,15,11,8,10,13,5,12,4,7,14,3,17,6,9,2,19,1,21},
{21,19,15,13,11,12,14,10,7,16,6,17,9,4,18,3,8,5,20,2,22,1},16591}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26},
{25,24,20,18,19,22,14,11,7,8,15,12,9,13,5,16,4,6,17,21,3,10,2,23,26,1},
{26,23,22,18,14,10,13,15,21,16,8,9,11,7,17,5,19,12,4,3,20,6,24,2,1,25},31177}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27},
{26,24,23,20,18,22,12,15,16,11,6,17,8,7,5,10,14,4,19,9,3,13,21,25,2,27,1},
{27,25,21,18,16,11,17,12,10,13,22,7,14,15,19,9,6,20,4,8,23,5,3,2,24,1,26},35976}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28},
{27,26,24,21,19,17,16,18,10,8,12,9,14,5,15,20,23,11,4,13,6,3,7,22,2,25,28,1},
{28,25,22,19,17,16,14,11,18,20,12,15,9,23,7,5,4,8,21,6,13,24,10,3,26,2,1,27},41314}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29},
{29,26,25,23,21,15,18,10,11,16,20,12,9,6,13,19,8,14,4,22,17,5,3,24,7,27,2,1,28},
{28,27,24,19,17,20,14,22,18,11,8,12,15,21,9,6,13,7,23,4,5,16,25,3,10,2,26,29,1},47221}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31},
{30,28,27,22,24,21,14,19,20,9,13,18,15,25,11,7,8,6,16,5,4,12,23,10,17,3,26,29,2,31,1},
{31,29,26,24,18,17,22,14,12,23,15,10,11,6,13,19,16,20,7,21,25,8,4,9,5,27,3,2,28,1,30},60908}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32},
{32,30,27,24,26,17,21,14,10,20,16,22,9,12,7,18,8,13,11,23,19,15,4,25,5,6,28,3,2,29,1,31},
{31,29,28,24,18,23,16,21,26,12,13,9,20,14,22,8,17,10,11,5,6,7,25,4,19,15,3,27,30,2,32,1},68774}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33},{33,31,29,25,24,22,16,18,13,17,9,19,14,26,21,8,15,12,5,10,20,23,7,27,6,11,4,3,28,2,30,1,32},{32,30,28,25,21,19,23,18,22,15,26,11,14,7,8,20,10,12,27,13,6,5,16,4,17,9,24,29,3,31,2,33,1},77375}
{{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34},{34,32,30,27,28,21,16,22,24,13,15,10,18,14,23,12,6,17,8,20,7,25,5,19,11,4,26,9,3,29,2,31,1,33},{33,31,29,26,20,22,25,16,13,21,17,23,12,14,8,15,28,9,18,7,19,5,24,6,10,27,4,11,30,3,32,2,34,1},86762}

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу Пред.  1, 2, 3

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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