2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 
Сообщение15.02.2009, 20:12 
Заслуженный участник
Аватара пользователя


15/10/08
11536
Насколько я в состоянии понять, минимальности суммы относительно транспозиций для доказательства глобальной минимальности недостаточно, хотя условия, которым должны удовлетворять перестановки, для этого случая записываются очень просто... Интересно, введение этой вашей нормы как-то данную ситуацию исправляет?

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


03/01/09
1677
москва
Maxal
Вы не могли бы привести пример подстановок, на которых достигается минимум при $n=7$?

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


27/06/08
4058
Волгоград
mihiv писал(а):
Maxal
Вы не могли бы привести пример подстановок, на которых достигается минимум при $n=7$?

Хоть я и не Maxal, но пример вот:
$(1 2 3 4 5 6 7)$
$(5 4 6 3 2 7 1)$
$(7 5 2 3 4 1 6)$

Добавлено спустя 14 минут 29 секунд:

Re: по следам перестановочного неравенства

maxal писал(а):
Пусть $S_n$ - это множество всех перестановок чисел $\{1,2,\dots,n\}$.
Найдите значение
$$\min_{\pi,\sigma,\tau\in S_n} \sum_{j=1}^n \pi(j)\cdot \sigma(j)\cdot\tau(j)$$
как функцию от $n$.

Очевидная оценка снизу задается формулой $ceil(n \cdot n!^{\frac3n})$
Интересно, что для всех проверенных $n$ (до 7) оценка получается точной.

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


09/02/06
4382
Москва
VAL писал(а):
Очевидная оценка снизу задается формулой $ceil(n \cdot n!^{\frac3n})$
Интересно, что для всех проверенных $n$ (до 7) оценка получается точной.

Эта оценка, среднего арифметического члеов произведений по сравнению с их средним геометрическим действительно интересна. Но при больших n не будет точной. Интересно найти действительную константу а, для которого $S_{min}(n)=an^4(1+o(1))$. Нижняя оценка (от VAL) $a=e^{-3}$, у меня получилось верхняя $a=\frac{19}{324}$.

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


09/02/06
4382
Москва
Вот как достигается $a=\frac{1}{18}$.
Объединим в тройки $(1,n-1,n),(2,n-3,n-2),...$, которые будут встречаться трижды. Когда $n=3k+1$ останется тройка (k+1,k+1,k+1), когда $n=3k+2$ останутся тройки (k+1,k+2,k+1) дважды. Соответственно определим $\pi(i)=n-2i+1,\pi(n-2i+1)=n-2i+2,\pi(n-2i+2)=i,i\le [n/3]$, когда $n=3k+1$ определим $\pi(k+1)=k+1$, когда $n=3k+2$ $\pi(k+1)=k+2,\pi(k+2)=k+1$, другая перестановка $\sigma(i)=\pi^2(i),\tau(i)=i$.
При этом, в случае $n=3k$ получаем
$$S=3\sum_{i=1}^k(n+1-2i)(n+2-2i)i=\frac{k(k+1)}{2}[3n(n+2)-(4n+6)(2k+1)+6k(k+1)]=\frac{n^2(n+3)^2}{18}$$,
в случпе $n=3k+1$ $S=\frac{k(k+1)}{2}[9k^2+19k+8]+(k+1)^3$,
в случае $n=3k+2$ $S=\frac{k(k+1)}{2}[9k^2+24k+22]+2(k+1)^2(k+2)$.

 Профиль  
                  
 
 
Сообщение16.02.2009, 20:06 
Заслуженный участник
Аватара пользователя


15/10/08
11536
Люблю я такие темы. Полезно иной раз ощутить себя полным нулем. Это стимулирует )

P.S. Посоветуйте что нибудь почитать такого, чтобы после прочтения оного можно было понять хотя бы часть написанного Рустом )

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


08/04/08
8556
Есть такой алгоритм локальной оптимизации. Для
$S = \sum\limits_{j=1}^n \pi _j \sigma _j \tau _j$ и $S' = \sum\limits_{j=1}^n \pi '_j \sigma '_j \tau '_j$, где $(\forall j) \pi _j = \pi '_j, \sigma _j = \sigma '_j, \tau _j = \tau '_j$, кроме двух индексов $i,k$, для которых $\sigma '_i = \sigma _k, \sigma '_k = \sigma _i$.
Тогда $S' <S$ равносильно $sign(\pi _i \pi _k - \tau _i \tau _k) = - sign (\sigma _i - \sigma _k)$. Используя это свойство, можно брать некоторую $(\pi , \sigma , \tau)$ с ее $S$ и строить $(\pi ', \sigma ', \tau ')$ $S': S' <S$ и заходить в локальные максимумы. И запрограммировать легко.
Логичный вопрос: много ли локальных минимумов для $S_n$ и различаются ли значения в них?
Даже уже для $n=4$ есть несколько локальных минимумов и с разными значениями.

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


09/02/06
4382
Москва
Для сумм произведений из двух перестановок локальный минимум единственный (с противоположным упорядочением), к сожалению начиная для сумм произведений с трёх перестановок таких локальных минимумов много.

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


