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
125
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
894
Adelaide, Australia
Теперь два человека нашли 25.00. Может рекорды закончились?

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


25/08/12
125
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.

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


01/06/12
894
Adelaide, Australia
Very nice work Herbert! Can we use these ideas to estimate the optimal scores for each grid?

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


25/08/12
125
Germany
dimkadimon в сообщении #1371711 писал(а):
Very nice work Herbert! Can we use these ideas to estimate the optimal scores for each grid?

Not really. For a valid grid we have
score = (3N-3)(3N-2) - GD

I see no apparent method to estimate GD. The only thing we know is GD >=0. So we get score <= (3N-3)(3N-2) which is nothing new. For N=4 it seems for example that we cannot get below GD=3.

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


07/06/16
15
Омск
Привет, коллеги математики!
Уже скоро объявят конечные результаты конкурса, поэтому могу уже рассказать как решал задачу. Правда мой результат не впечатляет - всего 24.7 из 25.

Решал так. Сначала написал программку, которая методом Монте-Карло генерировала решения, отбирая максимальные.
Так удалось набрать первоначальную статистику.
Затем удалось увидеть что 5,6,7 могут располагаться или треугольником (в трёх соседних гексах, соприкасающихся с двумя другими), или в виде ленты гексов.
Удобно было выразить разные способы как замощения площади с последующей редукцией граничных гексов до получения решения.
К сожалению, полностью задачу автоматизировать не хватило времени или желания.
Испробовал замощения следующих видов:
тройки 2,3,4 и 5,6,7
тройки 5,6,7 с лентами 2,3,4 между ними
два концентрических замощения.

Из минусов: так и не понял как можно получить превышение над теоретическим максимумом, которое точно получили два лидера.
Надеюсь узнаю это завтра.

Извините что не делился своими мыслями раньше - совершенно забыл про этот форум.

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


01/11/17
27
Archimedes в сообщении #1373444 писал(а):
Из минусов: так и не понял как можно получить превышение над теоретическим максимумом, которое точно получили два лидера.

Even leaders are far below the theoretical maximum. Check your calculations.

Yes, the subgrids of values 5,6,7 always degenerate to disjoint chains, which itself can degenerate to simple cell, 3-cell loop, or larger loop.

Both ends of a chain are always defective cells.

The maximal sum of the values within a particular chain/loop depends only from its size and is non-linear but simple to calculate.

Joining chains/loops or rearranging them to sizes closer to optimal is a powerful method. I investigated and exploited few shortcuts. Hopefully leaders will share much more interesting stuff.

Additionally, representing all chains in canonical form drastically reduces the number of the working grids.

More on that after the official end.

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


07/06/16
15
Омск
dobrichev в сообщении #1373476 писал(а):
Even leaders are far below the theoretical maximum. Check your calculations.

Спасибо за ваш развёрнутый ответ!
Оказывается я действительно принимал за теоретический максимум один из рекордных результатов на какую-то дату. Прошу прощения.

dobrichev в сообщении #1373476 писал(а):
More on that after the official end.

Да, подождём, уже меньше суток осталось.

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


07/06/16
15
Омск
Ну, что же, раз все молчат, давайте начну я.

Давайте рассмотрим первое решение размерности 8.
Изображение

Я его раскрасил так, чтобы лучше были видны закономерности.
Красным цветом выделены единицы, так как они должны покрывать всё поле собой и соседними к ним шестью гексами.
Жёлтым выделил 2, 3 и 4, которые отнесём к низшей группе. Между ними есть отличия в "поведении", но не хочу перегружать схему излишним количеством цветов.
Синим выделил высшую группу цифр 5-7, так как они самые требовательные к своему окружению и легко "перетекают" из одной в другую.

