Al Zimmermann: non-coplanar points

[Vovka17]

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

[ctac]

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

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

К сожалению у меня нет достаточно времени для того чтобы принять серьезное участие в конкурсе. Но мне интересно обдумывать всякие идеи и следить за идеями других людей здесь на форуме. Кстати вот вы пишете про решение с ошибками и про решение с меньшими ошибками, и у меня возник вопрос: а как оценить решение по числу ошибок в нем и возможно ли это вообще?

[dimkadimon]

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

а как оценить решение по числу ошибок в нем и возможно ли это вообще?

Очень важный вопрос! Я считаю количество множеств из четырех точек, которые все на одной плоскости. Это значит что если 5 точек на одной плоскости то они дадут сразу 5 ошибок.

[Vovka17]

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

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

Ладно, согласен, настало время это признать.

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

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

Ценность идеи можно проверить лишь в реальном бою. А то, что времени нет, так у кого ж оно есть. Всё на уровне хобби. В отличие от большинства конкурсов для программистов, эти соревнования очень лояльны по срокам решений - можно вводить всё в первый день, можно каждый день по чуть-чуть, можно прийти в последний день с топовыми результатами... и никто вас не осудит. Уж если не решитесь в этом конкурсе, так в следущем, надеюсь увидеть вас в рейтинговой таблице.

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

Я считаю количество множеств из четырех точек, которые все на одной плоскости. Это значит что если 5 точек на одной плоскости то они дадут сразу 5 ошибок.

Аналогично.

[ctac]

Цитата:

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

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

Ценность идеи можно проверить лишь в реальном бою. А то, что времени нет, так у кого ж оно есть. Всё на уровне хобби. В отличие от большинства конкурсов для программистов, эти соревнования очень лояльны по срокам решений - можно вводить всё в первый день, можно каждый день по чуть-чуть, можно прийти в последний день с топовыми результатами... и никто вас не осудит. Уж если не решитесь в этом конкурсе, так в следущем, надеюсь увидеть вас в рейтинговой таблице.

Ну, если получится

Цитата:

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

Я считаю количество множеств из четырех точек, которые все на одной плоскости. Это значит что если 5 точек на одной плоскости то они дадут сразу 5 ошибок.

Аналогично.

[/quote]

Т.е. если 6 точек на одной плоскости то они дадут сразу 15 ошибок, а если 7 точек на одной плоскости то они дадут сразу 35 ошибок?

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

[Vovka17]

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

Т.е. если 6 точек на одной плоскости то они дадут сразу 15 ошибок, а если 7 точек на одной плоскости то они дадут сразу 35 ошибок?

Да, но это не меняет сути. Вы можете считать это хоть лишь одной ошибкой - на здоровье! И цель остается прежней - достичь нуля ошибок.

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

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

Всё правильно. Если к хорошему решению просто добавить точку, то мы получим плохое решение, с большой ошибкой, но точек в нём уже на 1 больше. Учитывая связанность точек, возможно потребуется переставить почти все старые точки, чтобы "втолкнуть" ещё одну.
(При добавлении точки, сложность нахождения решения возрастает по дикой экспоненте, и тем сильнее, чем ближе мы к максимуму для данного $n$)

[Pavlovsky]

Кто то копал в сторону формулировки двойственных задач? Например, в ЗД пространстве точка и плоскость двойственные понятия.

[Pavlovsky]

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

Что если взять решение и прокрутить его на несколько градусов вокруг всех трех осей?

Может попробовать проективные преобразования? Хотя, на первый взгляд они ничего не дают.

[Pavlovsky]

Что нового?

[ctac]

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

Что нового?

Увы, фраза: "no news is good news" в нашем случае не годится

А вообще-то есть одно наблюдение: Если берешь решение и вставляешь его в больший куб (например решение для куба 13х13х13 в куб 17х17х17) то все точки оказываются собранными в углу куба и остается много пустого места, но добавить еще точек не удается или почти не удается. Т.е. видимо для хорошего решения точки должны быть равномерно "размазаны по кубу".

[Pavlovsky]

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

Тогда любое решение задачи будет представлено из точек начального решения и множества независимых вершин графа G.

[Pavlovsky]

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

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

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

В качестве метрики выбрал такую; $R(p_1,p_2)=max(|x_1-x_2|,|y_1-y_2|,|z_1-z_2|)$

Получилось, что для больших N $R(p_1,p_2)=1$ редко но бывает.

[ctac]

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

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

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

В качестве метрики выбрал такую; $R(p_1,p_2)=max(|x_1-x_2|,|y_1-y_2|,|z_1-z_2|)$

Получилось, что для больших N $R(p_1,p_2)=1$ редко но бывает.

Является ли это хорошим критерием равномерности распределения точек в кубе?
Например случай, когда для всех пар точек кроме одной пары $R(p_1,p_2)=5$ и лишь для одной пары равно 1?

[Pavlovsky]

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

для всех пар точек кроме одной пары $R(p_1,p_2)=5$

Так не бывает. Наверно надо так $R(p_1,p_2)\ge 5$

Я проверял чисто практический вопрос. Насколько можно применять эвристику запрета на близкие точки. То есть запретить точки расстояние между которыми меньше некторого порога $R(p_1,p_2)< R_0$

[Vovka17]

Специально статистику по расстояниям между точками не собирал, но разглядывал несколько своих решений в 3D. Расстояния между точками различны и бывают всякие - от самых малых ($1, 1.41...$) до некоторого максимума, который можно влепить между точками в данном кубе.
Также долго считал, что в центре куба не будет точек, и можно отрезать и выкинуть из поиска шар точек в центре, но сам не исключал их. И вот, в одном из максимальных решений для большого куба нашлась точка очень близко к центру - резко выбивается из общей статистики. Так что вероятность мала, но она есть. Наверное то же самое касается и угловых точек.

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

видимо для хорошего решения точки должны быть равномерно "размазаны по кубу".

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

В общем, довольно безрадостная картина вырисовывается...