2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 25  След.
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение06.11.2014, 15:47 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #926960 писал(а):
У меня уже для N=6 не оптимальное решение. Поэтому экспериментально проверить гипотезу затруднительно. Но мое лучшее решение для N=6 имеет k=9, score=1502. Впрочем это понятно, оно было получено по алгоритму в два этапа.

Для N=4 лучшее решение (оптимальное) имеет k=4, score=240.

Так что доводы в пользу двух-этапного алгоритма есть!


Да возможно этот метод даст хорошие решения. Думаю для больших N оптимальных решений много и поэтому хотя бы одно из них может иметь такой вид.

Кстати мне кажется алгоритм можно улучшить. Можно разбить второй этап (где мы оптимизируем четвертинки) в несколько маленьких этапов. В каждом маленьком этапе оптимизируем самые крайние места, начиная с углов. Например вот возможный порядок оптимизации для 8x8:

12344321
23455432
34566543
45677654
45677654
34566543
23455432
12344321

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


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #927496 писал(а):
Кстати мне кажется алгоритм можно улучшить.


Ну у меня тоже много соображений по этому поводу.

Например.
Будем называть весом числа k:
$\sum\limits_{i \ne k}{nod(i,k)}$

Веса чисел для N=4

(Оффтоп)

12 23
6 17
8 17
16 17
15 16
10 15
4 13
14 13
3 8
5 8
9 8
2 7
7 6
11 0
13 0


Как это использовать, очевидно. Чем выше вес числа тем ближе он должен быть к углам квадрата.

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

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


24/11/10
48
Цитата:
Будем называть весом числа k:
$\sum\limits_{i \ne k}{nod(i,k)}$

Веса чисел для N=4

(Оффтоп)

12 23
6 17
8 17
16 17
15 16
10 15
4 13
14 13
3 8
5 8
9 8
2 7
7 6
11 0
13 0


Я не понял, почему, к примеру, у вас для 2 вес 7 а не 14?

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


21/02/10
1594
Екатеринбург
Vitaly12 в сообщении #927841 писал(а):
Я не понял, почему, к примеру, у вас для 2 вес 7 а не 14?


Ой извиняюсь. Я считаю по предложенной WhiteFox методе. НОД уменьшается на единицу.

$\sum\limits_{i \ne k}{(nod(i,k)}-1)$

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


24/11/10
48
Цитата:
Я считаю по предложенной WhiteFox методе. НОД уменьшается на единицу.


А как насчет если просто не прибавлять к сумме НОДы равные единице? Результат для сравнения чисел будет тот же, или так хуже?

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


16/08/05
1146
Квадратность задачи можно развернуть в чисто векторное описание.

Пусть для квадрата $n\times n$ нужно найти вектор $X$ длиной $N=n^2$. Тогда искомая сумма зависит от двух статичных таблиц GCD и DIST размером $N\times N$. Статичных в том смысле, что их не нужно пересчитывать в процессе вычислений и достаточно посчитать в начале.

(код GCD и DIST)

Код:
n= 3; N= n^2;

GCD= matrix(N, N, i, j, gcd(i, j));

DIST= matrix(N, N);
for(a=1, N,
ia= a\n; ja= a%n; if(ja, ia++, ja= n);
for(b=1, N,
  ib= b\n; jb= b%n; if(jb, ib++, jb= n);
  if(ib > ia || (ia == ib && jb > ja), DIST[a,b]= (ia - ib)^2 + (ja - jb)^2, DIST[a,b]= 0)
));

(GCD и DIST для n=3)

Код:
? GCD
%4 =
[1 1 1 1 1 1 1 1 1]
[1 2 1 2 1 2 1 2 1]
[1 1 3 1 1 3 1 1 3]
[1 2 1 4 1 2 1 4 1]
[1 1 1 1 5 1 1 1 1]
[1 2 3 2 1 6 1 2 3]
[1 1 1 1 1 1 7 1 1]
[1 2 1 4 1 2 1 8 1]
[1 1 3 1 1 3 1 1 9]

