Al Zimmermann: non-coplanar points

[Vovka17]

Да, согласен. Не сработало наше жульство.
Можно упростить ваш пример до

Есть частичное решение:
(0,0,1),(0,1,0),(1,0,0)
Добавляем точку (0,0,10). Ошибок нет. Дописываем первую симметричную:
(0,0,1),(0,1,0),(1,0,0),(0,0,10),(0,10,0)
и получаем
"The four points (0, 0, 1), (0, 1, 0), (0, 0, 10) and (0, 10, 0) are coplanar."

Это легко видеть.
Очень жаль! Казалось, что что-то в этом есть...
Может хоть третью симметричную можно не проверять? Проверьте, пожалуйста, Дмитрий, у вас всё на мази - пару строк поправить. Иначе я перестаю понимать какой выигрыш нам даёт симметрия.

-- 07.06.2016, 11:27 --

dimkadimon в сообщении #1129489 писал(а):

Tim находит решение $(11,28)$ за 12 секунд. Tom находит такое решение только через 26 минут.

12 секунд! Немыслимо (хоть оно было для меня близко - всего одну точку добавить к $(11,27)$ , но очень далеко, судя по тому, к какой ошибке удавалось сводить решение)...
Они вдвоём совершенно заслуженно в призерах. И дело здесь не в везении.

[Pavlovsky]

dmd в сообщении #1129595 писал(а):

При этом смотрите, что сделала "canonical representation" с видом этого решения
Код:

(0,1,3), (0,1,4), (0,2,8), (1,5,3), (1,6,10), (1,7,10), (2,0,8), (2,2,10), (2,6,1), (3,8,3), (3,9,0), (5,7,9), (5,8,0), (6,0,9), (6,9,8), (7,0,9), (7,1,5), (7,3,2), (8,7,7), (8,10,5), (9,2,4), (9,10,7), (10,3,1), (10,5,2)

троек вообще в нём не видно

Когда мы говорим о С3 решении, то обязательно надо уточнять относительно какой диагонали. Ведь в кубе их 4. Приведенное вами решение:

Цитата:

(0,1,3),(1,7,10),(7,0,9),
(3,9,0),(9,10,7),(10,3,1),
(0,1,4),(1,6,10),(6,0,9),
(1,5,3),(5,7,9),(7,1,5),
(0,2,8),(2,0,8),(2,2,10),
(5,8,0),(8,10,5),(10,5,2),
(2,6,1),(6,9,8),(9,2,4),
(3,8,3),(7,3,2),(8,7,7)

Является С3 решением относительно диагонали (0,1,1)-(1,0,0)

-- Вт июн 07, 2016 16:31:22 --

Vovka17 в сообщении #1129690 писал(а):

(0,0,1),(0,1,0),(1,0,0)
Добавляем точку (0,0,10). Ошибок нет. Дописываем первую симметричную:
(0,0,1),(0,1,0),(1,0,0),(0,0,10),(0,10,0)

Это ограничение приходит в голову первым. Точки (a,b,c) и (ka,kb,kc) плохо совместимы в С3 решениях.

-- Вт июн 07, 2016 16:35:26 --

dmd в сообщении #1129595 писал(а):

Код:

33
(0,0,1),(0,1,0),(1,0,0),(10,9,10),(9,10,10),(10,10,9),(10,8,4),(8,4,10),(4,10,8),(9,8,1),(8,1,9),(1,9,8),(9,6,5),(6,5,9),(5,9,6),(8,3,1),(3,1,8),(1,8,3),(6,9,0),(9,0,6),(0,6,9),(6,10,3),(10,3,6),(3,6,10),(1,6,2),(6,2,1),(2,1,6),(0,7,10),(7,10,0),(10,0,7),(2,0,2),(0,2,2),(2,2,0)

Программа по тупости нашла даже решение 33 для N11, проверялись на валидность только вся первая тройка, и первая точка из всех остальных троек.

