2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 4, 5, 6, 7, 8, 9, 10 ... 13  След.
 
 Re: Al Zimmermann: non-coplanar points
Сообщение06.04.2016, 06:41 
Аватара пользователя


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

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

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


21/02/10
1594
Екатеринбург
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), оценка получается сильно завышенной и соответственно отбраковка бесперспективных решений практически не происходит. В остальных случаях процедура работает очень хорошо и массово бракует решения.

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


10/11/12
121
Бобруйск
Pavlovsky в сообщении #1112708 писал(а):
Пусть у нас есть семейство параллельных плоскостей. Обладающее свойством: любая точка куба принадлежит одной и толькой одной плоскости из семейства.
Конечно это будет выполняться. Ведь плоскости параллельны.

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

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

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


21/02/10
1594
Екатеринбург
Vovka17 в сообщении #1112889 писал(а):
Ведь плоскости параллельны.

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

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


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

Vovka17 в сообщении #1112889 писал(а):
Пусть их будет столь много, сколько ещё даёт прирост к скорости.


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

Vovka17 в сообщении #1112889 писал(а):
Что ж, если вам такой метод даёт результаты


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

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


21/02/10
1594
Екатеринбург
Есть еще один способ разбиения на семейства плоскостей.

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

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


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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение12.04.2016, 12:38 


09/03/16
34
Pavlovsky в сообщении #1114358 писал(а):
Активность в конкурсе пошла на убыль. Похоже все достигли пределов возможностей своих программно-аппаратных комплексов.


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

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


01/06/12
1014
Adelaide, Australia
Pavlovsky в сообщении #1114358 писал(а):
Активность в конкурсе пошла на убыль. Похоже все достигли пределов возможностей своих программно-аппаратных комплексов.

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

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


21/02/10
1594
Екатеринбург
Как то задача бедна на идеи по улучшению алгоритма. :-(

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


01/06/12
1014
Adelaide, Australia
Pavlovsky в сообщении #1114625 писал(а):
Как то задача бедна на идеи по улучшению алгоритма. :-(

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

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


10/11/12
121
Бобруйск
dimkadimon в сообщении #1114634 писал(а):
Pavlovsky в сообщении #1114625 писал(а):
Как то задача бедна на идеи по улучшению алгоритма. :-(

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

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

dimkadimon в сообщении #1114386 писал(а):
Когда после 3х дней на кластере не находишь новых результатов то понимаешь что надо улучшать алгоритм...

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

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

(Оффтоп)

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

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


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

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


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

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


21/02/10
1594
Екатеринбург
Vovka17 в сообщении #1115210 писал(а):
Но, те результаты, которые есть, показывают, что для больших $n$ - крайне низкая. Ещё более низкая - в центре куба.


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

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


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

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

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

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



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

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


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

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