? DIST
%5 =
[0 1 4 1 2 5 4 5 8]
[0 0 1 2 1 2 5 4 5]
[0 0 0 5 2 1 8 5 4]
[0 0 0 0 1 4 1 2 5]
[0 0 0 0 0 1 2 1 2]
[0 0 0 0 0 0 5 2 1]
[0 0 0 0 0 0 0 1 4]
[0 0 0 0 0 0 0 0 1]
[0 0 0 0 0 0 0 0 0]

(GCD и DIST для n=4)

Код:
? GCD
%14 =
[1 1 1 1 1 1 1 1 1  1  1  1  1  1  1  1]
[1 2 1 2 1 2 1 2 1  2  1  2  1  2  1  2]
[1 1 3 1 1 3 1 1 3  1  1  3  1  1  3  1]
[1 2 1 4 1 2 1 4 1  2  1  4  1  2  1  4]
[1 1 1 1 5 1 1 1 1  5  1  1  1  1  5  1]
[1 2 3 2 1 6 1 2 3  2  1  6  1  2  3  2]
[1 1 1 1 1 1 7 1 1  1  1  1  1  7  1  1]
[1 2 1 4 1 2 1 8 1  2  1  4  1  2  1  8]
[1 1 3 1 1 3 1 1 9  1  1  3  1  1  3  1]
[1 2 1 2 5 2 1 2 1 10  1  2  1  2  5  2]
[1 1 1 1 1 1 1 1 1  1 11  1  1  1  1  1]
[1 2 3 4 1 6 1 4 3  2  1 12  1  2  3  4]
[1 1 1 1 1 1 1 1 1  1  1  1 13  1  1  1]
[1 2 1 2 1 2 7 2 1  2  1  2  1 14  1  2]
[1 1 3 1 5 3 1 1 3  5  1  3  1  1 15  1]
[1 2 1 4 1 2 1 8 1  2  1  4  1  2  1 16]

? DIST
%15 =
[0 1 4 9  1 2 5 10  4 5 8 13  9 10 13 18]
[0 0 1 4  2 1 2  5  5 4 5  8 10  9 10 13]
[0 0 0 1  5 2 1  2  8 5 4  5 13 10  9 10]
[0 0 0 0 10 5 2  1 13 8 5  4 18 13 10  9]
[0 0 0 0  0 1 4  9  1 2 5 10  4  5  8 13]
[0 0 0 0  0 0 1  4  2 1 2  5  5  4  5  8]
[0 0 0 0  0 0 0  1  5 2 1  2  8  5  4  5]
[0 0 0 0  0 0 0  0 10 5 2  1 13  8  5  4]
[0 0 0 0  0 0 0  0  0 1 4  9  1  2  5 10]
[0 0 0 0  0 0 0  0  0 0 1  4  2  1  2  5]
[0 0 0 0  0 0 0  0  0 0 0  1  5  2  1  2]
[0 0 0 0  0 0 0  0  0 0 0  0 10  5  2  1]
[0 0 0 0  0 0 0  0  0 0 0  0  0  1  4  9]
[0 0 0 0  0 0 0  0  0 0 0  0  0  0  1  4]
[0 0 0 0  0 0 0  0  0 0 0  0  0  0  0  1]
[0 0 0 0  0 0 0  0  0 0 0  0  0  0  0  0]


При этом считать сумму нужно по ненулевому треугольнику матрицы DIST. Количество элементов суммы легко определить для каждого $N$

(кол-во членов суммы)

Код:
? n=3;N=n^2;sum(i=1,N-1,i)
%17 = 36
? n=4;N=n^2;sum(i=1,N-1,i)
%18 = 120
? n=5;N=n^2;sum(i=1,N-1,i)
%19 = 300
? n=6;N=n^2;sum(i=1,N-1,i)
%20 = 630


