J'ai un graphe non orienté non pondéré et je veux sélectionner nœuds dans telle sorte qu'ils soient aussi loin que possible les uns par rapport aux autres, en termes de distance géodésique . En d'autres termes, ils doivent être répartis sur le graphique autant que possible.
Soit avoir la longueur d'un plus court chemin entre et dans . Maintenant, pour un ensemble de sommets , définissez
Soit le problème SCATTERED SET le problème qui sur l'entrée demande de trouver un ensemble de sommets maximisant .
Existe-t-il un algorithme efficace qui résout l'ensemble dispersé?
Réponses:
Je ne sais pas s'il existe un algorithme à temps polynomial (on dirait qu'il pourrait être difficile à NP), mais voici quelques approches algorithmiques plausibles que vous pourriez envisager, si vous devez le résoudre dans la pratique:
Heuristique
Un algorithme bien exploré est Furthest Point First (FPF). À chaque itération, il choisit un point le plus éloigné de l'ensemble de points sélectionné jusqu'à présent. Répéterk fois. Comme il s'agit d'une stratégie gourmande, il n'y a aucune raison de s'attendre à ce que cela donne une réponse optimale ou même proche de l'optimale, et elle a été conçue pour optimiser une fonction objective légèrement différente ... mais dans certains contextes, elle donne une approximation raisonnable, donc cela pourrait valoir la peine d'essayer.
FPF est issu de la littérature sur le clustering basé sur les graphiques et a été présenté dans le document de recherche suivant:
Teofilo F. Gonzalez. Regroupement pour minimiser la distance maximale entre les clusters . Informatique théorique, vol 38, pp.293-306, 1985.
Vous pouvez essayer d'explorer la littérature sur le clustering basé sur des graphiques pour voir si quelqu'un a étudié votre problème spécifique.
Algorithmes exacts
Si vous rencontrez ce problème dans la pratique et avez besoin d'une solution optimale exacte, vous pouvez essayer de le résoudre à l'aide d'un solveur ILP.
Voici comment. Introduire des variables 0 ou 1Xje , où Xje indique si le je e sommet a été sélectionné, et 0 ou 1 variable yi , j , ce qui signifie que yi , j= 1 seulement si Xje= 1 et Xj= 1 . Maintenant, maximisez la fonction objectif∑i , jré( i , j )yi , j , soumis aux contraintes ∑Xje≤ k et Xje≥yi , j et Xj≥yi , j . Résolvez maintenant cet ILP avec un solveur ILP standard. Comme ILP est NP-difficile, il n'y a aucune garantie que cela sera efficace, mais cela pourrait fonctionner sur certaines instances problématiques.
Une autre approche consiste à utiliser MAX-SAT pondéré . En particulier, introduire des variables booléennesXje , où Xje est vrai si le je e sommet a été sélectionné, et les variables yi , j . La formule estϕ ∧∧i , jyi , j , où ϕ doit être vrai (ses clauses ont du poids W pour certains très grands W ) et chaque clause yi , j est donné du poids ré( i , j ) . Définissez la formuleϕ être vrai si tout au plus k du Xje sont vraies (voir ici pour plus de détails sur la façon de le faire) et siyi , j=Xje∧Xj pour tous i , j . Maintenant, la solution à ce problème MAX-SAT pondéré est la solution au problème d'origine, vous pouvez donc essayer de lancer un solveur MAX-SAT pondéré sur le problème. Les mêmes mises en garde s'appliquent.
la source
Non, le problème est NP-complet.
Laisser( G , k ) être une instance de INDEPENDENT SET. Constructiong′ en ajoutant un sommet universel u à g . L'observation cruciale est que la distance entre deux sommets dansg est 1 po g′ si et seulement si elles sont adjacentes g et 2 sinon.
Maintenant, la solution optimale de SCATTERED SET en entrée(g′, k ) est 2 (k2) si et seulement si g a un ensemble de taille indépendant k .
la source