С этим решением немного сложнее. здесь в конфликт вступили тройки (6,9,0),(9,0,6),(0,6,9) и (6,10,3),(10,3,6),(3,6,10).
Если вместо тройки (6,10,3),(10,3,6),(3,6,10) взять ко-тройку (6,0,3),(0,3,6),(3,6,0), то получим предыдущий вариант.

[Archimedes]

Привет участникам конкурса!
У меня результаты более чем скромные: удалось найти решения только до размерности куба 7. Для размерности 11 получил только результат 26. Времени на задачу выделял мало, но не факт что хорошая идея пришла бы в противном случае.
Использовал несколько подходов.
Сначала тупой перебор рекурсивным алгоритмом с запоминанием компланарности всех точек куба.
Потом методом Монте-Карло с проверкой компланарности только добавляемой точки.
Потом перебором лучших решений с убиранием случайной точки с просчётом компланарности всех точек.
Потом, после анализа найденных решений, пришла идея о симметрии, которая мне виделась как наличие у большинства точек симметричных относительно центра куба, но с небольшим сдвигом (не более sqrt(3)). Алгоритм, однако, показал себя очень плохо - не доходил уровня 3-4 в решении до предыдущих методов.
Потом попробовал выбирать следующую точку так, чтобы на кубе оставалось максимальное число "свободных" точек (тех, которые неколлинеарны уже помещённым на куб). Как ни странно, алгоритм показал себя также очень слабо. Стало понятно что лучшие решения "берут" качеством, а не количеством.
Тогда родилась идея сделать целевую функцию, минимум которой приходился бы на область вблизи шара радиуса, близкого к 1/2 стороны куба. Идея также ничего выдающегося не дала.

Для проверки некомпланарности использовалось смешенное произведение векторов в кординатной форме с предварительной проверкой на неколлинеарность, так как при трёх коллинеарных точках любая четвёртая будет компланарной.
Здесь я мог потерять одну точку в решении, но алгоритм не нашёл две (28-26), поэтому я это не прорабатывал.

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

[Pavlovsky]

Archimedes в сообщении #1129717 писал(а):

Жаль что конкурс уже закончился, у меня как в анекдоте про шамана, ещё столько идей осталось.

Конкурс закончился, но вводить рекордные результаты можно. Они будут отображаться в конце Final Report. Делаем ставки, кто отнимет у Tim Foden хотя бы один рекорд?

[dmd]

Vovka17 в сообщении #1129690 писал(а):

Может хоть третью симметричную можно не проверять?

Проверил. Третью симметричную так же надо проверять.

[yae9911]

I have checked that all published record solutions show the discussed 3-fold rotational symmetry, potentially with one or two additional points on the rotation axis (cube diagonal). At least the top-ranked 6 participants all have used the C3 symmetry to find their best solutions.

In AZ's Yahoo Forum it was mentioned that all good solutions tend to have a "coconut structure".
The radial structure can be perhaps be seen best, if the solution points are rotated around the symmetry axis into a plane containing this axis.
A collection of the corresponding plots can be found at

Points rotated into a plane containing the symmetry axis

Visualizing such things needs some trial and error. 3D animation sometimes helps, see Tim Foden's Winning Result for N=97 in Al Zimmermann's Non-Coplanar Points Programming Contest

More interesting than the radial distribution seems the arrangement of the point in the outermost planar "shells". Both Tim Foden's 97_188 and Moritz Franckenstein's 97_179 solution have the surface of the cube and 3 layers below populated by the maximum possible number of 3 points per face, i.e. the layers 48, 47, 46, and 45 (distance from cube center) all contain 18 points. Of course this could have be used to construct good starting solutions.

I am extremely curious to see counterexamples where a non-symmetric solution beats the best symmetric solution.

