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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 03.01.2010, 05:14
Новичок

Отправить личное сообщение для saqwer Посмотреть профиль Найти все сообщения от saqwer
 
Регистрация: 22.12.2009
Адрес: Киев
Сообщений: 14

Разделяемые множества точек
В трехмерном прострастве имеются два множества точек. Задача: определить являются ли эти множества точек разделяемыми?

П.с.: два множества точек называются разделяемыми, если существует плоскость, которая делит пространство на два подпространства так, что каждая из точек находится в одном подспространстве с другими точками своего множества.

П.п.с: два множества точек называются разделяемыми, если выпуклые оболочки построенные на них - не пересекаются.
  #2  
Старый 03.01.2010, 05:56
гость

 
Сообщений: n/a

Простейшее хакерское решение
Берешь и обучаешь простейший линейный классификатор - персептрон.

Есть теорема Новикова, говорящая, что если классы линейно разделимы, то процесс обучения персептрона сойдется.

Если он слишком долго не будет сходится, то пиши что не разделимы.
  #3  
Старый 03.01.2010, 07:06
Новичок

Отправить личное сообщение для saqwer Посмотреть профиль Найти все сообщения от saqwer
 
Регистрация: 22.12.2009
Адрес: Киев
Сообщений: 14

Сообщение от гость Посмотреть сообщение
Берешь и обучаешь простейший линейный классификатор - персептрон.

Есть теорема Новикова, говорящая, что если классы линейно разделимы, то процесс обучения персептрона сойдется.

Если он слишком долго не будет сходится, то пиши что не разделимы.
А если попытаться не обучать персептрон, а придумать более строгий математический алгоритм?(если можно - удобный для программирования)
  #4  
Старый 03.01.2010, 07:38
гость

 
Сообщений: n/a

Ну можно сделать так: разделяющую плоскость всегда можно повернуть так, чтобы она касалась каких-то трех точек, да? Вот и перебираем всевозможные тройки точек из заданных, строим плоскость и смотрим - разделяющая она или нет. O(n^4).
  #5  
Старый 03.01.2010, 15:40
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Сделать по определению.
Построить выпуклые оболочки для каждого множества, а потом проверить пересекаются ли они.
  #6  
Старый 03.01.2010, 15:59
гость

 
Сообщений: n/a

Сообщение от prografix Посмотреть сообщение
Сделать по определению.
Построить выпуклые оболочки для каждого множества, а потом проверить пересекаются ли они.
так это же сложно сделать программно
  #7  
Старый 03.01.2010, 16:09
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

В принципе да. Но если уже есть готовая программа построения выпуклой оболочки, то уже проще.
  #8  
Старый 03.01.2010, 21:18
гость

 
Сообщений: n/a

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

но кажется, есть более простой алгоритм.

и еще: "разделяющую плоскость всегда можно повернуть так, чтобы она касалась каких-то трех точек, да? "
-- Нет.

кажется, что есть более простой алгоритм
  #9  
Старый 04.01.2010, 11:37
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Можно не строить выпуклую оболочку, а свести эту задачу к задаче линейного программирования. Вот только ограничения получатся однородными, поэтому надо будет зафиксировать какую-нибудь переменную и решить эту задачу дважды ( с положительным и с отрицательным значением ).
  #10  
Старый 04.01.2010, 12:04
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Разбиение множества. ugo Математические алгоритмы 35 27.09.2010 22:17
Еще одна задача на разбиение множества jungle4ever Математические алгоритмы 7 23.06.2009 17:30
Нахождение множества элементарных циклов графа kilobait Графы 9 17.03.2008 10:02
Покрытие множества кругами Tolran Вычислительная геометрия 3 29.11.2007 01:00
алгоритм нахождения минимального множества сечений контуров обратной связи ikro Графы 0 03.05.2007 11:00