2014 dxdy logo

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

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





Начать новую тему Ответить на тему На страницу Пред.  1 ... 9, 10, 11, 12, 13
 
 Re: Al Zimmermann: non-coplanar points
Сообщение07.06.2016, 12:09 
Аватара пользователя


10/11/12
119
Бобруйск
Да, согласен. Не сработало наше жульство.
Можно упростить ваш пример до
Код:
Есть частичное решение:
(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)$ , но очень далеко, судя по тому, к какой ошибке удавалось сводить решение)...
Они вдвоём совершенно заслуженно в призерах. И дело здесь не в везении.

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение07.06.2016, 14:27 
Аватара пользователя


21/02/10
1594
Екатеринбург
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), то получим предыдущий вариант.

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение07.06.2016, 14:57 


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

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

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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение07.06.2016, 16:56 
Аватара пользователя


21/02/10
1594
Екатеринбург
Archimedes в сообщении #1129717 писал(а):
Жаль что конкурс уже закончился, у меня как в анекдоте про шамана, ещё столько идей осталось.


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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение07.06.2016, 17:56 


16/08/05
661
Vovka17 в сообщении #1129690 писал(а):
Может хоть третью симметричную можно не проверять?

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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение09.06.2016, 01:21 
Аватара пользователя


14/12/14
7
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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение09.06.2016, 16:14 
Аватара пользователя


01/06/12
737
Adelaide, Australia
Hugo, how do you prove the optimality of the solutions? Have you found any non-symmetric optimal solutions for N<=13?

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение21.06.2016, 07:35 
Аватара пользователя


21/02/10
1594
Екатеринбург
Один вопрос так и остался открытым. Почему симметрия С3 дает хорошие результаты?

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение21.06.2016, 11:13 


07/06/16
9
Омск
Pavlovsky в сообщении #1133086 писал(а):
Один вопрос так и остался открытым. Почему симметрия С3 дает хорошие результаты?

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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение21.06.2016, 15:43 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение21.06.2016, 15:57 
Аватара пользователя


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

dimkadimon в сообщении #1133154 писал(а):
Пока не вижу как можно оптимизировать нахождение решений C3?

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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение21.06.2016, 16:04 
Аватара пользователя


01/06/12
737
Adelaide, Australia
В случае перебора все ясно. Но в случае отжига не вижу особой выгоды.

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение22.06.2016, 11:00 
Аватара пользователя


21/02/10
1594
Екатеринбург
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.

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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение29.06.2016, 07:40 
Аватара пользователя


21/02/10
1594
Екатеринбург
Немного о классах эквивалентности 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.

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение01.07.2016, 11:43 
Аватара пользователя


21/02/10
1594
Екатеринбург
Пусть у нас есть некоторое С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 решение, дополнительным перебором.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 195 ]  На страницу Пред.  1 ... 9, 10, 11, 12, 13

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



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

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


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

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