Ordre de construction de mines

**philben** · 21/07/2011, 03h19

bonsoir,

En lisant l'excellent algo de Alikendarfen (post 19/07 à 13h08), je me suis demandé pourquoi il ne conservait que la meilleure amélioration par boucle ?
J'ai donc modifié l'algo dans ce sens c'est à dire que si T12 > T21, on swap les mines et on ajoute alors la prod de la mine 2 sinon on ajoute la prod de la mine1.

Résultats (Tri des mines + algo)

les 324 mines P = 5 - Résultat : 2,15567768032801 (Temps ~ 0)
les 500 mines P = 5 - Résultat : 14,8174076121783 (temps ~ 0)
30 000 mines P = 5 - Temps : 30ms (jeu de test perso)

Le code de l'algo en VBA

:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
' Dérivé du code original de Alikendarfen
Private Sub Algo(ByVal ProdInitiale As Double)
   Dim Mine1 As tMine, Mine2 As tMine
   Dim ProductionCourante As Double, t12 As Double, t21 As Double
   Dim i As Long, Swap As Long
   Dim Ameliore As Boolean
 
   Do
 
      Ameliore = False
      ' Production de départ
      ProductionCourante = ProdInitiale
      ' Parcourt des paires de mines
      For i = 1 To UBound(gMines)
         Mine1 = gMines(gIndex(i - 1))
         Mine2 = gMines(gIndex(i))
         ' Temps mine1 avant mine2, partant de la production courante
         t12 = (Mine1.Cout / ProductionCourante) + (Mine2.Cout / (ProductionCourante + Mine1.Prod))
         ' Temps mine2 avant mine1, partant de la production courante
         t21 = (Mine2.Cout / ProductionCourante) + (Mine1.Cout / (ProductionCourante + Mine2.Prod))
         ' Ce gain est il meilleur ?
         If (t12 > t21) Then
 
            ProductionCourante = ProductionCourante + Mine2.Prod
 
            Swap = gIndex(i - 1)
            gIndex(i - 1) = gIndex(i)
            gIndex(i) = Swap
 
            Ameliore = True
         Else
            ProductionCourante = ProductionCourante + Mine1.Prod
         End If
      Next i
 
   ' Tant qu'on améliore, on continue
   Loop While Ameliore
 
End Sub

Qu'en pensez-vous ? J'ai loupé quelque chose ?

Amicalement,

Philippe

**Alikendarfen** · 21/07/2011, 08h41

Envoyé par philben

bonsoir,

En lisant l'excellent algo de Alikendarfen (post 19/07 à 13h08),...

C'est gentil ! Mais l'algo n'est pas de moi, mais de Baruch... celui là, je l'ai seulement porté en C#.

Envoyé par philben

je me suis demandé pourquoi il ne conservait que la meilleure amélioration par boucle ?
J'ai donc modifié l'algo dans ce sens c'est à dire que si T12 > T21, on swap les mines et on ajoute alors la prod de la mine 2 sinon on ajoute la prod de la mine1.

Pourquoi pas...
Effectivement, ça peut améliorer les choses. Mais je crois qu'on reste malgré tout dans le domaine de l'heuristique... ?

Je ferai un petit bench sur cette version dès que j'aurai le temps.

Merci !

**Baruch** · 21/07/2011, 12h07

Tiens ! Bonjour philben,

Effectivement, on peut modifier l'algo par permutations comme tu le fais pour le rendre plus rapide.
Mais, la raison pour laquelle je ne permute que le couple au gain le plus fort à chaque itération, c'est que j'essaye d'avoir le plus de chance d'aboutir à la fin à la solution idéale (et peut-être avoir un temps proche de celle-ci). C'est une intuition à vérifier :

Il faudrait comparer ton algo et le simple algo par permutations par rapport à un algo exact : voir le nombre d'erreurs commises et les écarts de temps.

Et puis pourquoi continuer vers la droite comme tu le fais, et pas vers la gauche ?

