2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 13  След.
 
 Re: Al Zimmermann: non-coplanar points
Сообщение23.03.2016, 00:07 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Herbert Kociemba в сообщении #1108520 писал(а):
I suspected it, but now it is sure. It is Tomas.

Wow big leap forward! If he wins this competition, he will become the first to win 3 in a row! I thought that he was unusually quiet...

He still has some records to go, so there is still hope.

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


01/06/12
1016
Adelaide, Australia
Цитата:
1 24.99 Tomas Rokicki Palo Alto, California, United States 23 Mar 2016 16:08


It's game over.

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


10/11/12
121
Бобруйск
Если Tomas Rokicki выиграет в очередной раз, то это ещё не показатель, что "game over". Я до последнего останусь при своей мысли, что найти оптимальные значения для больших $n$ невозможно в настоящее время. А значит шансы остаются у всех до последнего дня конкурса.
Мне, например, до сих пор не удается даже $n=7$ решить полностью. Интересно до каких $n$ удалось достигнуть текущих максимумов остальным присутствующим (Без указания самих максимумов, разумеется. Кажется это нарушит правила).

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


01/06/12
1016
Adelaide, Australia
Какое то время у меня были максимумы для первых 17 $n$. Несколько даже уникальные рекорды. Но потом пришёл Tomas... Теперь даже не знаю, наверное потерял половину максимумов. N=7 уже две недели ищу рекорд, близко но никак.

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


10/11/12
121
Бобруйск
dimkadimon в сообщении #1108738 писал(а):
N=7 уже две недели ищу рекорд, близко но никак.

О, как! А я думал, что только у меня такие трудности.
dimkadimon в сообщении #1108738 писал(а):
Какое то время у меня были максимумы для первых 17 $n$. Несколько даже уникальные рекорды. Но потом пришёл Tomas... Теперь даже не знаю, наверное потерял половину максимумов.

Я стараюсь отслеживать текущие рекорды. С тех пор, как Jeremy Sawicki потерял свои 25.00, все рекорды для $n>7$ были так или иначе улучшены.

Может кто-нибудь подскажет как визуализировать массив точек в Вольфраме. Уж очень хочется посмотреть на "сферическое распределение" со всех сторон, да нет никаких инструментов для этого.

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


01/06/12
1016
Adelaide, Australia
Vovka17 в сообщении #1108754 писал(а):
О, как! А я думал, что только у меня такие трудности.

Я даже не уверен что рекорд существует, но вроде так близко...

Vovka17 в сообщении #1108754 писал(а):
Может кто-нибудь подскажет как визуализировать массив точек в Вольфраме.


Про Вольфрам не знаю, а в Матлабе несложно используя scatter3.

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


10/11/12
121
Бобруйск
dimkadimon в сообщении #1108784 писал(а):
Я даже не уверен что рекорд существует, но вроде так близко...

А вот здесь не понятно. Я имел ввиду повторить текущий рекорд для $n=7$. Конечно он существует - кто-то же решил уже!

В вольфраме есть функция:
Код:
ListPointPlot3D[{{x1,y1,z1},{x2,y2,z2},…}]
generates a 3D scatter plot of points with coordinates .

