2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 7, 8, 9, 10, 11, 12, 13  След.
 
 Re: Al Zimmermann: non-coplanar points
Сообщение01.05.2016, 20:16 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение01.05.2016, 21:50 


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


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

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


01/06/12
1006
Adelaide, Australia
ctac в сообщении #1119889 писал(а):
а как оценить решение по числу ошибок в нем и возможно ли это вообще?


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

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


10/11/12
121
Бобруйск
Pavlovsky в сообщении #1112454 писал(а):
Колхозный подход дает неплохие результаты!

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

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

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

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

Аналогично.

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение02.05.2016, 08:49 


09/03/16
34
Цитата:
ctac в сообщении #1119889 писал(а):
К сожалению у меня нет достаточно времени для того чтобы принять серьезное участие в конкурсе. Но мне интересно обдумывать всякие идеи и следить за идеями других людей здесь на форуме.

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

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


Цитата:
dimkadimon в сообщении #1119976 писал(а):
Я считаю количество множеств из четырех точек, которые все на одной плоскости. Это значит что если 5 точек на одной плоскости то они дадут сразу 5 ошибок.

Аналогично.
[/quote]

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

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

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


10/11/12
121
Бобруйск
ctac в сообщении #1120010 писал(а):
Т.е. если 6 точек на одной плоскости то они дадут сразу 15 ошибок, а если 7 точек на одной плоскости то они дадут сразу 35 ошибок?

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

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

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

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


21/02/10
1594
Екатеринбург
Кто то копал в сторону формулировки двойственных задач? Например, в ЗД пространстве точка и плоскость двойственные понятия.

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


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #1118913 писал(а):
Что если взять решение и прокрутить его на несколько градусов вокруг всех трех осей?


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

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


21/02/10
1594
Екатеринбург
Что нового?

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение10.05.2016, 23:04 


09/03/16
34
Pavlovsky в сообщении #1122601 писал(а):
Что нового?


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

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

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


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

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

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


21/02/10
1594
Екатеринбург
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$ редко но бывает.

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение11.05.2016, 21:46 


09/03/16
34
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?

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


21/02/10
1594
Екатеринбург
ctac в сообщении #1122919 писал(а):
для всех пар точек кроме одной пары $R(p_1,p_2)=5$


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

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

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


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

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

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

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

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



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

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


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

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