Quand on permute un couple de mines adjacentes, il y a 2 nouveaux couples qui apparaissent : un à gauche et un à droite. Toi tu étudies celui à droite, celui à gauche étant étudié à la prochaine itération.

Tout ça pour dire qu'on ne sait pas grand chose des listes idéales 2 à 2, ni comment s'arranger pour obtenir la liste idéale :/

**philben** · 22/07/2011, 03h17

Bonsoir,

Mais l'algo n'est pas de moi, mais de Baruch... celui là, je l'ai seulement porté en C#.

Bravo donc à Baruch pour l'algo et à Alikendarfen pour le code en c#

Tout ça pour dire qu'on ne sait pas grand chose des listes idéales 2 à 2, ni comment s'arranger pour obtenir la liste idéale

En effet, j'ai donc modifié l'algo pour démarrer avec une distance > 1 entre les mines étudiées puis cette distance diminue d'un pas de 1 lorsqu'il n'y a plus d'amélioration jusqu'à 1.

Après quelques petits essais, une distance maxi entre 3 et 7 semble être un bon compromis entre rapidité et convergence vers l'optimum, en sachant que les mines sont initialement triées.

Par exemple pour 100 000 mines le résultat est amélioré si la distance initiale est 2 ou + par rapport à une distance initiale de 1.

La fonction en VBA :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
' Dérivé de l'algo de Baruch et du code original en c# de Alikendarfen
Private Sub AlgoDistance(ByVal ProdInitiale As Double, ByVal DistanceMax As Long)
   Dim Mine1 As tMine, Mine2 As tMine
   Dim ProductionCourante As Double, t12 As Double, t21 As Double
   Dim i As Long, Swap As Long, Distance As Long, j As Long
   Dim Ameliore As Boolean
 
   ' Démarrage avec la distance la + grande entre les mines
   Distance = DistanceMax
 
   Do
 
      Ameliore = False
 
      ' Production de départ
      ProductionCourante = ProdInitiale
 
      ' Parcourt des paires de mines selon le distance entre mines
      For i = Distance To UBound(gMines)
         Mine1 = gMines(gIndex(i - Distance))
         Mine2 = gMines(gIndex(i))
 
         ' Temps mine1 avant mine2, partant de la production courante
         t12 = (Mine1.Cout / ProductionCourante) + (Mine2.Cout / (ProductionCourante + Mine1.Prod))
         ' Temps mine2 avant mine1, partant de la production courante
         t21 = (Mine2.Cout / ProductionCourante) + (Mine1.Cout / (ProductionCourante + Mine2.Prod))
 
         ' Ce gain est il meilleur ?
         If (t12 > t21) Then
            Swap = gIndex(i - Distance)
            gIndex(i - Distance) = gIndex(i)
            gIndex(i) = Swap
            Ameliore = True
         End If
 
         ' Production courante jusqu'à i - 1
         For j = i - Distance To i - 1
            ProductionCourante = ProductionCourante + gMines(gIndex(j)).Prod
         Next j
      Next i
 
      ' Distance réduite si pas d'amélioration
      If Not Ameliore Then Distance = Distance - 1
 
   ' Tant qu'on améliore ou distance conforme, on continue
   Loop While Ameliore Or Distance >= 1
 
End Sub

J'ai aussi testé de relancer plusieurs fois l'algo mais ça n'a pas amélioré le résultat initialement trouvé.

Amicalement,

Philippe

**Baruch** · 23/07/2011, 12h54

Hmmm je pense qu'un peu de recherche théorique ne ferait pas de mal pour améliorer l'algo par permutations.

Bon moi j'ai une question, qui pourrait être utile :

Soit L une liste idéale, rev(L) est-elle la pire liste possible ?

rev(L) étant la liste L renversée, càd parcourue de droite à gauche.

**Alikendarfen** · 23/07/2011, 13h59

Envoyé par Baruch

Hmmm je pense qu'un peu de recherche théorique ne ferait pas de mal pour améliorer l'algo par permutations.

