Поиск элементов с максимальным наименьшим расстоянием

[terricola]

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

[worm2]

Даже для m=2 задачка непростая...

[Circiter]

2terricola

Цитата:

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

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

[terricola]

Э-э-э... А можно вкратце объяснить суть метода главных компонент?

[Severyanin]

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

[Circiter]

2terricola

Цитата:

можно вкратце объяснить суть метода главных компонент?

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

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

2Severyanin

Цитата:

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

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

[Severyanin]

2Circiter. Попробовал, не получилось). А Вам спасибо за подсказку, PCA очень помог когда выползла похожая задача.

(Оффтоп)

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