Bonjour,
Je fais un algo génétique pour de la coloration de graphe.
J'ai défini un opérateur de croisement qui prend un sous ensemble des noeuds du graphe et qui échange les couleurs de ces noeuds entre les 2 solutions considérées.
Voici mon pb :
J'ai deux séquences de n couleurs variant chacune de (0 à k-1), par exemple :
0 0 0 1 4 2 0 4 2 1 0 2 3 3 1 4 2 4
1 3 2 1 3 0 0 3 3 1 0 2 2 1 1 4 0 3
J'aimerais établir une table d'équivalence entre les couleurs de la première et de la deuxième séquence.
Ici ça pourrait donner :
0 1 2 3 4 -> 0 à k-1
? 1 0 ? 3 -> permutation de [|0,k-1|]
L'objectif serait de minimiser le nombre de couples des deux séquences qui ne tapent pas dans cette table...
Pour le moment la seule solution que je vois c'est de compter les paires et de choisir les paires finales en commençant par les paires similaires les plus nombreuses, mais l'algo est assez lent..
Vous voyez un algo efficace pour résoudre ce pb ?
)