Bon moi j'ai une question, qui pourrait être utile :

Soit L une liste idéale, rev(L) est-elle la pire liste possible ?

rev(L) étant la liste L renversée, càd parcourue de droite à gauche.

Peut-être, peut-être pas...

Quelques remarques :

- Pour la meilleure liste possible, on peut partir de la fin.

- Il y a probablement beaucoup de mauvais chemins intermédiaires.

- L'algo NDO (qui au bout du compte reste le meilleur algo exact), doit générer plusieurs millions de chemins intermédaires pour aboutir à une unique solution (qui est la seule optimale 2 à 2) sur le jeu de test d'elentarion. Pour le dire autrement, les chemins intermédiaires optimaux 2 à 2 sont très nombreux.

**Baruch** · 23/07/2011, 21h39

Euh attends l'algo NDO c'est pas l'algo par insertion ? Parce-que celui-ci n'est pas exact (5 erreurs sur 10000 essais je crois).

- Pour la meilleure liste possible, on peut partir de la fin.

Tu veux dire dans un approche où on construit la liste pas à pas ? Si c'est ça, il vaut mieux partir du début puisque sinon il faut recalculer à chaque fois les mines placées.

Pour le dire autrement, les chemins intermédiaires optimaux 2 à 2 sont très nombreux.

Je suis entrain d'essayer de trouver le nombre maximal de liste idéales 2 à 2 (de taille n) sur un jeu de n mines.

n=1 -> 1 liste
n=2 -> 1 liste
n=3 -> 3 listes au plus

Qui fait la suite ? xD

**Alikendarfen** · 24/07/2011, 10h05

Envoyé par Baruch

Euh attends l'algo NDO c'est pas l'algo par insertion ? Parce-que celui-ci n'est pas exact (5 erreurs sur 10000 essais je crois).

... encore ! Non, c'est l'algo naïf avec dominances et optimalité 2 à 2...

Envoyé par Baruch

Tu veux dire dans un approche où on construit la liste pas à pas ? Si c'est ça, il vaut mieux partir du début puisque sinon il faut recalculer à chaque fois les mines placées.

Non ^^... on fixe arbitrairement Tfin et Pfin = p0 + somme(pi) et on remonte le temps. Le problème est symétrique dans sa construction.
Est-ce que ça peut apporter qq chose ?

Envoyé par Baruch

Je suis entrain d'essayer de trouver le nombre maximal de liste idéales 2 à 2 (de taille n) sur un jeu de n mines.

n=1 -> 1 liste
n=2 -> 1 liste
n=3 -> 3 listes au plus

Qui fait la suite ? xD

Bonne idée...
... c'est quand même curieux qu'il n'y ait pas de théorie sur tout ça...
Quels mots clés on pourrait utiliser pour trouver sur google ???

Sinon, pour ceux qui s'y connaissent en math, y aurait-il un moyen d'exprimer la suite sous forme de fraction continue ?

Edit : Autre truc :
@Baruch, l'approche que tu avais évoquée où on précalcule tous les p* :
Dans ce cadre, on constate :
A- Des p* < pO
B- Des p* > p0 et < pTot
C- Des p* > pTot
Que peut-on déduire sur A et C tant qu'il y a des B ??
Ou pour le dire autrement, l'ordre pour les mines A et C est-il impacté par celles dans le cas B (en admettant par exemple qu'on ne s'intéresse qu'aux mines qui sont dans A et C et pas dans B) ??

**Baruch** · 28/07/2011, 16h51

Désolé je n'ai pas beaucoup l'occasion de répondre, je suis pas chez moi.

... encore ! Non, c'est l'algo naïf avec dominances et optimalité 2 à 2...

Ah ouiiii ^^' Faut pas utiliser des abréviations aussi ^^.

Mais le plus rapide c'est pas l'algo par combinaisons avec dominances et optimalité 2 à 2 ?

