Choisir un sous-ensemble pour maximiser la distance minimale entre les points

J'ai un ensemble de points , et j'ai la distance entre chaque point $C$ $D(P_i,P_j)$ . Ces distances sont euclidiennes mais les points se trouvent en fait dans un espace caractéristique.

Parmi les points je veux choisir un sous-ensemble de points. Appelez ce sous-ensemble . Je veux choisir ce sous-ensemble afin de maximiser la distance minimale entre tous les points du nouvel ensemble . $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)$

En ce moment, j'utilise l'escalade pour résoudre ce problème. Je comprends que le recuit simulé peut donner une meilleure solution.

Existe-t-il une solution connue à ce type de problème? Ou ce problème peut-il être reformulé en un autre problème facile à résoudre?

optimization user1389800
la source

Je suis intéressé par un problème similaire. Sur la base de mes résultats de recherche jusqu'à présent, il est comparable au problème de dispersion de p dans le problème de localisation des installations pour lequel il s'agit d'un bon article de synthèse.

XTZ

Savez-vous quel est le nom de ce problème?

Dandelion

Réponses:

La version de problème de décision de ce problème d'optimisation est:

Étant donné un seuil , vous voulez savoir s'il est possible de trouver un sous-ensemble de points de sorte que chaque paire de points dans le sous-ensemble soit au moins unités séparées. $t$ $n$ $t$

Bien sûr, si vous pouvez résoudre le problème de décision, nous pouvons résoudre votre problème d'optimisation (par recherche binaire sur le seuil ). $t$

Or, ce problème de décision est le problème de trouver un ensemble indépendant dans un graphe euclidien, où les points ont un bord entre eux s'ils sont à distance écart. Une approche consisterait à examiner des algorithmes d'approximation standard pour un ensemble indépendant. $x,y$ $\le t$

Encore mieux, vous pouvez regarder des algorithmes pour un ensemble indépendant dans des graphiques d'intersection géométrique . Considérons un ensemble de disques, où chaque disque a un diamètre et est centré sur l'un des points de votre ensemble $t$ $C$ . Nous pouvons maintenant former un graphique d'intersection géométrique, où il y a un sommet pour chaque disque et une arête entre deux sommets si leurs disques correspondants se croisent. Le problème de trouver un ensemble indépendant dans ce type de graphique a été étudié et il existe des algorithmes d'approximation pour ce problème que vous pourriez essayer d'utiliser.

Si vous voulez l'optimum exact plutôt qu'une approximation, vous pouvez utiliser n'importe lequel des "gros marteaux" standard, comme un solveur SAT ou un solveur ILP. Il existe un moyen simple de formuler le problème d'ensemble indépendant en tant qu'instance SAT, puis vous pouvez lui appliquer un solveur SAT pour déterminer s'il existe un sous-ensemble de points qui sont tous éloignés les uns des autres. $n$ $\ge t$

DW
la source