Algorithme pour le nombre de transitions entre deux partitions (graphiques)

Question

Dites que j'ai un ensemble (ou un graphique) qui est partitionné en groupes. Je suis intéressé à trouver le nombre de transitions entre deux partitions, où une transition implique de prendre un élément hors d'une partition et en le déplaçant dans une autre (ou partition singleton par lui-même)

Par exemple il y a une transition entre les partitions

1 2 | 3 et 1 | 2 | 3

mais entre 1 2 3 4 et 1 2 | 3 | 4

Le nombre minimum de transitions est 2 je crois.

Donc, ma question est de savoir s'il existe des algorithmes qui, étant donné une paire de partitions et un ensemble, peuvent renvoyer le nombre d'états de transitions entre eux? Il y a une complication supplémentaire que cet ensemble représente réellement un graphe et je voudrais que chaque partition (et partition de transition) soit connectée (ie 1 2 | 3 serait invalide s'il n'y a pas de connexion in/direct entre 1 et 2). 2 débloqué par la partition unique de 3) mais à moins que vous ne soyez vraiment éclairé sur ce sujet, vous pouvez très probablement ignorer cela.

Merci

Comme une note j'ai une méthode que je pensais à moi-même qui est essentiellement de trouver tous les voisins d'une partition A (c.-à-toutes les partitions qui se trouvent dans une transition) et faire la même chose pour la partition B et s'il y a un chevauchement entre ces deux ensembles de voisins, alors ils sont à une transition. Cependant cette méthode devient très chère très rapidement.

Answer 1

Je voudrais développer un peu votre méthode, et essentiellement construire un graphique et faire une recherche graphique. Les sommets du graphe seraient un partitionnement valide de l'ensemble et les bords seraient des transitions. Vous pouvez réellement construire et rechercher en même temps et ne construire que la partie du graphique nécessaire à la recherche. Pour ce faire, j'utiliserais un A * (ou une autre meilleure première recherche) et générerais à chaque étape tous les voisins de la partition actuelle. La partie délicate est de déterminer la meilleure heuristique pour la recherche A *. Vous pouvez probablement estimer le nombre de transitions en supposant que toutes les transitions entraîneraient des partitions connectées (en fait, ignorez votre contrainte).

Ceci est évidemment coûteux, mais vous économisez du temps et de l'espace en utilisant une recherche best-first et en générant le graphique que vous allez.