Что мы здесь видим?
1. Мы видим длинные изгибающиеся последовательности синих гексов, которые на большом своём протяжении параллельны сторонам поля. Я использовал регулярные замощения низкой периодичности, которые были параллельны в лучшем случае только двум сторонам из шести. Здесь же сложное замощение ориентировано так, что последовательности жёлтых гексов лежат строго на гранях поля.
Как все наверное уже знают, в вершинах поля могут стоять только гексы 1-4, а на сторонах только 1-5. Поэтому если в середине поля среднее значение гекса 3.5, то на сторонах не более 3, а в вершинах не более 2.5. И было очень умно найти такую последовательность, которая в значительной степени состоит из жёлтых гексов в линиях, параллельных сторонам поля, так как в этом случае вынужденное редуцирование гексов на гранях поля при наложении на него замощения сводится к минимуму.
2. В идеале, на гранях не должно быть синих гексов, но для R8 нет идеального замощения, в котором бы жёлтые последовательности совпадали со всеми шестью гранями поля. Поэтому мы видим как синие гексы на гранях, так и минимальные циклы из трёх синих гексов 5, 6 и 7. Они здесь идеально вписались в те области, в которых длинные циклы синих гексов имели слишком много пересечений с гранями поля.
3. Здесь трудно это заметить, но на больших полях видно лучше что грани обычно состоят из облестей с тремя видами гексов: (1,2,3), (1,2,4) и (1,3,4). Для первого случая гекс 4 и не требуется, а для второго и третьего случаев гекс 2 обычно лежит на второй линии от грани поля. Это делает возможным максимально близкое прилегание линий синих гексов к граням поля.

Что можно ещё добавить? Если вам будет интересно, могу написать какие именно регулярные замощения использовал я, и какие из них дали лучший результат. Хотя, напомню, что своими простыми регулярными замощениями я получил только результат 24.76 .

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


01/11/17
27
Well, the contest finished.

Both leaders that reached 25.00, Tom Sirgedas and Tomas Rokicki, happened to use different approaches. Congratulations!

The contestants who willed to share their methods did it in the contest discussion group.

I briefly described my methods here, where at the end of the page also added references to the pages where other contestants do the same.

@Archimedes: Thank you too for sharing your approach, and yes, it would be interesting to know few more details.