Казалось бы это то, что надо. Но не работает :-( . Наверное в онлайн-версии не будет. Жаль. Хотелось просто поглядеть что там, да как, не устанавливая для этого сурьезного софта.

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


01/06/12
1016
Adelaide, Australia
Vovka17 в сообщении #1108786 писал(а):
А вот здесь не понятно. Я имел ввиду повторить текущий рекорд для $n=7$. Конечно он существует - кто-то же решил уже!

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

Посмотрите что Tomas делает с ближайшими соперниками, он их почти до 24 опустил. У него какой то супер метод, аж страшно!

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


10/11/12
121
Бобруйск
Есть семерка! :D
Текущий рекорд $n=7$ не изменялся давно. Думаю, что у вас, Дмитрий, максимум и улучшить его уже не удастся.
dimkadimon в сообщении #1108794 писал(а):
Посмотрите что Tomas делает с ближайшими соперниками, он их почти до 24 опустил. У него какой то супер метод, аж страшно!

Он их опережает на 1-2 точки в заданиях, но начиная с достаточно младших $n$, а это самые дорогие баллы.

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


01/06/12
1016
Adelaide, Australia
Vovka17 в сообщении #1108804 писал(а):
Есть семерка! :D
Текущий рекорд $n=7$ не изменялся давно. Думаю, что у вас, Дмитрий, максимум и улучшить его уже не удастся.

Поздравляю! А вот насчет рекорда у меня еще есть надежда, ведь мы имеем дело с огромным количеством вариантов, даже для $n=7$.

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


21/02/10
1594
Екатеринбург
Herbert Kociemba в сообщении #1106395 писал(а):
As I had expected I made the method work today. Given three arbitrary points it generates a list of all integer grid points which are in the plane defined by the tree points. And this of course without testing all the points of the cube grid individually.


Наконец то и я решил эту задачу для общего случая. Получился простой, красивый и эффективный алгоритм.

1) Представим плоскость в виде: $ax+by+cz+d=0$
2) В цикле переберем координату z из интервала [0,N-1]
3) Получается линейное диафантово уравнение с двумя неизвестными (x,y). Решаем его расширенным алгоритмом Евклида.

Все!

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


10/11/12
121
Бобруйск
Herbert Kociemba в сообщении #1106395 писал(а):
As I had expected I made the method work today. Given three arbitrary points it generates a list of all integer grid points which are in the plane defined by the tree points. And this of course without testing all the points of the cube grid individually.

Раньше я прикидывал сколько плоскостей, содержащих 4 и более точек, содержит куб. Получились следующие цифры (могу и наврать, конечно):
Код:
n planes   for1point
2     12       6...6
3    147     25...33
5  16077   349...674
7 346743 3217...5326
...

В третьей колонке - число таких плоскостей, проходящих через одну точку куба.
Получается, что да, в таком подходе нам не надо проверять все сочетания по 4 точки на компланарность, и это круто! Но надо хранить огромный массив с количеством точек на каждой плоскости. И, при добавлении новой точки, отмечать её во всех пересекаемых плоскостях, которых не мало.
Выигрываем ли мы при этом что-то? Хмм...

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


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #1108980 писал(а):
Наконец то и я решил эту задачу для общего случая. Получился простой, красивый и эффективный алгоритм.

1) Представим плоскость в виде: $ax+by+cz+d=0$
2) В цикле переберем координату z из интервала [0,N-1]
3) Получается линейное диафантово уравнение с двумя неизвестными (x,y). Решаем его расширенным алгоритмом Евклида.

Все!

Гениально! Но будет ли это быстрее?

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


16/08/05
1146
dimkadimon в сообщении #1109002 писал(а):
Но будет ли это быстрее?

Не похоже, чтоб было сильно быстрее. Ведь основная вычислительная трудность в переборе всех вариантов трёх точек для получения $a,b,c,d$. Перебор четвёртой точки для получения $x,y,z$ в максимальном случае N25 составляет порядка $10^6$ обращений к массиву в памяти. Тогда решением вышеуказанного диофантова уравнения мы заменяем порядка $10^4$ переборных операций.

Вот если бы весь перебор у нас состоял из перебора точек $x,y,z$, помноженный на перебор допустимого диапазона значений $d$, а значения $a,b,c$ находились решением соответствующего диофантова уравнения - тогда если решений всего три, то точка $x,y,z$ подходяща и вычислительный выигрыш возможно сильнее.

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


21/02/10
1594
Екатеринбург
Получается забавная теоремка
$ax+by+cz+d=0$
Если a,b,c,d целые числа. a,b<>0
Тогда d+ct делится нацело на gcd(a,b) при любом целом t.

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

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



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

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


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

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