2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4
 
 Re: AZsPCs: Hexagonal Neighbors
Сообщение10.12.2018, 14:26 
Аватара пользователя


25/08/12
124
Germany
I do not see any particular reason why symmetrical solutions should give the best results. Even an infinite "perfect" grid has only translational symmetry but no reflectional or rotational symmetry.
Meanwhile I could refine my annealing approach a bit. Since swapping two cells does not change the frequencies of the 1, 2, 3 ... in the grid I added a term Max(0, desired_score - actual_score) to the energy definition and also allow sporadic changes of cell values. I think that I can reach 24.9 points (but not significantly more) in this way.

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


01/06/12
871
Adelaide, Australia
Теперь два человека нашли 25.00. Может рекорды закончились?

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


25/08/12
124
Germany
The discussion in the forum concerning the problem is not very vivid up to now... I give some consideration which might not be primarily valuable to find good scores for higher N but more from a theoretical point of view because they allow to prune the search tree considerably and can help to show optimality for smaller N.
Lets take for example this partially filled grid for N=4:
Изображение
This grid can be extended without problems to a valid grid but I claim that it is impossible to reach the best score of 87 in this way. We do this by introducing the terms grid error (GE) and grid defect (GD).

In a valid grid the grid error GE = 0. If for any grid cell with value 1<=k<=7 some of the values 1...k - 1 are missing in the neigborhood we increase GE by 1 for each of the missing values.

The grid defect GD is defined in the following way (the grid may be valid or invalid, the only assumption is that only values from 1..7 are used): If two adjacent cells have the same value, then GD is incremented by 1. If a cell has m>1 neighbors with the same *lower* value, we increment GD by m-1.

Then we have

GE = GD - (3N-3)(3N-2) + score.

In the example above we have GD >=4:
Two adjacent "1" -> +1
Two adjacent "5" -> +1
The leftmost "5" has 2 neigbors "4" -> +1
The rightmost "5" has 2 neighbors "1" -> +1

Since in a valid grid we have GE = 0 and (3N-3)(3N-2) = 90 and score =87, we must have only GD=3. Or expressed differently, with the above partial grid it is impossible to get a score > 86.

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

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



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

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


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

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