Al Zimmermann: non-coplanar points

[dimkadimon]

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

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

Автор показывает результат на очень простом примере, поэтому трудно судить эффективность алгоритма.

Мне понравилось как вы "наказали" бухгалтершу - красиво!

[Vovka17]

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

Автор показывает результат на очень простом примере, поэтому трудно судить эффективность алгоритма.

Да, на простом. Но он рассматривал пример из других книг и показал, как его наработки могут всё улучшить. Основная проблема указанная многими, кто сталкивался с отжигом - это правильный выбор параметров, а автор, кажется, как-то разобрался с этим. Думал это будет полезно и нам.
Впрочем, возможно всё не так просто. И сам по себе алгоритм отжига сильно не поможет. У нас получается сильно связанная группа точек и перестановкой одиночных точек, трудно разбить "плохое" расположение нескольких точек. И, чем больше точек в кубе, тем больше таких "неправильных" групп возможно...
Другими словами, отжиг плохо работает на функциях вида "расчески", со множеством локальных минимумов, разделенных локальными максимумами (а у нас именно такая функция!). Найти среди этого "леса" глобальный минимум трудно, так как нет спуска у функции, скатывающегося в этот минимум - это просто "такое" расположение всех точек, и любое отклонение от этого расположения даёт большую ошибку...

[ctac]

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

Другими словами, отжиг плохо работает на функциях вида "расчески", со множеством локальных минимумов, разделенных локальными максимумами

А как тут, по Вашему мнению смог бы работать GA?

[Vovka17]

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

[dimkadimon]

Согласен про GA. SA дает хорошие результаты если использовать правильный набор параметров, а это для меня сложно. Поэтому я обычно использую простой hill climbing и концентрируюсь на оптимизации подсчета функции. В этой теме уже достаточно написано чтобы получить четвертое место в данной задаче, а вот дальше надо что то новое.

У меня есть первая хорошая идея, которая возможно принесет улучшения, но ее надо как-следует проверить. Идея основана на симметричном расположении точек. Вместо расстановки всех точек $P$ возможно хватит расставить $P/2$ точек (если повезет то даже $P/3$ точек), а остальные точки можно найти от первых. Самое сложное найти хороший вид симметрии который позволит нам это осуществить с наименьшими проблемами.

[Pavlovsky]

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

Идея основана на симметричном расположении точек.

Я немного думал в этом направлении. В задаче No-three-in-line_problem симметрия поощряется. В текущей задаче тоже есть симметрия, но хитрая.
Пусть у нас есть некое симметричное преобразование. Есть точка и ее расчетная симметричная точка. Так в решение надо брать точку, которая находится рядом с расчетной симметричной точкой, но не совпадать с ней!

[Pavlovsky]

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

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

Опробовал эвристику на запрет точек в углах и центре куба. Вроде работает, но результатов не дает.

И постоянно мучают сомнения, почему брать в решение угловые и центральные точки куба - это плохо. О математически строгих утверждениях я уже не мечтаю, хотя бы общие соображения.

[ctac]

Цитата:

И постоянно мучают сомнения, почему брать в решение угловые и центральные точки куба - это плохо.

Я попробовал подсчитать число плоскостей проходящих через каждую точку в кубе 7х7х7.
Вот что получилось после вычета из всех значений минимального:
|31281| 7744|12794| 10498|12794| 7744|31281|
--------------------------------------------------------
| 7744| 648| 3622| 0 | 3622| 648 | 7744|
--------------------------------------------------------
|12794| 3622|23758|16860|23758| 3622|12794|
--------------------------------------------------------
|10498| 0 |16860|27806|16860| 0 |10498|
--------------------------------------------------------
|12794| 3622|23758|16860|23758| 3622|12794|
--------------------------------------------------------
| 7744 | 648| 3622 | 0 | 3622 | 648 | 7744|
--------------------------------------------------------
|31281| 7744|12794| 10498|12794| 7744|31281|
---------------------------------------------------------
(не получается выровнять строчки )
Максимальные значения в углах и в центре.
Т.е. когда мы ставим там точку, мы "портим" максимальное число плоскостей.

