fixfix
2014 dxdy logo

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

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




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


21/02/10
1594
Екатеринбург
Одномерное число Делакорта

Вариант 1
Дана полоса из N ячеек. Заполнить ячейки числами от 1 до N. Правила вычисления числа Делакорта такие же как в конкурсной задаче.

Вариант 2
Дана полоса из N ячеек. Заполнить ячейки числами от 1 до N*N. В каждую ячейку помещаем N чисел. Правила вычисления числа Делакорта такие же как в конкурсной задаче.

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


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #916120 писал(а):
Простые числа которые больше floor(N*N/2) можно ставить в середину квадрата.


В центр квадрата нужно ставить все простые числа. В самый центр 1 и больше floor(N*N/2). Остальные, чем меньше простое число тем ближе к центру.

Обоснование эвристики. Простые числа образуют группу для которых gcd(a,b)=1. Чем более плотную группу они образуют, тем больше больших расстояний останется для других чисел.

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


19/03/10
8952
 !  Pavlovsky, предупреждение за неиспользование $\TeX$ при записи формул.

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


16/08/05
1154

(немножко офтопа)


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


01/06/12
1016
Adelaide, Australia
А у меня идеи кончились. Похоже что для следующего прогреса надо оптимизировать код (не знаю как) и гонять компьютер сутками чтобы увеличить бал хотя бы на 0.001. Это мне не хочется делать и поэтому задача надоела. Оставляю её пока не появятся хорошие идеи...

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


21/02/10
1594
Екатеринбург
Возникли еще вспомогательные задачи.

Задача. Разбить числа из интервала [1...2k] на два подмножества по k чисел в каждом, так чтобы число Делакорта было максимальным. Если числа принадлежат разным подмножествам будем считать, что расстояние между ними 1. В противном случае растояние будет 0.

Задача. Дан квадрат сторона которого равна 1. В каждую вершину квадрата необходимо поместить k чисел из интервала [1...4k]. Найти решение с максимальным числом Делакорта.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение03.11.2014, 09:51 


16/08/05
1154

(ещё о матмоделировании)


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


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #924006 писал(а):
Возникли еще вспомогательные задачи.

Задача. Разбить числа из интервала [1...2k] на два подмножества по k чисел в каждом, так чтобы число Делакорта было максимальным. Если числа принадлежат разным подмножествам будем считать, что расстояние между ними 1. В противном случае растояние будет 0.

Задача. Дан квадрат сторона которого равна 1. В каждую вершину квадрата необходимо поместить k чисел из интервала [1...4k]. Найти решение с максимальным числом Делакорта.


Я не пробовал, но думаю смогу решить первую задачу почти оптимально для $2k<27^2$ методом отжига. Но я не вижу как это нам поможет решить оригинальную задачу. То есть, я вижу связь между задачами - первая задача как 1D аналог оригинальной задачи. Но решение упрощеного 1D варианта мало помогает решению 2D варианта имено потому что в 2D гораздо больше похожих вариантов расстоновки. Для 1D можно составить неплохое приблежение, ставим числа так: $(2k, k-1, 2k-4, ... ) (k, 2k-2, k-2, ... )$. Для каждого $2m$, $m$ лучше всего поставить в другое подмножество.

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


21/02/10
1594
Екатеринбург
Наличие в формуле числа Делакорта квадрата расстояния, делает задачу нелинейной. Максимальная сумма достигается когда числа размещаются в вершинах квадрата. Соответственно оригинальную задачу можно решать в два этапа.
Этап 1. Сначала решаем задачу
Pavlovsky в сообщении #924006 писал(а):
Задача. Дан квадрат сторона которого равна 1. В каждую вершину квадрата необходимо поместить k чисел из интервала [1...4k]. Найти решение с максимальным числом Делакорта

Этап 2. Квадрат разбиваем на 4 зоны, в каждую входит одна вершина квадрата и ее окрестности. В каждой зоне размещаем числа одного из 4-х множеств полученных на первом этапе. Максимизируем число Делакорта.

Pavlovsky в сообщении #924006 писал(а):
Задача. Разбить числа из интервала [1...2k] на два подмножества по k чисел в каждом, так чтобы число Делакорта было максимальным. Если числа принадлежат разным подмножествам будем считать, что расстояние между ними 1. В противном случае растояние будет 0.


Эта задача имеет очень важное теоретическое значение. Меня прежде всего интересует, является ли она NP-полной?

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


16/08/05
1154
Pavlovsky в сообщении #924006 писал(а):
Задача. Дан квадрат сторона которого равна 1. В каждую вершину квадрата необходимо поместить k чисел из интервала [1...4k]. Найти решение с максимальным числом Делакорта.

(MiniZinc модель)



(решения)



-- Вт ноя 04, 2014 00:26:55 --

Pavlovsky в сообщении #924006 писал(а):
Задача. Разбить числа из интервала [1...2k] на два подмножества по k чисел в каждом, так чтобы число Делакорта было максимальным. Если числа принадлежат разным подмножествам будем считать, что расстояние между ними 1. В противном случае растояние будет 0.

(модель)



(решения)


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


16/08/05
1154
Эх, кажется я не правильно суммы считал, "единичность" квадрата запутала. Видимо нужно, так же как и в общей задаче, отсекать лишние элементы доп. условием, типа такого
Код:
(ib > ia \/ (ia = ib /\ jb > ja))

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


01/06/12
1016
Adelaide, Australia
Не уверен что правильно понял условия задач, но вот мои лучшие результаты:

(Оффтоп)



(Оффтоп)



До сих пор сомневаюсь что это нам поможет. Например, я сравнил свои решения для оригинальной задачи (вроде у меня оптимальные для $N \leq 8$). В некоторых случаях, угловые цифры в моем решение были в одинаковых подмножествах.

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


21/02/10
1594
Екатеринбург
У меня уже для N=6 не оптимальное решение. Поэтому экспериментально проверить гипотезу затруднительно. Но мое лучшее решение для N=6 имеет k=9, score=1502. Впрочем это понятно, оно было получено по алгоритму в два этапа.

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

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

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение06.11.2014, 00:37 


16/08/05
1154

(про LocalSolver)


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


16/08/05
1154

(Оффтоп)


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

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



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

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


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

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