Количество единиц в треугольнике DIST зададут константу (только когда ищем максимум суммы) в искомой сумме, и оно равно (возможно, не уверен) $2(N-n)$. Количество единиц в соответствующем треугольнике матрицы GCD больше, поэтому смотреть нужно на единицы матрицы DIST.

Сама же сумма считается как
Код:
sum(i=1,N-1,sum(j=i+1,N,GCD[X[i],X[j]]*DIST[i,j]))

Это включая единицы, т.е. без вычета константы. Можно попытаться посчитать её без единиц с вычетом константы, что несколько сократит вычисления.

Итог. Задача выглядит NP-трудной. Ни веса чисел, ни разбиение квадрата на подквадраты не помогают. Получающиеся оптимумы не соответсвуют действительным. Пытаюсь в "векторной" картинке разглядеть хоть какую-то эвристику, в "квадратной" картине всё выглядит ещё сложнее.

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


22/03/09
8
Ворнежский Гос. Университет
Уже четвертый день сайт конкурса недоступен

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


21/02/10
1594
Екатеринбург
Немного о весовой функции.

Гипотеза. Пусть K число с максимальным весом. Тогда в решении с максимальным числом Делакорта, числа K и K/2 находятся в противоположных углах квадрата.

Примеры.
N=4 числа 16,8
N=5 числа 24,12
N=6 числа 36,18

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение14.11.2014, 12:35 


16/08/05
1146
Pavlovsky

Это понятно. Не понятно другое со второй диагональной парой углов, допустим на примере n=4. Почему в фактическом оптимуме во второй паре углов стоят числа (12,15), а не (12,6)? Казалось бы положить в сумму член 18*6 эффектнее, чем 18*3, но нет же. Почему совокупный вес (12,15) оказался сильнее, чем у пары (12,6)?

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


21/02/10
1594
Екатеринбург
Весовая функция всего лишь эвристика.
12 23
6 17
8 17
16 17
15 16

Число 15 на пятом месте. То есть достаточно хороший кандидат, чтобы поставить его в угол.

-- Пт ноя 14, 2014 15:34:35 --

dmd в сообщении #930805 писал(а):
Почему совокупный вес (12,15) оказался сильнее, чем у пары (12,6)?


Ну и конечно есть повод задуматься. Может как то уточнить весовую функцию или ее применение?

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


01/06/12
1016
Adelaide, Australia
dmd в сообщении #930805 писал(а):
Почему совокупный вес (12,15) оказался сильнее, чем у пары (12,6)?


Не забывайте про другие числа. 12 стоит в углу чтобы быть напротив 4 и 6, а 15 напротив 10. Если 15 заменить на 6, тогда 15 будет ближе к 10 и давать меньше очков (*). Тут все связано и поэтому эвристики не всегда будут работать.

(*) Правда пара (12,6) будет давать больше, но видимо не достаточно больше чтобы покрыть потерю от пары (10,15).

-- 14.11.2014, 20:32 --

Pavlovsky в сообщении #930790 писал(а):
Гипотеза. Пусть K число с максимальным весом. Тогда в решении с максимальным числом Делакорта, числа K и K/2 находятся в противоположных углах квадрата.


Для 9x9 у меня стоят цифры (по часовой стрелке): 80, 36, 60, 72. 40 почти напротив 80. Для 10х10 у меня: 96, 90, 84, 60. 48 почти напротив 96, 42 почти напротив 84, а 45 почти напротив 90. Поэтому есть подозрение что гипотеза не работает.

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


19/12/10
1546
Обозначим через $M_k$ множество целых положительных чисел не больших $n^2$ и кратных $k,$ и пусть $x_i,y_i$ обозначают $x$ и $y$ координаты числа $i$ соответственно, а $\bar x_k,\bar y_k$ обозначают средние $x$ и $y$ координаты всех чисел множества $M_k.$ И пусть $\varphi(k),$ как обычно, обозначает функцию Эйлера.