This is one of the published best boards for 27, with erased 567 chains, slightly prettified by hand by me in attempt to underline the symmetry of the sub-structures.
код: [ скачать ] [ спрятать ]
Используется синтаксис Python
                          2 1 2 3 1 4 2 4 1 2 3 1 4 2 4 1 2 3 1 4 2 1 4 3 1 3 4
                         4 3 . 4 . . 3 1 3 . 4 . . 3 1 3 . . . . 3 1 . 2 4 . 2 1
                        1 2 . 1 . 2 . 4 2 . 1 . 2 . 4 2 4 1 4 2 . . . 3 1 . . 4 3
                       4 . . 4 . 3 1 . . . 4 . 3 1 . . . . . 3 1 4 2 4 . 2 3 1 . 2
                      2 3 1 3 2 . . 2 3 1 3 2 . 4 2 3 1 3 2 . . . 3 1 . . 4 . . 3 1
                     1 4 . . . 1 4 . . . . . 1 . . . . . . 1 4 2 . . 2 3 1 . 2 4 . 2
                    2 1 . 2 4 . 2 3 1 4 2 4 . 2 3 1 4 2 4 . . 3 1 4 . . 4 . 3 1 . . 4
                   3 4 . 3 1 3 . 4 . . 3 1 3 . 4 . . 3 1 3 2 . . 2 3 1 . 2 . 4 2 3 1 3
                  1 . 2 . 4 2 . 1 . 2 . 4 2 . 1 . 2 . 4 . . 1 4 . . 4 . 3 1 . . . . 2 1
                 3 . . 1 . . . 4 . 3 1 . . . 4 . 3 1 . 2 . 4 2 3 1 . 2 . . 2 3 1 4 . . 4
                1 2 4 3 2 3 1 3 2 . . 2 3 1 3 2 . . . 3 1 3 . . . . 3 1 4 . . 4 2 3 1 3 2
               . 4 1 . . 4 . . . 1 4 . . . . 4 1 4 2 4 . 2 . 1 4 2 4 . 2 3 1 . . . . . . 1
              2 3 . 2 . 1 . 2 4 . 2 3 1 4 2 . . . 3 1 . . 4 . . 3 1 . . 4 . 2 3 1 4 2 4 . 2
             2 1 . . 3 4 . 3 1 3 . 4 . . 3 1 3 2 . . 2 3 1 3 2 . 4 2 3 1 . . 4 . . 3 1 3 . 4
            3 . 2 4 1 . 2 . 4 2 . 1 . 2 . . . . 1 4 . . 4 . . 1 . . . 4 2 3 1 . 2 . 4 2 . 1 3
           1 . 4 3 . . 3 1 . . . 4 . 3 1 4 2 4 . 2 3 1 . 2 . 4 2 3 1 . . . . . 3 1 . . . 4 2 1
          3 2 . 1 . 2 4 . 2 3 1 3 2 . . . 3 1 3 . . . . 3 1 3 . . 4 2 3 1 4 2 4 . 2 3 1 3 . . 3
         1 . . 3 . 4 1 . . 4 . . 4 1 4 2 . 4 2 4 1 4 2 4 . 2 . 1 . . . . . 3 1 . . 4 . 2 . 1 4 2
        2 4 1 4 2 . 3 2 3 1 . 2 . . . 3 1 . . . . . 3 1 . . 4 . 2 3 1 4 2 . 4 2 3 1 . . 4 . . . 1
       4 3 . . . 1 . . . 4 . 3 1 3 2 . 4 2 3 1 3 2 . 4 2 3 1 3 . . . . 3 1 . . . 4 2 3 1 3 2 3 . 2
      2 1 . 2 3 . 2 4 1 . 2 . 4 . . 1 . . . 4 . . 1 . . . 4 2 4 1 4 2 . 4 2 3 1 . . . 4 . . 1 . 4 3
     3 . . 4 1 4 . 3 . . 3 1 . 2 . 4 2 3 1 . 2 . 4 2 3 1 . . . . . 3 1 . . . 4 2 3 1 . 2 . 4 2 . 1 4
    1 4 2 3 . 2 . 1 . 2 4 . . 3 1 3 . . 4 . 3 1 3 . . . 2 3 1 3 2 . 4 2 3 1 . . . 4 . 3 1 3 . . 3 2 1
   3 . . 1 . . 3 . 4 . 1 . 2 4 . 2 . 1 . 2 . . 2 . 1 4 . . 4 . . 1 . . . 4 2 3 1 . 2 . . 2 . 1 4 . . 3
  1 2 . 3 2 4 1 . 2 3 . . 3 1 . . 4 . . 3 1 4 . . 4 2 3 1 . 2 . 4 2 3 1 . . . . . 3 1 4 . . 4 2 . 1 4 2
 . 4 1 4 . . 3 . 4 1 4 2 4 . 2 3 1 3 2 4 . 2 3 1 3 . . 4 . 3 1 3 . . . 2 3 1 4 2 4 . 2 3 1 3 . . 3 . . 1