Non ^^... on fixe arbitrairement Tfin et Pfin = p0 + somme(pi) et on remonte le temps. Le problème est symétrique dans sa construction.
Est-ce que ça peut apporter qq chose ?

Oui bon d'accord.

La question de la symétrie est à mon avis intéressante, c'est la raison de ma question plus haut.

Sinon, pour ceux qui s'y connaissent en math, y aurait-il un moyen d'exprimer la suite sous forme de fraction continue ?

Ca m'étonnerait, puisque ça dépend de l'ensemble de mines considéré.

Edit : Autre truc :
@Baruch, l'approche que tu avais évoquée où on précalcule tous les p* :
Dans ce cadre, on constate :
A- Des p* < pO
B- Des p* > p0 et < pTot
C- Des p* > pTot
Que peut-on déduire sur A et C tant qu'il y a des B ??
Ou pour le dire autrement, l'ordre pour les mines A et C est-il impacté par celles dans le cas B (en admettant par exemple qu'on ne s'intéresse qu'aux mines qui sont dans A et C et pas dans B) ??

Désolé je ne comprends pas du tout ce que tu racontes ^^, tu peux expliciter stp ?

J'ai pas le temps de poster là, mais j'ai pas mal de trucs à raconter sur les listes idéales 2 à 2.

**Baruch** · 29/07/2011, 12h30

Je suis toujours coincé dans l'étude des listes idéales 2 à 2 à 3 éléments, mais voici quand même ce que j'ai trouvé :

D'abord voici comment étudier (plus) facilement les listes idéales 2 à 2 :

[AB]p est meilleur que [BA]p

équivaut à

cA/p + cB/(p+pA) <= cB/p + cA/(p+pB)

équivaut à

cA*(1+p/pA) <= cB*(1+p/pB) si pA et pB non nuls

équivaut à

fA(p) <= fB(p)

Donc, si vous voulez visualiser ce qui se passe :

Sur un graphique, tracer pour toutes les mines M la fonction fM. Ordonnée à l'origine cM, pente cM/pM.

fA(p) = fB(p) pour p = p*(A,B).

Le demi axe des p négatifs ne sert à rien.

Comment trouver les listes idéales 2 à 2 ?

Se placer à p0.
Choisir une mine A.
Se placer à p0+pA.
Choisir une mine parmi l'ensemble des mines M telles que fM(p0) >= fA(p0).
Se placer à p0+pA+pM, etc.
S'il n'y a aucune mine à choisir, revenir à l'étape précédente.

Voilà, c'est plus simple comme ça.

Le cas de 3 mines :

J'ai toujours pas réussi à tout comprendre, mais voici ce que j'ai fait :

