Wybór podzbioru w celu zmaksymalizowania minimalnej odległości między punktami

Mam zestaw punktów i mam odległość między każdym punktem . Odległości te są euklidesowe, ale punkty znajdują się w przestrzeni cech. $C$ $D(P_i,P_j)$

Z punktów chcę wybrać podzbiór punktów. Zadzwoń do tego podzbioru . Chcę wybrać ten podzbiór tak aby zmaksymalizować odległość minimalna między wszystkimi punktami w nowy zestaw . $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)$

W tej chwili korzystam ze wspinaczki, aby rozwiązać ten problem. Rozumiem, że symulowane wyżarzanie może dać lepsze rozwiązanie.

Czy istnieje znane rozwiązanie tego rodzaju problemu? A może ten problem można przeformułować w inny problem, który można łatwo rozwiązać?

optimization użytkownik1389800
źródło

Interesuje mnie podobny problem. Na podstawie moich dotąd poszukujących wyników, jest porównywalny do problemu p-rozpraszającym w błąd lokalizacji obiektu, dla którego to jest ładny przegląd papier.

XTZ

Czy wiesz, jak nazywa się ten problem?

Dmuchawiec

Odpowiedzi:

Wersja problemu decyzyjnego tego problemu optymalizacji:

Biorąc pod uwagę próg , chcesz wiedzieć, czy można znaleźć podzbiór punktów, tak aby każda para punktów w tym podzestawie znajdowała się w odległości co najmniej jednostek. $t$ $n$ $t$

Oczywiście, jeśli potrafisz rozwiązać problem decyzyjny, możemy rozwiązać twój problem optymalizacji (przez wyszukiwanie binarne na progu ). $t$

Teraz ten problem decyzyjny jest problem ze znalezieniem niezależnego zestawu w euklidesowej wykresie, gdzie punkty mają przewagę między nimi, jeśli są one w odległości siebie. Jednym z podejść byłoby przyjrzenie się standardowym algorytmom aproksymacyjnym dla niezależnego zestawu. $x,y$ $\le t$

Co więcej, możesz spojrzeć na algorytmy niezależnego zestawu w geometrycznych wykresach przecięcia . Rozważmy zestaw dysków, gdzie każdy dysk ma średnicę i skupia się na jednym z punktów w zestawie . Teraz możemy utworzyć geometryczny wykres przecięcia, w którym dla każdego dysku jest jeden wierzchołek i krawędź między dwoma wierzchołkami, jeśli ich odpowiednie dyski się przecinają. Problem znalezienia niezależnego zestawu na tego rodzaju wykresie został zbadany i istnieją algorytmy aproksymacyjne dla tego problemu, które można spróbować zastosować. $t$ $C$

Jeśli chcesz dokładnego optimum zamiast przybliżenia, możesz użyć dowolnego ze standardowych „dużych młotków”, takiego jak solver SAT lub solver ILP. Jest to prosty sposób na sformułowanie problemu Ustaw jako niezależnej instancji SAT, a następnie można zastosować SAT solver niej znaleźć, czy istnieje podzbiór punktów, które są wszystkie jednostki z dala od siebie. $n$ $\ge t$

DW
źródło