2 3 . 2 . 1 . 2 . 3 . . 1 . . 4 . . . 1 . . 4 . 2 . 1 . 2 . . 2 . 1 4 . . . . 3 1 . . 4 . 2 . 1 4 2 . 3 2
 1 . . 3 . 4 . 1 . 2 . 3 2 3 1 . 2 4 . 2 3 1 . . 4 . . 3 1 4 . . 4 2 3 1 4 2 . 4 2 3 1 . . 4 . . . 1 4 .
  2 4 1 . 2 3 . . 4 1 4 . . . . 3 1 3 . 4 . 2 3 1 3 2 4 . 2 3 1 3 . . . . 3 1 . . . 4 2 3 1 3 2 3 . 2 1
   . 3 . 4 1 4 2 3 . 2 . 1 4 2 4 . 2 . 1 . . 4 . . 4 1 . . 4 . 2 . 1 4 2 . 4 2 3 1 . . . . . 4 1 . 4 3
    1 2 . 3 . . 1 . . 3 . . 3 1 . . 4 . 2 3 1 . 2 . . 2 3 1 . . 4 . . 3 1 . . . 4 2 3 1 4 2 . 3 2 . 1
     4 1 . 2 . 3 2 4 1 4 2 . 4 2 3 1 3 . 4 . . 3 1 3 . 4 . 2 3 1 3 2 . 4 2 3 1 . . . . . 3 1 . 4 . 3
      3 . 4 1 4 . . 3 . . 1 . . . 4 2 . 1 . 2 4 . 2 . 1 . . 4 . . . 1 . . . 4 2 3 1 4 2 . 4 2 . 1 2
       2 . 3 2 . 1 . 2 . 3 2 3 1 . . . 4 . 3 1 . . 4 . 2 3 1 . 2 4 . 2 3 1 . . . . . 3 1 . . . 3 4
        1 . . . 3 . 4 1 4 . . . 2 3 1 3 2 . 4 2 3 1 3 . . 4 . 3 1 3 . 4 . 2 3 1 4 2 . 4 2 3 1 4 2
         2 4 1 4 2 . 3 2 . 1 4 . . 4 . . 1 . . . 4 2 4 1 . 2 . 4 2 . 1 . . 4 . . 3 1 . . . . . 1
          3 . . . 1 . . . 3 2 3 1 . 2 . 4 2 3 1 . . . . . 3 1 . . . 4 2 3 1 . 2 . 4 2 3 1 4 2 3
           1 2 3 . 2 4 1 4 . . 4 . 3 1 3 . . . 2 3 1 3 2 4 . 2 3 1 3 . . . . 3 1 . . . . . 3 1
            4 1 4 . 3 . 2 . 1 . 2 . 4 2 . 1 4 . . . . . 1 . . 4 . 2 . 1 4 2 4 . 2 3 1 4 2 . 4
             3 2 . 1 . . 3 . . 3 1 . . . 4 2 3 1 4 2 4 . 2 3 1 . . 4 . . 3 1 . . 4 . . 3 1 2
              4 . 3 2 4 1 4 2 4 . 2 3 1 3 . . . . 3 1 3 . 4 . 2 3 1 3 2 . 4 2 3 1 . 2 . 4 2
               1 . . . 3 . . 1 . . 4 . 2 . 1 4 2 . 4 2 . 1 . . 4 . . . 1 . . . . . 3 1 . 1
                2 4 1 . 2 . 3 2 3 1 . . 4 . . 3 1 . . . 4 2 3 1 . 2 4 . 2 3 1 4 2 4 . 2 3
                 . 3 4 . 1 4 . . 4 2 3 1 3 2 . 4 2 3 1 3 . . 4 . 3 1 3 . . . . 3 1 . . 4
                  1 2 . 3 2 . 1 . . . . . . 1 . . . 4 2 . 1 . 2 . 4 2 4 1 4 2 . . 2 3 1
                   3 1 . . . 3 2 3 1 4 2 4 . 2 3 1 . . . 4 . 3 1 . . . . . 3 1 4 . . 4
                    4 2 4 1 4 . . . . 3 1 3 . 4 . 2 3 1 3 2 . 4 2 3 1 3 2 . . 2 3 1 2
                     . 3 . 2 . 1 4 2 . 4 2 . 1 . . 4 . . . 1 . . . 4 . . 1 4 . . . 1
                      1 . . 3 . . 3 1 . . . 4 2 3 1 . 2 4 . 2 3 1 . 2 . 4 2 3 1 4 2
                       2 4 1 4 2 . . 2 3 1 3 . . 4 . 3 1 3 . 4 . . 3 1 3 . . . . 3
                        . 3 . . 1 4 . . . 2 . 1 . 2 . 4 2 . 1 . 2 4 . 2 . 1 4 2 1
                         1 2 . 3 2 3 1 4 . . 4 . 3 1 . . . 4 . 3 1 . . 4 . . 3 2
                          3 4 1 . 4 1 2 3 1 3 2 1 4 2 3 1 3 2 1 4 2 3 1 3 2 1 4

