2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 19, 20, 21, 22, 23, 24, 25  След.
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение22.12.2014, 04:07 
Аватара пользователя


01/06/12
971
Adelaide, Australia
Ладно терять уже нечего - выкладываю свою самую лучшую идею! Допустим у нас есть множество $S$, где $gcd(a,b)=k$, для всех $a,b \in S$. То есть для всех пар чисел в множестве их gcd одинаково (равно $k$). Обозначим множеством $L$ расположением всех чисел в $S$ (для какого то решения), то есть $L_a=(x_a,y_a),~a \in S$.

Утверждение: Числа в $S$ можно оптимально раставить в $L$ за время $O(n^3)$, где $n=|S|$.

Для этого можно использовать Венгерский алгоритм решающий задачу о назначениях (https://ru.wikipedia.org/wiki/%D0%92%D0 ... 1%82%D0%BC). Обозначим $n \times n$ матрицу M, где $M_{ab}$ это цена поставки числа $a \in S$ на место $L_b$. Точнее $M_{ab}=\sum_{i \notin S} gcd(a,i)*[(x_b-x_i)^2+(y_b-y_i)^2]$. Важно отметить что для подсчёта $M_{ab}$ нам не надо учитывать как числа в $S$ влияют друг на друга. Это потому что для всех $a,b \in S$ имеем $gcd(a,b)=k$ и любая перестановка в $L$ будет давать одинаковый результат. Венгерский алгоритм даст лучшее назначение рядов к колонкам в $M$, то есть оптимальную растановку чисел в $S$ на места $L$.

Теперь как находить $S$? Есть много вариантов. Например $S_i = C * p^k_i$, где $p_i$ простое число (или 1), $k$ и $C$ положительные константы. Для 6х6 и $k=1$ получаем такие разные $S$:

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


А вот результат для $k=2$:

1 4 9 25
2 8 18
3 12 27
4 16 36
5 20
6 24
7 28
8 32
9 36


А также можно объеденить эти $S$ и получить более длиные, например:

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

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


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #950553 писал(а):
выкладываю свою самую лучшую идею!


Классная идея.

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


21/02/10
1594
Екатеринбург
На яхе https://groups.yahoo.com/neo/groups/AlZ ... opics/6470 опубликована формула:
whitefox в сообщении #930921 писал(а):
$$\frac{n^4(n^2-1)}6$$


Комментарий:

Цитата:
even though it seem to have little bearing on the current contest.


A245828 Szeged index of the grid graph P_n X P_n

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


19/12/10
1546
whitefox в сообщении #940692 писал(а):
Впрочем, конкурсная задача довольно специфична и легко сводится к почти линейной задаче о назначениях.
Pavlovsky в сообщении #940852 писал(а):
Но whitefox говорит об использовании специфики задачи при лианеризации. Подождем, может расколется?! :D
dimkadimon в сообщении #950553 писал(а):
Ладно терять уже нечего - выкладываю свою самую лучшую идею!
. . .
Для этого можно использовать Венгерский алгоритм решающий задачу о назначениях

Раскололся, но не я. :D

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


21/02/10
1594
Екатеринбург
Все это уже поздновато, я уже сдался. Венгерский алгоритм реализую, но это уже больше для тренировки и на будущее.

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


19/12/10
1546
Код собственно "венгерского алгоритма" можно взять здесь: http://e-maxx.ru/algo/assignment_hungary#6

-- 23 дек 2014, 09:20 --

И так как каждую строку матрицы $M$ можно уменьшить на константу, то вместо $M_{ab}$, определённого dimkadimon, можно использовать: $$M_{ab}=\left((x^2_b+y^2_b)\sum_{k\mid a}\varphi(k)|M_k^*|\right)-2\left(x_b\sum_{k\mid a}\varphi(k)\sum_{i\in M_k^*}x_i\right)-2\left(y_b\sum_{k\mid a}\varphi(k)\sum_{i\in M_k^*}y_i\right)$$ где $\bar S$ дополнение множества $S$ до $\{1,\dots,n^2\}$ и $M_k^*=M_k\cap\bar S$.

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


21/02/10
1594
Екатеринбург
Меня, для начала, больше интересуют теоретические аспекты.

Пусть у нас есть система множеств $\lbrace S_i \rbrace$. Таких что для любых $a,b \in S_i$ $gcd(a,b)=K_i$

Интересуют алгебраические свойства этой системы множеств, ну и свойсва связанные с задачей.

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


19/12/10
1546
Сомневаюсь, что система $\{S_i\}$ имеет какие-то алгебраические свойства.

Саму систему строю так:
  1. нахожу все максимальные множества попарно взаимно простых чисел не больших $n^2$;
  2. для каждого $2\leqslant K\leqslant\frac{n^2}2$ и каждого множества, найденного на предыдущем шаге, умножаю на $K$ каждый элемент;
  3. в полученных множествах удаляю числа большие $n^2$;
  4. удаляю из системы не максимальные множества и дубли.

Использование системы $\{S_i\}$ похоже на жадный вариант наискорейшего спуска, только во втором случае выбирается наилучшая транспозиция, а в первом -- наилучшая перестановка множества $S_i$, что даёт надежду выхода из локального оптимума. И так как множества $S_i$ перекрываются, то есть надежда приблизится к глобальному оптимуму.

Разумеется, результат зависит от порядка использования множеств $S_i$. Наверно, лучшим вариантом будет выбирать $S_i$ случайно с некоторым весом (равному, например, сумме весов элементов).

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


21/02/10
1594
Екатеринбург
Множеств $S_i$ очень много. Тут никакого венгерского алгоритма не хватит все их перебрать. А если учесть что результат зависит от порядка оптимизации множеств $S_i$... Нужно как то поделить множества $S_i$ на плохие и хорошие.

whitefox в сообщении #951080 писал(а):
случайно с некоторым весом (равному, например, сумме весов элементов)


Сразу применять эвристики как то не хочется. Надо хоть немного, для приличия, поскрипеть мозгами.

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


01/06/12
971
Adelaide, Australia
whitefox в сообщении #951062 писал(а):
И так как каждую строку матрицы $M$ можно уменьшить на константу, то вместо $M_{ab}$, определённого dimkadimon, можно использовать:

Не понимаю, что это нам дает?

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


19/12/10
1546
dimkadimon в сообщении #951199 писал(а):
Не понимаю, что это нам дает?

Сокращение времени на вычисление матрицы $M.$

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


21/02/10
1594
Екатеринбург
Провел эксперименты с венгерским алгоритмом по методу Каменцкого. Результаты довольно скромные, расчитывал на гораздо большее.

Конкурс вышел на финишную прямую. Активность лидеров потихоньку спадает.
Вот думаю чем заняться последнюю неделю.
1) Можно запустить все наличные алгоритмы и получить результаты где то в районе 100-го места. 100-е место не вдохновляет.
2) Или похулиганить?! Сосредоточится на одном N и попробовать установить рекорд. Как думает сообщество, для какого N есть большие шансы найти рекордное решение?

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


