Algorithme / approximation de la distance de consigne / de Hamming indépendant combiné

Question

Entrée: Graphique G Sortie: plusieurs ensembles indépendants, de sorte que les membres d'un nœud à tous les ensembles indépendants est unique. Un nœud a donc aucune connexion à un nœud dans son propre ensemble. Voici un exemple de chemin.

Depuis des éclaircissements ont été appelé ici une autre rephrasal:

Diviser un graphique donné en ensembles de sorte que

1. je peux dire à un nœud de tous les autres par son appartenance à des ensembles par exemple si le noeud i est présent uniquement dans la série A aucun autre noeud doit être présent dans l'ensemble A seulement

   si le noeud j est présent dans la série A et B, alors aucun autre noeud doit être présent dans l'ensemble A et B seulement. si l'appartenance de noeuds est codée par un motif de bits, ces configurations de bits ont distance de Hamming d'au moins un

2. si deux noeuds sont contiguës dans le graphique, ils ne devraient pas être présentes dans le même ensemble, par conséquent, être un ensemble indépendant

Exemple: B n'a pas de noeuds adjacents D => A, A => D

Solution:

1. A B /
2. / B D

A possède motif de bits 10 et aucun noeud adjacent dans son ensemble. B a bit motif 11 et aucun noeud adjacent, D a 01 par conséquent, tous les noeuds ont distance de Hamming d'au moins 1 un des noeuds non adjacents => correct

Faux, parce que D et A sont connectés:

1. A D B
2. / D B

A a bit motif 10 et D dans son ensemble, ils sont adjacents. B a bit motif 11 et aucun noeud adjacent, D a 11 de même que B, alors il y a deux erreurs dans cette solution et il est donc pas accepté.

Bien sûr, cela devrait être étendu à d'autres jeux comme le nombre de nœuds augmente dans le graphique, car vous avez besoin au moins des ensembles de log(n).

Je l'ai déjà écrit une transformation en MAX-SAT, utiliser un solveur pour cela. mais le nombre de clauses est juste grand. Une approche plus directe serait bien. Jusqu'à présent, j'ai une approximation, mais je voudrais une solution exacte ou tout au moins une meilleure approximation.

J'ai essayé une approche où je un essaim de particules à optimize d'une solution arbitraire vers un meilleur. Cependant, le temps d'exécution est assez horrible et les résultats sont loin d'être grande. Je cherche un algorithme dynamique ou quelque chose, mais je ne peux pas comprendre comment diviser et conquérir ce problème.

Answer 1

Pas une réponse complète, et je ne sais pas comment elle sera utile pour vous. Mais va ici:

La distance de Hamming me frappe comme un hareng rouge. Votre énoncé du problème dit qu'il doit être d'au moins 1, mais il pourrait être 1000. Il suffit de dire le codage binaire pour les adhésions ensemble de chaque nœud est unique.

Votre relevé de problème ne sort pas, mais votre solution ci-dessus suggère chaque nœud doit être membre d'au moins 1 ensemble. c'est à dire. un bit codant pour l'ensemble des 0 est interdit pour les adhésions d'ensemble de tout noeud.

Ignorer les noeuds connectés pour un moment, les nœuds disjoints sont faciles: nombre Il suffit de les séquentiellement avec un codage binaire utilisé. Enregistrer ceux pour le dernier.

Votre exemple ci-dessus utilise les bords dirigés, mais encore une fois, qui me frappe comme un hareng rouge. Si A ne peut pas être dans le même ensemble que D parce que A => D, D ne peut pas être dans le même ensemble que A = indépendamment du fait que D> A.

Vous mentionnez besoin au moins log (N) ensembles. Vous aurez également à la plupart des jeux de N. Un graphique entièrement connecté (avec (N ^ 2-N) / 2 arêtes non orientés), il faudra N ensembles contenant chacun un seul noeud.

En fait, si votre graphique contient un simplex entièrement connecté de dimensions M (M dans 1..N-1) avec M + 1 sommets et (M ^ 2 + M) / 2 arêtes non orientées, vous aurez besoin d'au moins M + 1 ensembles.

Dans votre exemple ci-dessus, vous avez un tel simplex (M = 1) avec 2 sommets {A, D} et 1 (undirected) bord {(A, D)}.

Il semblerait que votre problème se résume à trouver les plus simplexes entièrement connectés dans votre graphique. Autrement dit, vous avez un problème de routage: Combien de dimensions avez-vous besoin d'acheminer vos bords si aucune croix? Il ne ressemble pas à un problème très évolutif.

Le premier grand simplex est facile Trouvées. Chaque noeud sommet obtient un nouveau jeu avec son propre bit.

Les nœuds disjoints sont faciles. Une fois que les noeuds connectés sont traitées, le nombre des noeuds simplement disjoints sauter séquentiellement des motifs de bits utilisés précédemment. A partir de votre exemple ci-dessus, étant donné que A et D prennent 01 et 10, le prochain modèle binaire disponible B est 11.

