2014 dxdy logo

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

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




 
 Поиск элементов с максимальным наименьшим расстоянием
Сообщение02.03.2010, 15:15 
Аватара пользователя
Не подскажет ли кто подход к решению следующей задачки. Дано ограниченное множество векторов мощности N. Нужно выбрать из него m векторов так, чтобы максимизировать наименьшее расстояние между любыми двумя из m выбранных. Число исходных векторов для поиска N велико, поэтому полный перебор заранее обречён.

 
 
 
 Re: Поиск элементов с максимальным наименьшим расстоянием
Сообщение02.03.2010, 19:16 
Аватара пользователя
Даже для m=2 задачка непростая...

 
 
 
 Re: Поиск элементов с максимальным наименьшим расстоянием
Сообщение04.03.2010, 08:28 
2terricola
Цитата:
Нужно выбрать из него m векторов так, чтобы максимизировать наименьшее расстояние между любыми двумя из m выбранных.

Может быть стоит поиграть с методом главных компонент aka PCA? Хотя все равно переборы сложные будут...

 
 
 
 Re: Поиск элементов с максимальным наименьшим расстоянием
Сообщение04.03.2010, 10:05 
Аватара пользователя
Э-э-э... А можно вкратце объяснить суть метода главных компонент?

 
 
 
 Re: Поиск элементов с максимальным наименьшим расстоянием
Сообщение04.03.2010, 18:13 
Аватара пользователя
я думаю, тут больше подойдут жадные алгоритмы - поиск с возвратом или метод ветвей и границ

 
 
 
 Re: Поиск элементов с максимальным наименьшим расстоянием
Сообщение04.03.2010, 18:52 
2terricola
Цитата:
можно вкратце объяснить суть метода главных компонент?

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

P.S.: Информации по PCA в интернете очень много, ищите. Хотя не факт, что в вашем случае подходит именно этот метод; я просто написал первое, что пришло на ум. :)

2Severyanin
Цитата:
поиск с возвратом или метод ветвей и границ

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

 
 
 
 Re: Поиск элементов с максимальным наименьшим расстоянием
Сообщение07.03.2010, 09:53 
Аватара пользователя
2Circiter. Попробовал, не получилось). А Вам спасибо за подсказку, PCA очень помог когда выползла похожая задача.

(Оффтоп)

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

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group