2014 dxdy logo

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

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




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


01/06/12
1013
Adelaide, Australia
Vovka17 в сообщении #1115183 писал(а):
Тем, кто заскучал, могу предложить одну работу
(на русском, кстати). Судя по представленным автором итогам, это может очень сильно помочь.

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

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

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


10/11/12
121
Бобруйск
dimkadimon в сообщении #1115551 писал(а):
Автор показывает результат на очень простом примере, поэтому трудно судить эффективность алгоритма.

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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение20.04.2016, 00:11 


09/03/16
34
Vovka17 в сообщении #1115886 писал(а):
Другими словами, отжиг плохо работает на функциях вида "расчески", со множеством локальных минимумов, разделенных локальными максимумами


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

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


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

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


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

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

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


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #1116954 писал(а):
Идея основана на симметричном расположении точек.


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

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


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


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

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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение22.04.2016, 13:22 


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

Я попробовал подсчитать число плоскостей проходящих через каждую точку в кубе 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|
---------------------------------------------------------

(не получается выровнять строчки :-( )
Максимальные значения в углах и в центре.
Т.е. когда мы ставим там точку, мы "портим" максимальное число плоскостей.

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


21/02/10
1594
Екатеринбург
Вы показали таблицу 7х7. Это какая то специально выбранная плоскость из куба 7х7х7?

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение22.04.2016, 15:22 
Заслуженный участник
Аватара пользователя


19/12/10
1546
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}$

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


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

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

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


10/11/12
121
Бобруйск
Вот мои значения количества значимых плоскостей (содержащих 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 ---- ---- ----
---- ---- ---- ---- ---- ---- ----
---- ---- ---- ---- ---- ---- ----
---- ---- ---- ---- ---- ---- ----

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


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

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение22.04.2016, 18:14 


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

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

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


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

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

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

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



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

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


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

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