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

У меня есть набор точек , и у меня есть расстояние между каждой точкой . Эти расстояния евклидовы, но точки на самом деле находятся в пространстве признаков. $C$ $D(P_i,P_j)$

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

max_{\begin{matrix} s \subset C \\ | s | = n \end{matrix}} (min_{\begin{matrix} i, j \in s \\ i \neq j \end{matrix}} D (P_{i}, P_{j}))

$\max_{\substack{s \subset C \\ |s| = n}} \left( \min_{\substack{i,j \in s \\ i \neq j} } D \left( P_i, P_j \right) \right)$

Прямо сейчас я использую восхождение на гору, чтобы решить эту проблему. Я понимаю, что имитация отжига может дать лучшее решение.

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

optimization user1389800
источник

Я заинтересован в аналогичной проблеме. Не основано на моем до сих пор в поисках результатов, это сравнимо с проблемой р-дисперсионной в задаче размещения объекта , для которого Это является хорошим специальным обзором.

XTZ

Вы знаете, как называется эта проблема?

Одуванчик

Ответы:

Вариант решения этой проблемы оптимизации:

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

Конечно, если вы можете решить проблему решения, мы можем решить вашу проблему оптимизации (путем бинарного поиска на пороге ). $t$

Теперь эта проблема решения является проблемой нахождения независимого множества в евклидовом графе, где точки имеют ребро между ними, если они находятся на расстоянии друг от друга. Один из подходов заключается в рассмотрении стандартных алгоритмов аппроксимации для независимого множества. $x,y$ $\le t$

Более того, вы можете посмотреть на алгоритмы для независимого множества в графах геометрических пересечений . Рассмотрим набор дисков, где каждый диск имеет диаметр и с центром в одной из точек в наборе . Теперь мы можем сформировать геометрический граф пересечений, где есть одна вершина для каждого диска и ребро между двумя вершинами, если их соответствующие диски пересекаются. Проблема нахождения независимого множества в этом виде графа была изучена и есть алгоритмы аппроксимации для этой проблемы, которые вы могли бы попробовать использовать. $t$ $C$

Если вам нужен точный оптимум, а не приближение, вы можете использовать любой из стандартных «больших молотков», такой как решатель SAT или решатель ILP. Существует простой способ сформулировать проблему независимого набора в качестве экземпляра SAT, и затем вы можете применить к нему решатель SAT, чтобы выяснить, существует ли подмножество из точек, которые все отстоят друг от друга. $n$ $\ge t$

DW
источник