08/04/08
8556
Лучше такой алгоритм (модификация предыдущего).
Если надо минимизировать сумму $\sum\limits_{j=1}^n \tau_1(j)...\tau_m(j)$, где $\tau_i \in S_n$, то пишите матрицу $(\tau_i(j))$ из этих перестановок, далее цикл: выбираете $i$ и вычисляете еще строку $p(j)=\frac{\prod\limits_{i=1}^m \tau_i(j)}{\tau_i(j)}$, после чего числа $\tau_i(j), j=1..n$ сортируете в порядке, противоположном порядку $p(j)$. И так последовательно для всех строк (возможно несколько раз). Цикл прекращается, когда для всех $i$ $\tau_i$ уже не изменяются.
Для пространства величиной порядка $n!^m$ алгоритм довольно быстро загоняет сумму в локальный минимум. Опять же легко программируется. Причем очень много локальных минимумов, которые одновременно являются и глобальными. В то же время, чем меньше делителей имеет $n$, тем, скорее всего, больше шагов до локального минимума и меньше глобальных минимумов. Точнее не могу сказать.
Для $m=3$ (наш случай) у меня получилось $S(n)=1; 6; 18; 44; 89; 162; 271$. Проверьте, пожалуйста.

 Профиль  
                  
 
 
Сообщение25.02.2009, 11:45 
Модератор
Аватара пользователя


11/01/06
5660
Sonic86
см. A070735

С практической точки зрения представляет интерес вычисление этой функции для $n>15$.

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


09/02/06
4382
Москва
Можно посчитать наилучшую асимптотику. Пусть наименьшее k пробегает снизу шагом 1, средний шагает сверху с шагом h(k), а наибольшее шагает подряд сверху минуя только значения, где был средний. Тогда для h(k) должно выполняться
(1) $$\sum_{i=1}^k h(k) \ge 2k.$$
Соответственно
(2) $$\tau(i)=i,\sigma(k)=n+1-\sum_{i=1}^k h(k), \pi(k)= max (a), a<\pi(k-1),a\not =\sigma (j).$$
После выбора значений $\sigma(k),\pi (k)$, выбираем $\pi(k+1)$ согласно (2), а $\sigma(k+1)$ выбираем из условия (2) и так, чтобы число $\sigma(k+1)$ ближайшее целое к
$$\frac{1}{(k+1)\pi(k+1)}(\frac{n!}{\prod_{i=1}^k i\sigma(i)\pi(i)})^{\frac{3}{n-k}}.$$
Тогда получится асимптотический наименьшая сумма, которую можно ещё уменьшить только разбивая тройки, но главный коэффициент a перед $n^4$ не изменится.
Этот коэффициент вычисляется следующем образом. Вначале вычислим b из
$\frac{1-2b}{b}=e^{3-9b},b<1/3$. Получается $b=0,0945..$. Тогда наилучшее а находится из
$$a=(1-3b)b(1-2b)^2+3\int_0^b x(1-2x)^2dx=0.0548<1./18.$$

 Профиль  
                  
 
 
Сообщение26.02.2009, 16:03 


24/03/07
321
Sonic86 писал(а):
Для $m=3$ (наш случай) у меня получилось $S(n)=1; 6; 18; 44; 89; 162; 271$. Проверьте, пожалуйста.


Абсолютный минимум (и сами перестановки) можно посчитать простым алгоритмом перебора со сложностью $n!\cdot n \rm{log} n$ - перебираем $\pi$, умножаем на (1,2,\ldots,n), сортируем, умножаем на (n,n-1,\ldots,1). Вплоть до $n=11$ считается довольно быстро. Думаю, если оптимизировать, то вполне можно и для $n=16$ посчитать ... на кластере ))

Добавлено спустя 7 минут 16 секунд:

Кстати, в инете где-нибудь можно вычислительные ресурсы на халяву поюзать для численных расчетов? Так чтоб автоматически всё было :roll:

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


08/04/08
8556
Dandan! Может на компе и быстрее, но $n!$ перебирать в принципе не вариант.
Я пока в Excele смог найти (но за точность не ручаюсь):
$S(n) = 1; 6; 18; 44; 89; 162; 271; 428; 643; 931; 1304; 1781$ - первые 12 чисел. По ссылке у maxal там их 15, но я решил себя проверить. Вот у меня даже для $n=12$ требуется сделать только 10 сортировок, а не 10! и вообще я делал 5-6 испытаний на каждое $n$. Придется все же студию поставить и прогу написать - много времени уходит.

Добавлено спустя 3 минуты 59 секунд:

Ага! Ну вот: 2 ошибки.
maxal! Что Вы имели ввиду под "практической значимостью"?! :)

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


09/02/06
4382
Москва
Реализовал вышеуказанный алгоритм с наименьшем а. Даже без дополнительной оптимизации результаты почти оптимальные. В особенности в случае $n=3k$. Здесь единственное отличие при $n=12$ по указанному алгоритму $S=1782$ а в таблице $S=1781$.
Для ориентировки этот алгоритм дает $n=18,S=7842,n=21,S=13938$.

 Профиль  
                  
 
 
Сообщение26.02.2009, 20:48 
Модератор
Аватара пользователя


11/01/06
5660
Sonic86 в сообщении #189792 писал(а):
Что Вы имели ввиду под "практической значимостью"?!

Практическая значимость - пополнить A070735 новыми значениями. :lol:

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

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



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

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


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

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