contrainte pour éviter de générer des doublons dans cette tâche de recherche

Question

Je dois résoudre le problème d'optimisation suivant: Étant donné un ensemble d'éléments (E1, E2, E3, E4, E5, E6) créer un ensemble arbitraire de séquences, par ex.

seq1:E1,E4,E3 
seq2:E2 
seq3:E6,E5 

et une fonction f qui donne une valeur pour chaque paire d'éléments, par ex.

f(E1,E4) = 5 
f(E4,E3) = 2 
f(E6,E5) = 3 
... 

en outre, il donne également une valeur pour la paire d'un élément combiné avec un élément spécial T, par ex.

f(T,E2) = 10 
f(E2,T) = 3 
f(E5,T) = 1 
f(T,E6) = 2 
f(T,E1) = 4 
f(E3,T) = 2 
... 

La fonction utilitaire qui doit être optimisée est la suivante: L'utilité d'une séquence est la somme de l'utilité de toutes les séquences. L'utilité d'une séquence A1, A2, A3, ..., AN est égale à f (T, A1) + f (A1, A2) + f (A2, A3) + ... + f (AN, T) pour notre exemple un ensemble de séquences ci-dessus cela conduit à

seq1: f(T,E1)+f(E1,E4)+f(E4,E3)+f(E3,T) = 4+5+2+2=13 
seq2: f(T,E2)+f(E2,T) =10+3=13 
seq3: f(T,E6)+f(E6,E5)+f(E5,T) =2+3+1=6 
Utility(set) = 13+13+6=32 

je tente de résoudre une version plus grande (plus d'éléments que 6, et non 1000) de ce problème en utilisant a * et une heuristique. En partant de séquences nulles et en ajoutant des éléments par étapes soit à des séquences existantes, soit en tant que nouvelle séquence, jusqu'à obtenir un ensemble de séquences contenant tous les éléments. Le problème je rencontre est le fait que lors de la génération des solutions possibles je finis avec des doublons, par exemple dans l'exemple ci-dessus toutes les combinaisons suivantes sont générées:

seq1:E1,E4,E3 
seq2:E2 
seq3:E6,E5 
+ 
seq1:E1,E4,E3 
seq2:E6,E5 
seq3:E2 
+ 
seq1:E2 
seq2:E1,E4,E3 
seq3:E6,E5 
+ 
seq1:E2 
seq2:E6,E5 
seq3:E1,E4,E3 
+ 
seq1:E6,E5 
seq2:E2 
seq3:E1,E4,E3 
+ 
seq1:E6,E5 
seq2:E1,E4,E3 
seq3:E2 

qui tous ont une utilité égale, étant donné que l'ordre du les séquences n'ont pas d'importance. Ce sont toutes des permutations des 3 séquences, puisque le nombre de séquences est arbitraire, il peut y avoir autant de séquences que d'éléments et une faculté (!) Quantité de doublons générés ... Une façon de résoudre un tel problème est de rester déjà visité états et ne les revisite pas. Cependant, comme stocker tous les états visités requiert une grande quantité de mémoire et que le fait de comparer deux états peut être une opération assez coûteuse, je me demandais s'il n'y avait pas moyen de les éviter en premier lieu.

la question: Est-il un moyen de gradin construire tout cela séquence contraignant l'ajout d'éléments de façon que seules les combinaisons de séquences sont générées au lieu de toutes les variantes de séquences (ou de limiter le nombre de copies). Par exemple, je n'ai trouvé un moyen de limiter la quantité de 'duplicats' générés en déclarant qu'un élément Ei devrait toujours être dans un seqj avec j < = i, donc si vous aviez deux éléments E1, E2 seulement

seq1:E1 
seq2:E2 

serait généré, et non

seq1:E2 
seq2:E1 

Je me demandais s'il y avait une telle contrainte qui empêcherait les doublons d'être produit du tout, sans manquer de générer toutes les combinaisons de jeux.

Answer 1

Eh bien, c'est simple.Permettre la génération de seulement ces séquences qui sont triés en fonction de premier élément, qui est, dans l'exemple ci-dessus, seulement

seq1:E1,E4,E3 
seq2:E2 
seq3:E6,E5 

serait correct. Et vous pouvez le garder très facilement: ne jamais autoriser une séquence supplémentaire dont le premier membre est inférieur au premier membre de son prédécesseur.