At the moment we (Moritz Franckenstein and myself) are trying to create a list of optimum number of points in small cubes. So far we have (examples)
N Points
2 [ 5]: (0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,1,1)
3 [ 8]: (0,0,2),(0,1,1),(0,2,1),(1,0,0),(1,0,1),(1,1,2),(2,1,2),(2,2,0)
4 [10]: (0,2,2),(0,3,3),(1,0,3),(1,1,0),(1,2,0),(2,0,0),(2,2,3),(2,3,2),(3,0,1),(3,3,2)
5 [13]: (0,0,2),(0,1,1),(0,4,3),(1,1,3),(1,3,4),(1,4,1),(2,3,0),(3,0,3),(3,0,4),(3,4,2),(4,1,0),(4,2,4),(4,3,0)
6 [15]: (2,0,2),(0,2,2),(2,2,0),(1,5,2),(5,2,1),(2,1,5),(5,0,1),(0,1,5),(1,5,0),(3,0,4),(0,4,3),(4,3,0),(1,3,5),(3,5,1),(5,1,3)
7 [18]: (0,2,2),(0,5,3),(1,2,4),(1,4,6),(1,6,5),(2,0,2),(2,2,0),(2,4,1),(3,0,5),(3,6,4),(4,1,2),(4,3,6),(4,6,1),(5,1,6),(5,3,0),(6,1,4),(6,4,3),(6,5,1)
8 [20]: (2,1,2),(1,2,2),(2,2,1),(0,5,6),(5,6,0),(6,0,5),(3,0,5),(0,5,3),(5,3,0),(5,1,7),(1,7,5),(7,5,1),(2,0,7),(0,7,2),(7,2,0),(3,7,6),(7,6,3),(6,3,7),(6,6,6),(4,4,4)
9 [23]: (6,4,1),(4,1,6),(1,6,4),(4,5,8),(5,8,4),(8,4,5),(3,7,0),(7,0,3),(0,3,7),(1,1,3),(1,3,1),(3,1,1),(5,0,3),(0,3,5),(3,5,0),(6,2,8),(2,8,6),(8,6,2),(7,6,5),(6,5,7),(5,7,6),(8,8,8),(7,7,7)
10 [26]: (5,8,4),(8,4,5),(4,5,8),(2,9,7),(9,7,2),(7,2,9),(0,8,2),(8,2,0),(2,0,8),(1,3,4),(3,4,1),(4,1,3),(0,6,5),(6,5,0),(5,0,6),(9,1,2),(1,2,9),(2,9,1),(9,6,4),(6,4,9),(4,9,6),(0,5,1),(5,1,0),(1,0,5),(8,8,8),(7,7,7)
11 [28]: (0,4,9),(0,7,2),(0,7,8),(1,1,1),(1,7,9),(1,10,3),(2,0,7),(2,5,3),(3,1,10),(3,2,5),(3,9,8),(4,9,0),(4,10,5),(5,3,2),(5,4,10),(6,8,10),(7,2,0),(7,8,0),(7,9,1),(8,0,7),(8,3,9),(8,10,6),(9,0,4),(9,1,7),(9,8,3),(10,3,1),(10,5,4),(10,6,8)
12 [30]: (8,0,2),(0,2,8),(2,8,0),(0,9,4),(9,4,0),(4,0,9),(0,10,11),(10,11,0),(11,0,10),(1,5,2),(5,2,1),(2,1,5),(1,7,6),(7,6,1),(6,1,7),(1,10,8),(10,8,1),(8,1,10),(3,5,10),(5,10,3),(10,3,5),(4,11,5),(11,5,4),(5,4,11),(4,11,7),(11,7,4),(7,4,11),(7,9,9),(9,9,7),(9,7,9)
13 [32] (0,0,1),(0,2,5),(0,3,8),(1,9,4),(1,10,10),(2,2,8),(2,10,11),(2,11,10),(3,1,0),(3,4,11),(3,6,3),(4,10,2),(4,12,3),(5,7,7),(6,3,9),(7,0,4),(7,5,5),(7,12,2),(8,3,1),(8,5,0),(8,11,9),(9,1,4),(9,8,12),(9,9,6),(10,5,12),(10,8,10),(11,0,9),(11,4,3),(11,12,0),(12,1,12),(12,4,5),(12,9,1)
14 [>=35] search still in progress
15 [>=36] search still in progress
--
Hugo Pfoertner

