2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 AZsPCs: Hexagonal Neighbors
Сообщение03.11.2018, 18:25 


16/08/05
1146
Стартовал новый конкурс: заполняем шестиугольные сетки

http://azspcs.com/Contest/HexagonalNeighbors

 Профиль  
                  
 
 Re: AZsPCs: Hexagonal Neighbors
Сообщение05.11.2018, 17:14 


01/11/17
42
Используется синтаксис Python
 1 . . . . . . 1 . . . . . . 1 . . .
. . . 1 . . . . . . 1 . . . . . . 1
 . . . . . 1 . . . . . . 1 . . . . .
. 1 . . . . . . 1 . . . . . . 1 . .
 . . . 1 . . . . . . 1 . . . . . . 1
. . . . . . 1 . . . . . . 1 . . . .
 . 1 . . . . . . 1 . . . . . . 1 . .
. . . . 1 . . . . . . 1 . . . . . .
 . . . . . . 1 . . . . . . 1 . . . .
. . 1 . . . . . . 1 . . . . . . 1 .
 . . . . 1 . . . . . . 1 . . . . . .

On infinite plane 1 must be placed not rarely than once in each 7 cells.
In the above example the rest of the cells could be safely populated by 2.

 Профиль  
                  
 
 Re: AZsPCs: Hexagonal Neighbors
Сообщение05.11.2018, 18:37 


01/11/17
42
Actually filling the whole plane with 1,2,3,4,5,6,7 in this way is trivial.

 Профиль  
                  
 
 Re: AZsPCs: Hexagonal Neighbors
Сообщение05.11.2018, 20:20 


16/08/05
1146
Нам же надо не тривиальное заполнение, а оптимальное - чтоб сумма была максимальна. Другой момент, наложите на бесконечную плоскость фактическую сетку конкретного n. Где гарантия, что в итоге граничные ячейки будут иметь всех нужных соседей?

 Профиль  
                  
 
 Re: AZsPCs: Hexagonal Neighbors
Сообщение05.11.2018, 21:37 


01/11/17
42
This was only a first approximation for the upper limit under assumption that the patches required for fixing the borders don't penetrate to the central cells.
Filling the plane with the following pattern gives average value of 4 per cell.
Используется синтаксис C
 1 2 3 6 7 5 4 1 2 3 6 7 5 4 1 2 3 6
7 5 4 1 2 3 6 7 5 4 1 2 3 6 7 5 4 1
 3 6 7 5 4 1 2 3 6 7 5 4 1 2 3 6 7 5
4 1 2 3 6 7 5 4 1 2 3 6 7 5 4 1 2 3
 7 5 4 1 2 3 6 7 5 4 1 2 3 6 7 5 4 1
2 3 6 7 5 4 1 2 3 6 7 5 4 1 2 3 6 7
 4 1 2 3 6 7 5 4 1 2 3 6 7 5 4 1 2 3
6 7 5 4 1 2 3 6 7 5 4 1 2 3 6 7 5 4
 2 3 6 7 5 4 1 2 3 6 7 5 4 1 2 3 6 7
5 4 1 2 3 6 7 5 4 1 2 3 6 7 5 4 1 2
 6 7 5 4 1 2 3 6 7 5 4 1 2 3 6 7 5 4
 

I wouldn't be surprised if any usage of 7 leads to a non-optimal distribution for honeycombs of finite size.

 Профиль  
                  
 
 Re: AZsPCs: Hexagonal Neighbors
Сообщение05.11.2018, 21:48 
Заслуженный участник


04/03/09
906
Можно получить верхнюю оценку на сумму чисел.
Из каждой клетки нарисуем стрелочки до некоторых ее соседей таким образом: если в клетке число $k$, то проводим $k-1$ стрелочек, по одной в $1,2, ... , k-1$. Например, если у клетки с $4$ соседи $(1,1,2,3,5,7)$, то проводим три стрелки - одну в любую из единиц, одну в двойку и одну в тройку. Тогда суммаррное количестве стрелок равно сумме чисел в клетках минус количество клеток, т.е. равно оценке, которую мы получим за расстановку. Но количество стрелок не превосходит количества пар соседних клеток, коих $(3n-3)(3n-2)$. Полученные участниками оценки находятся довольно близко к этому пределу.

 Профиль  
                  
 
 Re: AZsPCs: Hexagonal Neighbors
Сообщение06.11.2018, 04:10 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Интересная задача, но боюсь слишком простая для 3х месяцев. Оценка $(3n-3)(3n-2)$ хорошая.

 Профиль  
                  
 
 Re: AZsPCs: Hexagonal Neighbors
Сообщение08.11.2018, 15:58 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Я поспешил с оценкой сложности. Похоже что задача лёгкая только для лидера, а для остальных ещё есть над чем потрудиться. Нашёл первые 4 оптимальных решения и пока что не вижу никаких простых закономерностей. Кстати 7 в них присутствуют.

 Профиль  
                  
 
 Re: AZsPCs: Hexagonal Neighbors
Сообщение08.11.2018, 22:28 


20/01/13
62
On larger grids, patterns are obvious.

 Профиль  
                  
 
 Re: AZsPCs: Hexagonal Neighbors
Сообщение09.11.2018, 00:39 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Does that mean that the problem is pretty much dead and we will see many people reach 25.00?

 Профиль  
                  
 
 Re: AZsPCs: Hexagonal Neighbors
Сообщение09.11.2018, 08:44 


16/08/05
1146
Вчера N11 сменилось с 900 на 901, и это был не лидер. Но сегодня N11 лидер уже подтянул.

 Профиль  
                  
 
 Re: AZsPCs: Hexagonal Neighbors
Сообщение09.11.2018, 15:09 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
dmd в сообщении #1352791 писал(а):
Вчера N11 сменилось с 900 на 901, и это был не лидер. Но сегодня N11 лидер уже подтянул.

Верно. А N27 увеличилось от 6062 до 6066 за последние дни. Значит еще есть небольшая надежда улучшить результаты.

 Профиль  
                  
 
 Re: AZsPCs: Hexagonal Neighbors
Сообщение10.11.2018, 10:06 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
За один день изменилось 4 рекорда.

 Профиль  
                  
 
 Re: AZsPCs: Hexagonal Neighbors
Сообщение11.11.2018, 23:38 
Заслуженный участник


04/03/09
906
Тут даже N8 увеличивалось недавно. Что особенно печально, потому что мой якобы полный перебор новый рекорд не находит.

 Профиль  
                  
 
 Re: AZsPCs: Hexagonal Neighbors
Сообщение14.11.2018, 14:53 
Аватара пользователя


25/08/12
171
Germany
Using pencil and paper to find the optimal solution for N=3 (which took me some days) was very helpful to develop some ideas how to approach the problem with a computer program which I started coding yesterday. I impose some restriction how the numbers are placed and the program runs better than I thought. Up to N=7 it gives "optimal" solutions within less than a minute, but for N=8 it gives only score 441 instead of 442 (also in less than 1 min). More by accident I found the 442 somehow by trying some program modifications. Nevertheless I will try the original version on larger N and will see if it gives some reasonable good solutions (or solutions at all...)

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

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



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

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


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

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