09/06/12
26
Perhaps the maximum for N=16. The best estimate I've seen seems furthest away from the curve of Pavlovsky upper bounds.

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


14/12/14
27
Or try to find Max12. The corresponding record seems to be held by not too many participants.

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


21/02/10
1594
Екатеринбург
Scryer в сообщении #951648 писал(а):
for N=16

yae9911 в сообщении #951655 писал(а):
find Max12


В этой теме уже высказывалось удивление, что новые рекорды до сих пор находят для относительно небольших N. И даже давалось этому объяснение. Но все таки, найти новый рекорд для N=12 это наверно перебор.

-- Чт дек 25, 2014 09:40:39 --

$$\frac{n^4(n^2-1)}6$$

whitefox не привел доказательство этой формулы и никто у него не поинтересовался как он это сделал. Поэтому привожу свой вывод формулы.

1) Посчитать сумму квадратов расстояний между ячейками в квадрате NxN, можно отдельно по координатам x и y.

2) Количество ячеек для которых $|x_i-x_j|=k$ равно
$$N^2(N-k)$$

3) Получается такая формула для суммы квадратов расстояний между ячейками.
$$2N^2 \sum_{k=1}^{N-1}(N-k)k^2$$

4) Далее воспользуемся формулами расчета суммы натуральных чисел в степени k (k=2,3) и получим исходную формулу.

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

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



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

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


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

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