La partie la plus délicate devient alors comment plier les simplexes restant autant que possible dans la gamme existante avant de créer de nouveaux ensembles avec de nouveaux morceaux. Lors du pliage, on doit utiliser 2 ou plusieurs bits (fixe) pour chaque noeud, et les bits (fixe) ne doit pas se croisent avec les bits (fixe) pour tout noeud adjacent.

Considérez ce qui arrive à votre exemple ci-dessus lorsque l'on ajoute un autre nœud, C, à l'exemple:

Si C se connecte directement à la fois A et D, alors le problème initial est de trouver le 2-simplex avec 3 sommets {A, C, D} et 3 arêtes {(A, C), (A, D), ( CD)}. Une fois que A, C et D prennent les configurations de bits 001, 010 et 100, le plus bas motif de bits disponibles pour disjoints B est 011.

Si, d'autre part, C relie directement A ou D, mais pas les deux, le graphique a deux 1-simplexes. Supposons que nous trouvons le 1-simplex avec des sommets {A, D} d'abord en leur donnant les motifs de bits 01 et 10, le problème devient alors comment plier C dans cette gamme. Le seul motif de bits avec au moins 2 bits est 11, mais qui intersecte avec quel que soit le noeud C Connects pour que nous devons créer un nouvel ensemble et de mettre C en elle. A ce stade, la solution est similaire à celle ci-dessus.

Si C est disjoint, B ou C auront la configuration binaire 11 et le reste on aura besoin d'un nouvel ensemble et obtenir le modèle 100 bits.

Supposons que C se connecte à B, mais pas à A ou D. Encore une fois, le graphique a deux 1-simplexes mais cette disjoints de temps. Supposons que {A, D} se trouve d'abord comme ci-dessus donnant A et D des motifs de bits 10 et 01. Nous pouvons plier B ou C dans la gamme existante. Le motif de bits uniquement disponible dans la plage est 11 et B ou C pourrait obtenir ce motif que ni est adjacent à A ou D. Une fois 11 est utilisé, aucun motif de bits avec 2 ou plusieurs bits ensemble restent, et nous devrons créer un nouvel ensemble pour le noeud restant en lui donnant le motif 100 bits.

Supposons que C se connecte à tous 3 A, B et D. Dans ce cas, le graphe présente un 2-simplex avec 3 vertexes {A, C, D} et un 1-simplex avec 2 sommets {B, C}. En procédant comme ci-dessus, après le traitement de la plus grande simplex, A, C et D ont des configurations de bits 001, 010, 100. Pour le pliage B dans cette gamme, les motifs de bits disponibles avec 2 ou plusieurs bits ensemble sont: 011, 101, 110 et 111. Tous ces éléments, sauf 101 Intersection avec C si B obtiendrait le modèle binaire 101.

La question devient alors: Comment pouvez-vous trouver efficacement les plus grandes simplexes entièrement connectés

Si trouver le plus grand simplex entièrement connecté est trop cher , on pourrait mettre une limite supérieure approximative sur le potentiel simplexes entièrement connectés en trouvant des minimums maximales en termes de connexions:

1. balayage par les bords de la mise à jour sommets avec un compte de la des bords de raccordement.

2. Pour chaque nœud connecté, créez un tableau de départ compte zéro Cn où Cn est le nombre d'arêtes connecté au noeud n.

3. balayage à travers les bords de nouveau, pour les noeuds connectés n1 et n2, incrémenter le compteur dans n1 correspondant à Cn2 et vice versa. Si Cn2> Cn1, mettez à jour le dernier décompte dans le tableau n1 et vice versa.

4. balayage à travers les noeuds connectés à nouveau, le calcul d'une limite supérieure la plus grande simplex chaque noeud pourrait être une partie de. Vous pouvez construire un tableau de trou de pigeon avec une liste de sommets pour chaque limite supérieure tout en balayant à travers les noeuds.

5. Travail à travers le réseau trous de pigeon du plus grand au plus petit extraction et les noeuds de pliage dans des ensembles uniques.

Si vos nœuds sont dans un ensemble N et vos bords dans un ensemble E, la complexité sera: O (| N | + | E | + O (étape 5))

Si les suffixes d'approximation ci-dessus, la question devient: Comment pouvez-vous efficacement plier les noeuds dans les gammes existantes étant donné les exigences

Answer 2

peut-être pas la réponse que vous pouvait s'y attendre, mais je ne peux pas trouver un endroit pour ajouter un commentaire. Donc, je tape directement ici. Je ne peux pas bien comprendre votre question. Ou at-il besoin de connaissances spécifiques pour comprendre? Quel est cet ensemble indépendant? Comme je connais un noeud dans un ensemble indépendant d'un graphe orienté un chemin à deux voies à un autre noeud dans cet ensemble. Est-ce votre notion même?

Si ce problème est comme ce que je suppose, des ensembles indépendants se trouvent par cet algorithme: 1. faire la recherche en profondeur d'abord sur le graphe orienté, enregistre le temps d'un arbre enraciné par ce nœud est traversée. 2. puis inverser tous les bords dans ce graphique 3. faire à nouveau la recherche de profondeur Frist sur le graphique modifié. Le algorihtm est expliqué précisément par le livre "introduction à alogrithm"