[Pavlovsky]

Вы показали таблицу 7х7. Это какая то специально выбранная плоскость из куба 7х7х7?

[whitefox]

ctac в сообщении #1117456 писал(а):

не получается выровнять строчки

Попробуйте так:

|31281| 7744|12794|10498|12794| 7744|31281|
-------------------------------------------
| 7744|  648| 3622|    0| 3622|  648| 7744|
-------------------------------------------
|12794| 3622|23758|16860|23758| 3622|12794|
-------------------------------------------
|10498|    0|16860|27806|16860|    0|10498|
-------------------------------------------
|12794| 3622|23758|16860|23758| 3622|12794|
-------------------------------------------
| 7744|  648| 3622|    0| 3622|  648| 7744|
-------------------------------------------
|31281| 7744|12794|10498|12794| 7744|31281|
-------------------------------------------

Или так:
$\begin{tabular}{|r|r|r|r|r|r|r|} \hline 31281 & 7744 & 12794 & 10498 & 12794 & 7744 & 31281 \\ \hline 7744 & 648 & 3622 & 0 & 3622 & 648 & 7744 \\ \hline 12794 & 3622 & 23758 & 16860 & 23758 & 3622 & 12794 \\ \hline 10498 & 0 & 16860 & 27806 & 16860 & 0 & 10498 \\ \hline 12794 & 3622 & 23758 & 16860 & 23758 & 3622 &12794 \\ \hline 7744 & 648 & 3622 & 0 & 3622 & 648 & 7744 \\ \hline 31281 & 7744 & 12794 & 10498 & 12794 & 7744 & 31281 \\ \hline \end{tabular}$

[Vovka17]

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

Ой, извиняюсь. Вы же привели значения за вычетом константы.

[Vovka17]

Вот мои значения количества значимых плоскостей (содержащих 4 и более точек), проходящих через точки куба:

n=7
z=0
4863 4973 5065 4804 ---- ---- ----
---- 5136 5064 4960 ---- ---- ----
---- ---- 4865 4800 ---- ---- ----
---- ---- ---- 4673 ---- ---- ----
---- ---- ---- ---- ---- ---- ----
---- ---- ---- ---- ---- ---- ----
---- ---- ---- ---- ---- ---- ----
z=1
---- ---- ---- ---- ---- ---- ----
---- 5326 5056 5017 ---- ---- ----
---- ---- 4565 4716 ---- ---- ----
---- ---- ---- 4709 ---- ---- ----
---- ---- ---- ---- ---- ---- ----
---- ---- ---- ---- ---- ---- ----
---- ---- ---- ---- ---- ---- ----
z=1
---- ---- ---- ---- ---- ---- ----
---- ---- ---- ---- ---- ---- ----
---- ---- 3742 4153 ---- ---- ----
---- ---- ---- 4325 ---- ---- ----
---- ---- ---- ---- ---- ---- ----
---- ---- ---- ---- ---- ---- ----
---- ---- ---- ---- ---- ---- ----
z=2
---- ---- ---- ---- ---- ---- ----
---- ---- ---- ---- ---- ---- ----
---- ---- ---- ---- ---- ---- ----
---- ---- ---- 3217 ---- ---- ----
---- ---- ---- ---- ---- ---- ----
---- ---- ---- ---- ---- ---- ----
---- ---- ---- ---- ---- ---- ----

[Pavlovsky]

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

[ctac]

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

Вы показали таблицу 7х7. Это какая то специально выбранная плоскость из куба 7х7х7?

Да. Это когда z=0.

Вот 3 плоскости для куба 3х3х3:

74 0 74
0 34 0
74 0 74

0 34 0
34 238 34
0 34 0

74 0 74
0 34 0
74 0 74

Через центр проходит больше всего плоскостей.

[Pavlovsky]

ctac в сообщении #1117540 писал(а):

Через центр проходит больше всего плоскостей.

Vovka17 приводит противоположные цифры.