[dimkadimon]

Hugo, how do you prove the optimality of the solutions? Have you found any non-symmetric optimal solutions for N<=13?

[Pavlovsky]

Один вопрос так и остался открытым. Почему симметрия С3 дает хорошие результаты?

[Archimedes]

Pavlovsky в сообщении #1133086 писал(а):

Один вопрос так и остался открытым. Почему симметрия С3 дает хорошие результаты?

С этим-то как раз всё понятно. Представьте себе куб, поставленный вертикально на большую диагональ.
Симметричные тройки будут лежать на горизонтальных плоскостях, в каждой такой плоскости будет находиться три точки - максимально возможное количество на плоскости.
Если посмотреть сверху, то точки, лежащие на двух плоскостях будут повёрнуты друг относительно друга на одинаковый угол, что практически исключает параллельность прямых и плоскостей, проведённых через симметричные точки (кроме нескольких вырожденных случаев). Другими словами, точки не будут накладывать друг на друга дополнительные ограничения по отношению к тем, которые возникают в среднем при выборе случайной точки.
Следовательно, вероятность найти решение с большим числом симметричных точек выше.

[dimkadimon]

Я все равно не понимаю почему симметрия C3 дает результаты быстрее чем поиск без симметрии, который можно очень хорошо оптимизировать? Пока не вижу как можно оптимизировать нахождение решений C3?

[Pavlovsky]

Мы принудительно добавляем в решение сразу три точки. Тем самым сокращаем глубину перебора в три раза! Это просто гигантское сокращение объема перебора!

dimkadimon в сообщении #1133154 писал(а):

Пока не вижу как можно оптимизировать нахождение решений C3?

К тому же можно оптимизировать проверку. Используя идею macroxue.
https://groups.yahoo.com/neo/groups/AlZ ... sages/6991

[dimkadimon]

В случае перебора все ясно. Но в случае отжига не вижу особой выгоды.

[Pavlovsky]

dmd в сообщении #1129501 писал(а):

Проверил - это не так. Всё равно проверку на некомпланарность нужно делать для каждой добавляемой точки.

Пусть у нас есть С3 решение и тройка точек P1=(x,y,z); P2=(z,x,y); P3=(y,z,x);

Утверждение 1. Если точку P1 можно добавить к решению. Тогда к решению можно добавить и точку P2 и P3. Не все разом, а одну из них.

Утверждение 2. Если к решению можно добавить одновременно точки P1 и P2. Тогда к решению можно добавить всю тройку точек P1,P2,P3.

Получается проверять надо только две точки из трех.

[Pavlovsky]

Немного о классах эквивалентности macroxue.
https://groups.yahoo.com/neo/groups/AlZ ... sages/6991

Пусть у нас есть точка P=(x,y,z). Пусть значения координат упорядочены по возрастанию.

Тогда функция $F(P)=\frac{y-x}{z-x}$ является определяющей для классов эквивалентности macroxue. То есть если $F(P_1)=F(P_2) $, то точки $P_1$ и $P_2$ принадлежат одному классу эквивалентности macroxue.

[Pavlovsky]

Пусть у нас есть некоторое С3 решение.

Утверждение 1. В С3 решении может быть не более 2-х точек вида (a,a,a). Другими словами на диагонали (0,0,0)-(N,N,N) в решении может быть не более двух точек.

Утверждение 2. В С3 решении может быть не более 3-х точек вида (a,b,b),(b,a,b) ,(b,b,a) a<>b.

Следствие 1. Если не считать точки (0,0,0) и (N,N,N). В С3 решении, в вершинах и на ребрах куба может быть не более трех точек.

Как это можно использовать? При поиске С3 решения не рассматривать точки вида (a,a,a),(a,b,b),(b,a,b) ,(b,b,a). Это сильно сократит пространство перебора, а потеряем мы на этом максимум 5 точек. Эти точки можно добавить в готовое С3 решение, дополнительным перебором.