By eye I can't see chain U-turns over cells different than '1'. Do you see?

IMO the structures of the board remain unexplored. There should be much yet undiscovered symmetries, constrains, transformation moves, improvement shortcuts, etc.

For example one can define a family of acceptable moves and demonstrate the minimal required moves to transform one of the two published maximal 27s boards to the other. (Reduction of the board to all-ones and rebuilding to other is not acceptable).

It was fun.

 Профиль  
                  
 
 Re: AZsPCs: Hexagonal Neighbors
Сообщение06.02.2019, 15:25 


07/06/16
15
Омск
Итак, первый период, назовём его стихийным :), когда я написал программу и методом Монте-Карло генерировал поля, прошёл у меня за пару недель.
Для других задач он длился у меня намного дольше. Поэтому могу смело сказать что участие в конкурсах нас точно развивает.

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

Итак, какие замощения я испробовал.

Сначала я сделал Замощение 1
Изображение
У этого замощения период 14, поэтому каждому полю соответствовало 14 вариантов.
Для этого варианта я написал программу, которая генерировала поле размера N со сдвигом P, подставляла близкие к идеальным для данного замощения гексы на границах.
Затем я вручную подгонял ближайшие к вершинам поля гексы, добиваясь отсутствия противоречий в решении.
Потом запускался другой алгоритм этой же программы, который пробовал:
1. увеличивать значения гексов,
2. менять местами два гекса если это возможно,
3. переставлять местами три гекса, если это возможно.
Этот алгоритм работал надёжно, хотя и не очень быстро. Но, так как идей было мало, спешить особо было некуда.

Как оказалось, Замощение 1 было одним из самых продуктивных. Им я получил большинство своих максимальных значений полей. Связано это видимо с тем, что период повторения 14 - достаточно большой, и поэтому случайные совпадения с границами поля были более вероятны чем у других вариантов замощения.

Затем я проверил некоторые из других подобных замощений:
Изображение
Они не дали никакого прогресса по сравнению с первоначальным Замощением 1.

Тогда я стал искать и нашёл самое простое замощение, Замощение 2:
Изображение
Его период равен 7, и оно, как мне казалось сначала, может дать преимущества по сравнению с Замощением 1.
Но реально получилось только увеличить на 1 рекорд для поля R15.

Нужны были новые идеи, и я получил Замощение 3:
Изображение
Была надежда на то, что такое замощение даст больший результат, так как при деградации тройки 5,6,7 уменьшается всегда самый большой элемент - 7, а при уменьшении длинной последовательности 5,6,7 возможно под деградацию попадёт 6 или 5.
К сожалению, предположение оказалось неверным. При деградации гексов на пересечении последовательностей 5,6,7 с гранями поля из-за отбрасывания гексов 2 и 3 деградировали гексы 4, что вызывало деградацию более одного гекса в последовательностях 5,6,7.
Я понимал что вариантов Замощения 3 как минимум 3, но все их проверять не стал, так как и по одному было понятно что это не даст улучшения.

Тогда родилось концентрическое Замощение 4, сразу в двух вариантах:
Изображение
и
Изображение

Как я сейчас понимаю, я уже стоял на пороге осознания существования сложных замощений из комбинации линий и концентрических элементов. Шаг этот сделать не удалось, но сами концентрические замощения дали для некоторых полей увеличение результата на 2-3 единицы.

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

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

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



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

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


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

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