Al Zimmermann: non-coplanar points

[Vovka17]

Но и не хорошие. Для $n=11$ никак не могу найти даже решение с 27 точками. В остальных задачах отставание ещё больше. Так что хвастаться пока нечем. Можно "насилуя" железо приблизиться ещё на 1-2 точки к максимумам, но это мой предел на текущий момент.

В задаче no-three-in-line problem есть множество решений, где пары точек расположены на квадрате симметрично. И вокруг этого строится много теории. Расположить же три точки симметрично в кубе не получается. И, поэтому, несмотря на общность задач в двумерном и трехмерном пространстве, я пока не вижу единых подходов к решению.

[Pavlovsky]

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

Но текущие максимумы для средних и, уж тем более, для старших $n$ очень далеки от оценки $3n$. Не понятно, как может помочь знание максимумов.

Пусть у нас есть семейство параллельных плоскостей. Обладающее свойством: любая точка куба принадлежит одной и толькой одной плоскости из семейства.

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

Тогда верхнюю оценку можно вычислить по формуле:$ \sum_{i=0}^{K}\min(Q_i+S_i,3)$ где K количество плоскостей в семействе; $Q_i$ количество точек из решения принадлежащих плоскости i; $S_i$ количество доступных точек в плоскости i.

Несколько замечаний.
1) Естественно можно использовать много семейств плоскостей. Я использую 9 семейств. Оценка вычисляется для каждого семейства в отдельности.
2) Когда в текущем решении мало точек (<N), оценка получается сильно завышенной и соответственно отбраковка бесперспективных решений практически не происходит. В остальных случаях процедура работает очень хорошо и массово бракует решения.

[Vovka17]

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

Пусть у нас есть семейство параллельных плоскостей. Обладающее свойством: любая точка куба принадлежит одной и толькой одной плоскости из семейства.

Конечно это будет выполняться. Ведь плоскости параллельны.

Что ж, если вам такой метод даёт результаты, то почему вы используете только 9 разновидностей плоскостей. Не надо их задавать вручную, дайте программе возможность самой формировать такие семейства плоскостей и использовать их все в поиске решения.
Пусть их будет столь много, сколько ещё даёт прирост к скорости. А то, что таких семейств можно построить очень и очень много даже для небольших кубов было косвенно показано мною раньше.

Ваш подход, чем то напоминает решение задачи n-queens problem с использованием битовых полей и сдвигов (Не могу найти хорошей ссылки ). Это один из быстрейших алгоритмов для той задачи. Только там на выходе готовые расстановки, а у вас куб-полуфабрикат, который надо окончательно проверить на некомпланарность...

[Pavlovsky]

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

Ведь плоскости параллельны.

С этим надо быть осторожным. Геометрия 3D дискретного пространства отличается Евклидового пространства. Например две плоскости пересекаются по некоторой прямой. Но может так получится, что эта прямая не содержит точек с целочисленными координатами. То есть в дискретном пространстве эти плоскости параллельны! В дискретном пространстве плоскости могут телепортироваться сквозь друг друга!

Цитата:

любая точка куба принадлежит одной и толькой одной плоскости из семейства

Это свойство очень важно для процедуры, поэтому я его и выделил отдельно.

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

Пусть их будет столь много, сколько ещё даёт прирост к скорости.

Эксперименты показали 9 семейств это и есть оптимум. Дальнейшее добавление семейств приводит к росту затрат времени на их расчет, но не дает экономии при отсечении плохих вариантов. Варианты которые могло бы отсечь новое семейство, очень часто отсекаются предыдущими семействами.

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

Что ж, если вам такой метод даёт результаты

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

[Pavlovsky]

Есть еще один способ разбиения на семейства плоскостей.

Пусть у нас есть частично заполненное решение. Возьмем из него две точки. Построим все плоскости проходящие через прямую, проходящую через эти точки. Тогда верхняя оценка будет равна: количеству точек в решении плюс количество плоскостей которые содержат хотя бы одну доступную точку (может быть добавлена к решению без нарушения условий задачи).

[Pavlovsky]

Активность в конкурсе пошла на убыль. Похоже все достигли пределов возможностей своих программно-аппаратных комплексов.

[ctac]

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

Активность в конкурсе пошла на убыль. Похоже все достигли пределов возможностей своих программно-аппаратных комплексов.

Или же закончились все хорошие идеи

[dimkadimon]

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

Активность в конкурсе пошла на убыль. Похоже все достигли пределов возможностей своих программно-аппаратных комплексов.

Когда после 3х дней на кластере не находишь новых результатов то понимаешь что надо улучшать алгоритм...

[Pavlovsky]

Как то задача бедна на идеи по улучшению алгоритма.

[dimkadimon]

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

Как то задача бедна на идеи по улучшению алгоритма.

Либо наши мозги бедны :)

[Vovka17]

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

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

Как то задача бедна на идеи по улучшению алгоритма.

Либо наши мозги бедны :)

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

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

Когда после 3х дней на кластере не находишь новых результатов то понимаешь что надо улучшать алгоритм...

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

Тем, кто заскучал, могу предложить одну работу (на русском, кстати). Судя по представленным автором итогам, это может очень сильно помочь. Но моего уровня подготовки катастрофически мало, чтобы понять о чем же там написано, а детально разбираться - долго и некогда... Хотелось бы услышать мнение математиков - есть ли там что-то стоящее?

(Оффтоп)

Вчера на работе иду на вызов. Возле бухгалтерии стоит женщина, отчитывает на весь коридор свою молодую подчиненную: "... не правильно... переделать... исправь... И, запомни, нет такого ответа - Я не знаю"
Этой своей последней фразой она меня зацепила, но удержался и прошел мимо...
Сделал работу, иду обратно. Стоит эта "начальница" одна. Не удержался, и проходя мимо, тихо так ей: "А не подскажите мне, случайно, что такое корпускулярно-волновой дуализм"
- Чё-ээ.. - с лицом полным непонимания.
- Ну у вас же нет ответа "я не знаю", - напоминаю ей.
- Да я даже слов то таких не зна... - в голове у неё на полуслове закоротило.
- Вообще-то это в школе проходят, - закончил я и пошел в свой отдел.

[Pavlovsky]

Какая вероятность, что точка (0,0,1), и ей подобные, будет в рекордном решении?

[Vovka17]

У меня нет рекордных решений для $n>7$. Но, те результаты, которые есть, показывают, что для больших $n$ - крайне низкая. Ещё более низкая - в центре куба.
Однако я не исключаю из рассмотрения ни те, ни другие. Сам не знаю почему, наверное потому, что прирост скорости в 1,5-2 раза - это не то, что мне поможет.

[Pavlovsky]

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

Но, те результаты, которые есть, показывают, что для больших $n$ - крайне низкая. Ещё более низкая - в центре куба.

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

[Vovka17]

Вы считаете, что можно получить математически строгие значения без самих решений? Мне кажется, что для нашей задачи это архисложная затея (впору для квантового компьютера).

В общедоступной ссылке есть все возможные решения для $n=5$. (Наверное, при желании, можно найти все решения и для $n=7$).
По этим данным можно построить статистику точек в рекордных решениях для каждой точки куба 5x5x5 (возможно и для 7х7х7).
Это слишком мало, конечно, но хоть что-то, за неимением "волшебной формулы".