Il existe au moins une liste idéale 2 à 2 (puisqu'il y a au moins la liste idéale).
Appelons-la ABC.

De là, on sait que BAC n'est pas idéale 2 à 2, ni ACB, puisqu'on permute 2 mines adjacentes.

Reste BCA, CAB, CBA.

Si BCA ou CAB est idéale 2 à 2, CBA ne l'est pas.
Si CBA est idéale 2 à 2, BCA et CAB ne le sont pas.

Donc l'ensemble des listes idéales 2 à 2 est contenu dans :

soit {ABC,BCA,CAB}
soit {ABC,CBA}

Penchons-nous sur le 2e cas. Peut-on vraiment avoir ABC et CBA, la liste renversée, idéales 2 à 2 ?

Si CBA peut effectivement être idéale 2 à 2, alors CBA ne peut pas être la pire liste possible, puisque BCA et CAB sont pires.
Donc si ABC est la liste idéale, on pourrait avoir rev(ABC) qui n'est pas la pire liste, et donc il n'y a pas la symétrie dont on parlait.

Je n'ai pas accès à mon pc, donc je n'ai pas pu tester si ce cas arrivait ou pas. Quelqu'un peut le faire ?

Je n'ai pas réussi à trouver d'exemple à la main, et en même temps je n'ai pas pu montrer que ce cas était impossible.

ABC et CBA sont idéales 2 à 2 équivaut à :

cA(1+p0/pA) <= cB(1+p0/pB)
cC(1+p0/pC) <= cB(1+p0/pB)
cB(1+(p0+pA)/pB) <= cC(1+(p0+pA)/pC)
cB(1+(p0+pC)/pB) <= cA(1+(p0+pC)/pA)

ce qui équivaut à

p0 <= p*(A,B) <= p0+pC
p0 <= p*(B,C) <= p0+pA

où p*(A,B) = p*(B,A) = (cB-cA)/(cA/pA - cB/pB)

ce système implique :

cB/pB <= cC/pC
cB/pB <= cA/pA
cC <= cB
cA <= cB
pB >= pC
pB >= pA

**JeitEmgie** · 29/07/2011, 13h03

Envoyé par Baruch

Je suis toujours coincé dans l'étude des listes idéales 2 à 2 à 3 éléments, mais voici quand même ce que j'ai trouvé :

j'ai regardé ce qui se passe visuellement lorsqu'on optimise l'ordre d'une liste déjà relativement bonne après une préparation par un algorithme de tri en O(n) (par exemple dominance-productivité ou dominance-theta en fonction du quel des deux donne le meilleur résultat sur l'ensemble de départ) :
dans un espace 2D où X est le coût C et Y le 1/Rendement, l'impression visuelle donnée par l'animation m'a amené à vérifier un résultat qui pour le moment n'a qu'une confirmation expérimentale :
l'ordre des éléments minimise la somme des surfaces des triangles (dans cet espace) formés par les éléments pris successivement par groupe de 3…

Si cela se confirme, cela met à mal l'idée de rechercher une optimisation 2 à 2.

**Baruch** · 29/07/2011, 17h43

Oui c'est une impression tout à fait justifiée, elle rejoint le fait que dans une liste idéale les mines sont globalement triée par rendement décroissant.

Ce qui me gêne dans votre hypothèse, c'est que vous prenez les mines 3 par 3. Pourquoi pas 4 par 4 ?

Enfin, peut-être est-ce vrai, mais je crois qu'on n'a pour l'instant aucun outil qui permette de le démontrer, ni de le réfuter.

**JeitEmgie** · 29/07/2011, 22h55

Envoyé par Baruch

Oui c'est une impression tout à fait justifiée, elle rejoint le fait que dans une liste idéale les mines sont globalement triée par rendement décroissant.

Ce qui me gêne dans votre hypothèse, c'est que vous prenez les mines 3 par 3. Pourquoi pas 4 par 4 ?

Enfin, peut-être est-ce vrai, mais je crois qu'on n'a pour l'instant aucun outil qui permette de le démontrer, ni de le réfuter.

ce n'est pas une hypothèse à proprement parler : c'est juste une constatation expérimentale en regardant le "film" des modifications en pas à pas dans l'espace 2D décrit…
on voit que les échanges des points diminuent la surface des triangles formés par 3 points successifs…
il ne vient pas à l'esprit de regarder ce qui se passe avec 4 points successifs…

de toute façon 4 points successifs n'ont aucune raison de toujours former un polygone convexe… la plupart du temps (c'est très visible dans l'exemple des 380 mines) 4 points successifs dans cet espace forment un Z…

à partir de là, la vérification par calcul de la somme des surfaces montre qu'en effet elle diminue en même temps que le temps s'optimise avec les échanges…
et donc la constatation expérimentale soulève la question : hasard des jeux pris pour les tests ou a-t-on mis le doigt sur quelque chose d'intéressant ?

**Baruch** · 30/07/2011, 10h09

Eh bien il faudrait alors formaliser cela ^^

Vous avez fait des tests sur plusieurs jeux de grande taille ?

**Baruch** · 02/08/2011, 15h55

J'ai réussi à trouver un exemple intéressant :

On a ABC et CBA toutes les 2 idéales 2 à 2.

A : p = 1 , c = 2 , c/p = 2
B : p = 3 , c = 4 , c/p = 1,33
C : p = 2,5 , c = 3,75 , c/p = 1,5

p*(A,B) = 3
p*(B,C) = 1,5
p*(A,C) = 3,5

p0 = 1
p0 + pA = 2
p0 + pB = 4
p0 + pC = 3,5

Je vous invite à faire un dessin pour comprendre, voir mon post plus haut.

On a ici un ensemble de 3 mines, tel que les seules listes idéales 2 à 2 sont ABC et CBA.

Donc l'une des deux est la liste idéale, ici c'est ABC.

CBA= rev(ABC), mais CBA n'est pas la pire liste possible, puisque BCA et CAB sont moins bien que CBA.
On n'a donc pas la symétrie dont on avait parlé.

**Baruch** · 05/08/2011, 21h46

Bon le sujet est un peu mort, mais vacances oblige ^^.

Je vois 3 algorithmes qu'il faudrait essayer (et que je vais coder en Caml) :

- L'algorithme par combinaisons, avec dominances et optimalité 2 à 2.

- Un algorithme par permutations amélioré :

Au lieu de permuter le couple de gain maximal à chaque itération, on fait cela :

Pour les couples à permuter qui sont isolés, càd qu'on a une sous-liste [ABCD] telle que [BC] est à améliorer, mais pas [AB] ni [CD], on les permute tous dans la même itération.

Pour les couples non isolés, càd qu'on a une sous-liste [M1...Mk] telle que tous les [Mi Mi+1] sont à améliorer, on réapplique l'algorithme sur chaque liste correspondant à la permutation de [M1M2], [M2M3], etc.

A la fin, on a donc un ensemble de listes, et on prend celle dont le temps est minimal.

Le problème c'est le nombre de listes au final, à voir...

- Encore une variante de l'algorithme par permutations :

Soit le tri de rang k :

A chaque itération, on permute le couple de mines distantes de k de gain maximal
S'il n'y a pas de couple à permuter, on arrête.

L'algorithme consiste à appliquer à la liste de départ un tri de rang n, puis n-1, n-2, etc. jusqu'au rang 2 (qui correspondant au tri par permutations original).

Je pense que ça traduit bien le fait qu'il faut trier la liste d'abord globalement puis plus précisément pour éviter au final d'être coincé dans une mauvaise liste idéale 2 à 2. Le problème c'est que cet algorithme prend sûrement trop de temps.

**Alikendarfen** · 06/08/2011, 11h55

Envoyé par Baruch

D'abord voici comment étudier (plus) facilement les listes idéales 2 à 2 :

[AB]p est meilleur que [BA]p

équivaut à

cA/p + cB/(p+pA) <= cB/p + cA/(p+pB)

équivaut à

cA*(1+p/pA) <= cB*(1+p/pB) si pA et pB non nuls

équivaut à

fA(p) <= fB(p)

...

Comment trouver les listes idéales 2 à 2 ?

Se placer à p0.
Choisir une mine A.
Se placer à p0+pA.
Choisir une mine parmi l'ensemble des mines M telles que fM(p0) >= fA(p0).
Se placer à p0+pA+pM, etc.
S'il n'y a aucune mine à choisir, revenir à l'étape précédente.

Pour info (et au risque d'être un peu lourd), ça c'est ce que fait l'algo NDO (naïf avec dominance et optimalité 2 à 2)...
... sauf que NDO inclut la dominance absolue (c1 < c2 et p1 > p2) en plus.

L'algo pourrait être amélioré à condition de trouver une condition simple déterminant à chaque p (p courant) une dominance à partir de p.

Dans l'idée, ça rejoint l'approche que tu avais évoquée :

Envoyé par Baruch

Bon je pense avoir trouvé quelque chose de très intéressant ^^ :
... etc (je ne remets pas tout le post)

Mais jusque là, je n'ai pas vu comment l'adapter efficacement...

Il faudrait un peu plus qu'une matrice, mais plutôt un critère disant qu'à partir de p, une partie des mines doivent nécessairement être placées avant d'autres... (donc la combinatoire serait nettement élaguée)

Quelqu'un a-t-il un tel critère (je ne me souviens pas si ça a déjà été déterminé) ?

**Alikendarfen** · 06/08/2011, 12h04

Envoyé par JeitEmgie

ce n'est pas une hypothèse à proprement parler : c'est juste une constatation expérimentale en regardant le "film" des modifications en pas à pas dans l'espace 2D décrit…
on voit que les échanges des points diminuent la surface des triangles formés par 3 points successifs…
il ne vient pas à l'esprit de regarder ce qui se passe avec 4 points successifs…

de toute façon 4 points successifs n'ont aucune raison de toujours former un polygone convexe… la plupart du temps (c'est très visible dans l'exemple des 380 mines) 4 points successifs dans cet espace forment un Z…

à partir de là, la vérification par calcul de la somme des surfaces montre qu'en effet elle diminue en même temps que le temps s'optimise avec les échanges…
et donc la constatation expérimentale soulève la question : hasard des jeux pris pour les tests ou a-t-on mis le doigt sur quelque chose d'intéressant ?

Pour la forme de la courbe... ça semble juste normal. Si on prend une courbe (x = temps ; y = production ou y = cout) :
- La courbe est croissante
- La meilleure courbe est celle qui se termine le plus "à gauche"
> donc la surface des triangles est nécessairement minimisée globalement
> et localement aussi du fait de l'idéalité deux à deux (?)

**Baruch** · 06/08/2011, 12h10

Pour info (et au risque d'être un peu lourd), ça c'est ce que fait l'algo NDO (naïf avec dominance et optimalité 2 à 2)...
... sauf que NDO inclut la dominance absolue (c1 < c2 et p1 > p2) en plus.

Ah oui c'est vrai ^^. Mais ce post c'était juste pour montrer comment on pouvait trouver les listes idéales 2 à 2 plus facilement (et visuellement).

Je ne comprends pas pourquoi tu n'utilises pas l'algo par combinaisons avec dominances et optimalité 2 à 2 ?

L'algo pourrait être amélioré à condition de trouver une condition simple déterminant à chaque p (p courant) une dominance à partir de p.

Oui je pensais avoir trouvé une telle dominance, mais je crois qu'en fait elle était erronée. Je vais replonger dans le problème.

Ce qui est sûr, c'est que trouver toutes les listes idéales 2 à 2 puis prendre la meilleure, ce n'est pas efficace.

Tu penses quoi des 2 algos par permutations que j'ai évoqués plus haut ?

**Alikendarfen** · 06/08/2011, 12h24

Envoyé par Baruch

Je ne comprends pas pourquoi tu n'utilises pas l'algo par combinaisons avec dominances et optimalité 2 à 2 ?

Parce que cet algo est moins efficace : pour étudier les combinaisons, ou plutôt pour identifier que n arrangements correspondent à la même combinaison, il faut comparer ces arrangements, ce qui nécessite un certain "d'investissement" dans ce calcul.
Or par ailleurs, étant donné une combinaison, il y a "très peu" d'arrangements idéaux deux à deux.

Edit : de plus, dans l'algo par combinaisons, il faut maintenir en mémoire ces combinaisons, à une étape donnée du calcul, et ça coute cher aussi en termes de perf.

... donc le truc est de savoir ce qui coute le moins et de ce que j'ai pu tester, c'est NDO !

Envoyé par Baruch

Tu penses quoi des 2 algos par permutations que j'ai évoqués plus haut ?

On a vu qu'on arrive à de très bonnes performances par ces approches.
Mais pour trouver un algo exact, il faut être sûr de passer par toutes les listes optimales 2 à 2... et jusque là je ne vois pas bien comment faire avec une approche par permutations ??

Ordre de construction de mines

Algorithmes et structures de données

Discussions similaires

Partager

Partager