2014 dxdy logo

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

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




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


21/02/10
1594
Екатеринбург
Vovka17 в сообщении #1110839 писал(а):
Знание максимальных результатов в этой задаче никак не облегчает их нахождение.


В моем алгоритме, знание лучшего результата очень ускоряет поиск.

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


10/11/12
121
Бобруйск
Pavlovsky в сообщении #1110874 писал(а):
В моем алгоритме, знание лучшего результата очень ускоряет поиск.

Хм, интересно. У меня вот никаких идей о том, как эта информация может помочь в поиске... Ну, может только для младших $n$ ... и то, ерунда... Ладно, я по колхозному пока ваяю, без высших материй

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


01/06/12
1014
Adelaide, Australia
Ура Jarek снял один рекорд с Tomas (может даже не один). Только вот жалко что Ал $A(n)^2$ показывает и не пишет даты нахождения...

-- 01.04.2016, 06:45 --

Pavlovsky в сообщении #1110874 писал(а):
В моем алгоритме, знание лучшего результата очень ускоряет поиск.

А вот это крайне интересно!

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


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #1110962 писал(а):
А вот это крайне интересно!

Немного поторопился хвастаться. Ожидал прорыва от нового алгоритма. И вроде все тестовые эксперименты говорили что все работает. А вот рабочий запуск пока не дал результатов. Предстоит долгая работа, чтобы разобраться что к чему.

Раз сказал А, надо говорить Б. Суть идеи такова.

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

Пусть нам удалось придумать алгоритм вычисления верхней оценки. Но это число надо с чем то сравнить. С неким целевым $K_0$. То есть мы ищем решение в котором не менее $K_0$ точек. Чем больше $K_0$ тем раньше и чаще мы будем отбраковывать бесперспективные частные решения. Но если мы возьмем слишком большое значение, то рискуем вообще ничего не найти. Самое логичное в качестве $K_0$ взять наилучшее известное решение.

Для текущей задачи для вычисления верхней оценки текущего решения можно использовать свойство:
dimkadimon в сообщении #1104977 писал(а):
Допустим $A(n)$ это максимальное количество точек для $n \times n \times n$. В каждой плоскости $1 \times n \times n$ может быть не более трех точек, а таких плоскостей у нас $n$. Значит $A(n) \leq 3n$.

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


10/11/12
121
Бобруйск
Но текущие максимумы для средних и, уж тем более, для старших $n$ очень далеки от оценки $3n$. Не понятно, как может помочь знание максимумов. Возможно только для младших $n$ будет какая то польза.
Кстати верхнюю оценку можно оценить гораздо точнее, чем простейшее $A(n)\leqslant3n$. Может как-нибудь займусь этим исследованием на досуге. Пока же не вижу в этом смысла.

(Оффтоп)

Что за "спам" из Индонезии на странице результатов http://azspcs.net/Contest/Tetrahedra/Standings?

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


21/02/10
1594
Екатеринбург
Vovka17 в сообщении #1111160 писал(а):
Что за "спам" из Индонезии на странице результатов

Детишки в детском саду, добрались до компьютера воспитательницы.

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


21/02/10
1594
Екатеринбург
Не пора ли заняться теорией?!
Some advances in the no-three-in-line problem
R.R Hall, T.H Jackson, A Sudbery, K Wild

http://www.sciencedirect.com/science/ar ... 6575900436

В статье показано как получить решение no-three-in-line problem с оценкой $(\frac{3}{2}-\varepsilon )*N
$. Для этого используется гипербола: $xy \equiv k\mod p$.

Может нечто подобное можно получить и для текущей задачи: $xyz \equiv k\mod p$ ??

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


21/02/10
1594
Екатеринбург
Цитата:
1 24.97 Tim Foden Stevenage, United Kingdom 4 Apr 2016 11:03
2 24.90 Tomas Rokicki Palo Alto, California, United States 3 Apr 2016 02:52
3 24.43 Jarek Wroblewski Wroclaw, Poland 2 Apr 2016 21:41
4 23.71 Jeremy Sawicki Menlo Park, California, United States 28 Mar 2016 09:12
5 23.58 Dmitry Kamenetsky Adelaide, Australia 4 Apr 2016 05:58


Битва за звание царя горы идет жестокая. Бывших на самом верху жестоко опускают все ниже и ниже. Jeremy Sawicki еще недавно был безусловным царем горы. А нынче Dmitry Kamenetsky вполне может его обогнать.

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


21/02/10
1594
Екатеринбург
Не могу найти статью:
Guy, R. K.; Kelly, P. A. (1968). "The no-three-in-line problem". Canad. Math. Bull. 11: 527–531.

У кого богатый опыт поиска научной литературы - помгите пожалуйста! :cry:

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


22/12/08
17
Санкт-Петербург
Pavlovsky в сообщении #1112048 писал(а):
Не могу найти статью:
Guy, R. K.; Kelly, P. A. (1968). "The no-three-in-line problem". Canad. Math. Bull. 11: 527–531.

У кого богатый опыт поиска научной литературы - помгите пожалуйста! :cry:
У меня на запрос https://www.google.com/?#q=site:oeis.org+%22The+no-three-in-line+problem%22 находятся две PDF-ки на сайте OEIS. Вторая даже с такими же номерами страниц.

Update: видимо, хороший запрос такой: https://www.google.com/?#q=no-three-in-line+problem+pdf. Документы выше - где-то в середине первой страницы.

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


21/02/10
1594
Екатеринбург
Спасибо, вроде то что надо!

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


01/06/12
1014
Adelaide, Australia
Pavlovsky в сообщении #1112016 писал(а):
Может нечто подобное можно получить и для текущей задачи: $xyz \equiv k\mod p$ ??

У меня такие решения не получились. Так как решения шарообразные вокруг центра, может лучше искать такой вид: $a(x-x_c)^2+b(y-y_c)^2+c(z-z_c)^2=K^2$, где $(x_c,y_c,z_c)$ центр куба, а $K \leq N/2$ радиус шара. Можно даже попробовать несколько шаров где один внутри другого.

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


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #1112193 писал(а):
У меня такие решения не получились. Так как решения шарообразные вокруг центра, может лучше искать такой вид: $a(x-x_c)^2+b(y-y_c)^2+c(z-z_c)^2=K^2$


Возникла сумасшедшая мысль. В задаче "The no-three-in-line problem" в качестве основы можно использовать гиперболу или окружность. Это фигуры отличаются свойством: любая прямая пересекает их не более чем в двух точках.

А существует ли в 3D пространстве фигура которую любая плоскость пересекает не более чем в трех точках?? Очевидно 3D сфера и 3D гипербола этим свойством не обладают.

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


01/06/12
1014
Adelaide, Australia
Pavlovsky в сообщении #1112254 писал(а):
Возникла сумасшедшая мысль. В задаче "The no-three-in-line problem" в качестве основы можно использовать гиперболу или окружность. Это фигуры отличаются свойством: любая прямая пересекает их не более чем в двух точках.

Кажется таких нет. Для любой 3D фигуры можно найти плоскость которая ее пересекает в бесконечном количестве точек...

http://mathworld.wolfram.com/Plane-Plan ... ction.html

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


21/02/10
1594
Екатеринбург
Колхозный подход дает неплохие результаты!
Цитата:
17 22.60 Vladimir Chirkov Bobruisk, Russia 5 Apr 2016 14:30

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

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



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

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


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

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