Тогда число Делакорта равно:$$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)$$В частности, из этой формулы следует утверждение Pavlovsky
Pavlovsky в сообщении #916827 писал(а):
Для простоты изложения, пусть N=4.
Сформируем группы чисел.
2,4,6,8,10,12,14,16
3,6,9,12,15
4,8,12,16
5,10,15
6,12
7,14
8,16

Утверждение. Если можно заполнить квадрат 4х4 таким образом, что для каждой группы чисел сумма расстояний между ячейками минимально возможная. Тогда такое заполнение является минимально возможным решением.
Также замечу, что согласно данному ранее определению $D^*$
whitefox в сообщении #916964 писал(а):
Иными словами для правильного подсчета $D^*$ нужно $\gcd(a,b)$ уменьшить на единицу.
$$D^*=\sum\limits_{k=2}^{\frac{n^2}2}\varphi(k)\cdot D_k$$Вычислять $D_k$ удобнее по следующей формуле:$$D_k=\left(\left\lfloor\frac{n^2}k\right\rfloor\sum\limits_{i\in M_k}\left(x^2_i+y^2_i\right)\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)$$

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


29/04/13
7131
Богородский
whitefox, спасибо. Хотя удивляет сам факт свободного обсуждения конкурсных задач.

whitefox в сообщении #930921 писал(а):
Тогда число Делакорта равно:$$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)$$

Это верно, хотя Вами и не определён множитель $\varphi(k)$. Впрочем, понятно, что это за птица:

$\varphi(2)=1$
$\varphi(3)=2$
$\varphi(4)=2$
$\varphi(5)=4$
$\varphi(6)=2$
$\varphi(7)=6$
...


whitefox в сообщении #930921 писал(а):
Вычислять $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)$$

А вот это неверно. Формула не прошла численную проверку. Если не согласны, будем разбираться предметно.

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


19/12/10
1546
Yadryara в сообщении #931202 писал(а):
Хотя удивляет сам факт свободного обсуждения конкурсных задач.

У Zimmerman к этому вопросу довольно либеральный подход. Обсуждение конкурсных задач не только не запрещено, но даже приветствуется. Безусловно запрещены только две вещи:
  • публикация готовых решений, годных к вводу на конкурс;
  • публикация кодов программ поиска таких решений.
При этом можно сообщать полученные значения max и min, будь то правда или нет, а также приводить используемые алгоритмы.

К сожалению, сайт конкурса сейчас не доступен, а то привёл бы соответствующую цитату из правил.

Yadryara в сообщении #931202 писал(а):
хотя Вами и не определён множитель $\varphi(k)$. Впрочем, понятно, что это за птица
Обычно, если определение $\varphi(k)$ не приводится, то под этим понимается тотиента Эйлера. Это обозначение стало уже настолько привычным, что функцию Эйлера часто просто называют фи-функцией. Впрочем, ваше замечание учёл и свой предыдущий пост дополнил.

Yadryara в сообщении #931202 писал(а):
А вот это неверно. Формула не прошла численную проверку. Если не согласны, будем разбираться предметно.

Ведь это формула дисперсии, не так ли?
А потому справедливо общее правило $$D[X] = M\left[(X -M[X])^2\right]=M[X^2]-\left(M[X]\right)^2$$

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


29/04/13
7131
Богородский
whitefox в сообщении #931206 писал(а):
К сожалению, сайт конкурса сейчас не доступен, а то привёл бы соответствующую цитату из правил.

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

whitefox в сообщении #931206 писал(а):
Ведь это формула дисперсии, не так ли?
А потому справедливо общее правило $$D[X] = M\left[(X -M[X])^2\right]=M[X^2]-\left(M[X]\right)^2$$

Я ещё раз перепроверю свои расчёты. Но это будет не быстро.

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

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



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

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


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

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