Al Zimmermann: non-coplanar points

[Pavlovsky]

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

Знание максимальных результатов в этой задаче никак не облегчает их нахождение.

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

[Vovka17]

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

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

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

[dimkadimon]

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

-- 01.04.2016, 06:45 --

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

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

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

[Pavlovsky]

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$.

[Vovka17]

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

(Оффтоп)

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

[Pavlovsky]

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

Что за "спам" из Индонезии на странице результатов

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

[Pavlovsky]

Не пора ли заняться теорией?!
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$ ??

[Pavlovsky]

Цитата:

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 вполне может его обогнать.

[Pavlovsky]

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

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

[Gassa]

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

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

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

У меня на запрос 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. Документы выше - где-то в середине первой страницы.

[Pavlovsky]

Спасибо, вроде то что надо!

[dimkadimon]

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$ радиус шара. Можно даже попробовать несколько шаров где один внутри другого.

[Pavlovsky]

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 гипербола этим свойством не обладают.

[dimkadimon]

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

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

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

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

[Pavlovsky]

Колхозный подход дает неплохие результаты!

Цитата:

17 22.60 Vladimir Chirkov Bobruisk, Russia 5 Apr 2016 14:30