Discussion :

[Alikendarfen]

Désolé je n'arrive pas à comprendre l'algorithme que tu proposes... Tu peux être plus clair s'il-te-plaît ?

Tu parles du post #258 ?

L'idée générale est d'éliminer au plus vite une "fausse piste" (un chemin qui ne serait pas le meilleur parmi les chemins explorés).

Imaginons que notre hypothèse courante soit un chemin E avec une production p. Il y a n mines restantes.
On se demande si M0 (une des mines restantes) peut compléter E pour donner E' = E + [M0].

E' est un candidat à garder s'il n'existe pas une autre suite de mines [Mi] (parmi celles restant à placer) donnant E'bis = E + [Mi] et telle que :
- date fin de E'bis < date fin de E'
- cout de E'bis > cout de E'
- production de E'bis > production de E'

Si E'bis vérifiant ces conditions existe, alors E' n'est pas la meilleure solution.

L'intérêt (du moins j'imagine) c'est qu'on s'arrête de chercher la suite de [Mi] dès que date fin de E'bis dépasse celle de E'.
... ce qui pourrait permettre d'éliminer "rapidement" certaines hypothèses.

Reste qu'il faut voir :
- Dans quel ordre prendre les mines M0 pour que ce soit efficace
- Vérifier si les 3 conditions ci-dessus sont les bonnes ou bien si elles peuvent être améliorées

Qu'en penses tu ?

[Alikendarfen]

Voici un nouvel algo exact (... vous me direz... ) :

Son intérêt est qu'il élague un grand nombre de possibilités. A titre d'exemple, en comparaison de NDO (naïf avec dominance et optimalité 2 à 2), sur 75 mines du jeu d'essai d'elentarion :
- NDO : 29 secondes et 3 245 771 chemins étudiés
- Cet algo : 2,2 secondes et 63 681 chemins étudiés

C'est une sorte de Dijkstra (on en avait parlé lors des tous premiers posts !) qui utilise le principe décrit dans les derniers posts :

Parmi les chemins actuellement en cours d'évaluation, un chemin C1 peut être éliminé s'il existe un autre chemin C2 tel que :
- date fin de C1 >= date fin de C2
- et cout de C1 < cout de C2
- et production de C1 < production de C2
Soit : C1 termine plus tard, a permis de consommer moins et produit moins que C2.

Voici la fonction principale de l'algo. Elle prend en paramètre un chemin vide de production p :

Code C# :

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
 
    Chemin Traiter( Chemin cheminInitial )
    {
        // Le plus court est le chemin initial (vide et de production p)
        Chemin plusCourt = cheminInitial;
 
        // On constitue la liste des chemins actifs
        List<Chemin> chemins = new List<Chemin>();
        // Au départ, un seul chemin
        chemins.Add( plusCourt );
 
        // Tant que le plus court a des mines à traiter
        while ( plusCourt.MinesNonTraitees.Count > 0 )
        {
            // Retrait de ce chemin de la liste des chemins actifs
            chemins.Remove( plusCourt );
 
            // Elimination des plus mauvais chemins (répondant aux critères)
            chemins.RemoveAll( c => c.Cout < plusCourt.Cout && c.Production < plusCourt.Production );
 
            // Puis développement du plus court chemin sur les mines non encore traitées
            foreach ( Mine nonTraitee in plusCourt.MinesNonTraitees )
            {
                // Vérification de l'optimalité 2 à 2
                if ( VerifierOptimales2a2( plusCourt, nonTraitee ) )
                {
                    // Constitution d'un nouveau chemin avec la nouvelle mine
                    Chemin nouveauChemin = plusCourt.CreateCopy();
 
                    nouveauChemin.AjouterMine( nonTraitee );
 
                    // Ajout du nouveau chemin aux chemins actifs
                    chemins.Add( nouveauChemin );
                }
            }
 
            // Recherche du plus court chemin suivant
            plusCourt = null;
            foreach ( Chemin chemin in chemins )
                if ( plusCourt == null || chemin.DateFin < plusCourt.DateFin )
                    plusCourt = chemin;
        }
 
        return plusCourt;
    }

Note :
- l'algo utilise les dominances absolues (ça fait partie du code de la classe Chemin que j'ai donné plusieurs fois précédemment)
- il utilise également l'optimalité 2 à 2

[Baruch]

Yiha !

Désolé de pas avoir répondu avant, j'avais encore du mal à cerner ce que tu voulais faire ^^

Si cet algo est exact, c'est vraiment une bonne avancée

J'avais aussi réfléchi à un truc comme le dijkstra, mais j'avais conclu que ce n'était pas applicable au problème -__-.

En ce qui concerne l'exactitude je m'y penche tout de suite !

T'as fait des tests pour rechercher des cas inexacts ?

[Alikendarfen]

Content que ça te plaise !!

Oui j'ai fait des tests : 500 000 tirages de 10 mines vs. l'algo NDO et aucune différence.

... concernant la preuve pour l'exactitude, je te laisse voir. Mais la condition utilisée semble assez logique, mais peut être est-elle améliorable ?

[Baruch]

Ok !

Bon la preuve ne me paraît pas évidente...

Ta propriété est une relation de dominance sur l'ensemble des chemins.

c1 domine c2 ssi :

- c(c1) >= c(c2)
- p(c1) >= p(c2)
- t(c1) <= t(c2)

On a des inégalités larges puisque tout est continu blablabla (il me semble).

Je pose les bases de démo :

On a E un ensemble de n mines, p0 dans R+*

c1 et c2 sont des chemins de mines de E.

On pose L1 = c1 @ c1' et L2 = c2 @ c2',

où c1' et c2' sont les chemins idéaux de l'ensemble des mines restant.

Montrer que si c1 domine c2, alors L1 est meilleure que L2,

ie t(c1) + t(c1') <= t(c2) + t(c2')



Je sais que c'est pas facile, mais est-ce-que tu pourrais tester le tri naïf avec la dominance des chemins, mais sans la dominance des mines, et sans l'optimalité 2 à 2 ?

Car on ne sait pas si cette dominance marche uniquement avec ces autres conditions, et dans un tel cas toute démonstration issu de ce que j'ai écrit plus haut serait fausse.


Tiens, tu pourrais essayer de modifier cet algo NDO++ en remplaçant l'optimalité 2 à 2 par une optimalité 3 à 3 ?

Peut-être que ça peut marcher... (même si c'était moins bien pour le NDO classique)

Je continue à chercher la démo.

[Alikendarfen]

On a des inégalités larges puisque tout est continu blablabla (il me semble).

... sans doute oui, mais j'ai gardé des inégalités larges pour le moment.

Je sais que c'est pas facile, mais est-ce-que tu pourrais tester le tri naïf avec la dominance des chemins, mais sans la dominance des mines, et sans l'optimalité 2 à 2 ?

Car on ne sait pas si cette dominance marche uniquement avec ces autres conditions, et dans un tel cas toute démonstration issu de ce que j'ai écrit plus haut serait fausse.

OK, je vois l'idée. Mais à mon avis l'utilisation de la dominance et de l'optimalité ne sont là que pour optimiser la recherche (éliminer les chemins qui seraient de toutes façon non optimaux). Donc pas d'impact sur cette démo... ?
Mais ok pour faire un test.

Tiens, tu pourrais essayer de modifier cet algo NDO++ en remplaçant l'optimalité 2 à 2 par une optimalité 3 à 3 ?

Peut-être que ça peut marcher... (même si c'était moins bien pour le NDO classique)

Là, par contre, c'est plus compliqué car l'optimalité 3 à 3 et les dominances ne marchent pas très bien ensemble : tester l'optimalité 3 à 3 nécessite de "libérer" des mines dominées en cours de route (localement pour le test 3 à 3)... et ça n'est pas le cas deux à deux... donc tout l'algo est assez différent !

[Baruch]

OK, je vois l'idée. Mais à mon avis l'utilisation de la dominance et de l'optimalité ne sont là que pour optimiser la recherche (éliminer les chemins qui seraient de toutes façon non optimaux). Donc pas d'impact sur cette démo... ?

Oui mais bon on ne sait jamais, et puis ça m'éviterait de partir sur une mauvaise piste ^^

Là, par contre, c'est plus compliqué car l'optimalité 3 à 3 et les dominances ne marchent pas très bien ensemble : tester l'optimalité 3 à 3 nécessite de "libérer" des mines dominées en cours de route (localement pour le test 3 à 3)... et ça n'est pas le cas deux à deux... donc tout l'algo est assez différent !

Ca dépend de comment tu as implémenté l'algorithme non ? Enfin je croyais que ce serait simple à modifier, pardon ^^



Pour la démo, je suis toujours plus ou moins bloqué -__-.

Je suis coincé sur ce cas-ci :

E = {A,B,C,D}
c1 = [A,B] ; c2 = [C,D]

On suppose que le chemin idéal fils de c1 est [A,B,C,D].
Montrer que si c1 domine c2, alors [A,B,C,D] est nécessairement meilleur que [C,D,A,B] et que [C,D,B,A].


(pour l'instant tout ce que j'ai réussi à démontrer, c'est pour les ensembles de 2 ou 3 mines xD)

[Alikendarfen]

J'ai fait le test en n'exploitant plus la dominance ou l'optimalité 2 à 2 : sur un million de tirages de 5 mines, pas d'écart avec NDO.

Pour la démo, peut être faut-il la prendre par la fin ?

[Baruch]

Ah ok merci pour le test !

Pour la démo, peut être faut-il la prendre par la fin ?

Hmm c'est-à-dire ?

Ce que j'essaye de faire, c'est de prendre des cas simples (comme 4 mines au-dessus), pour comprendre le mécanisme... Et j'ai toujours pas compris xD

[Alikendarfen]

Tiens, tu pourrais essayer de modifier cet algo NDO++ en remplaçant l'optimalité 2 à 2 par une optimalité 3 à 3 ?

En fait, je ne vois pas le but... l'optimalité 3 à 3 est obtenue par celle 2 à 2, mécaniquement !
Quel algo tu as en tête ?

[Baruch]

En fait, je ne vois pas le but... l'optimalité 3 à 3 est obtenue par celle 2 à 2, mécaniquement !

Non !

Une liste optimale 3 à 3 est optimale 2 à 2, mais la réciproque est fausse.

Ce qui fait qu'il y a moins de chemins optimaux 3 à 3 que de chemins optimaux 2 à 2. Donc comme le NDO classique passe par tous les chemins optimaux 2 à 2 (qui en plus respectent les dominances), se limiter aux chemins optimaux 3 à 3 réduit les explorations. Mais, pour générer des chemins optimaux 3 à 3, il faut constamment trier des listes de 3 éléments, ce qui prend plus de temps que trier des listes de 2 éléments (en plus dans le NDO, on passe non pas par un tri, mais par une formule). Donc à voir si au final on y gagne ou pas.

J'avais fait un test dans le NDO classique, et il me semble que c'était moins efficace.

A titre indicatif, il y a au maximum 3 fois plus de listes idéales 2 à 2 que de listes idéales 3 à 3.

[Alikendarfen]

Non !

Une liste optimale 3 à 3 est optimale 2 à 2, mais la réciproque est fausse.

Ce qui fait qu'il y a moins de chemins optimaux 3 à 3 que de chemins optimaux 2 à 2. Donc comme le NDO classique passe par tous les chemins optimaux 2 à 2 (qui en plus respectent les dominances), se limiter aux chemins optimaux 3 à 3 réduit les explorations. Mais, pour générer des chemins optimaux 3 à 3, il faut constamment trier des listes de 3 éléments, ce qui prend plus de temps que trier des listes de 2 éléments (en plus dans le NDO, on passe non pas par un tri, mais par une formule). Donc à voir si au final on y gagne ou pas.

J'avais fait un test dans le NDO classique, et il me semble que c'était moins efficace.

A titre indicatif, il y a au maximum 3 fois plus de listes idéales 2 à 2 que de listes idéales 3 à 3.

Ah... idéales... pas optimales. Donc ok ça peut le faire.

[Alikendarfen]

En fait, oui et non... l'algo écarte tout seul les listes qui ne seraient pas idéales 3 à 3... et en passant par une élimination préalable des chemins non optimaux 2 à 2.

Donc pas de gain !

Je m'explique un peu plus "écarte les listes qui ne seraient pas idéales 3 à 3" :
Si n chemins terminant par les mêmes 3 mines sont encore en compétition, alors un seul est préservé car l'un d'entre eux termine avant, tout en ayant même cout et production totales.

De plus, si la relation "t1 < t2 et c1 >= c2 et p1 >= p2" fonctionne, prendre les mines par 3 nous prive des éliminations qui pourraient être engendrées par une ou deux mines.

[Baruch]

Ah... idéales... pas optimales. Donc ok ça peut le faire.

Hmm c'est quoi pour toi la différence ? :o

En fait, oui et non... l'algo écarte tout seul les listes qui ne seraient pas idéales 3 à 3... et en passant par une élimination préalable des chemins non optimaux 2 à 2.

Donc pas de gain !

Je m'explique un peu plus "écarte les listes qui ne seraient pas idéales 3 à 3" :
Si n chemins terminant par les mêmes 3 mines sont encore en compétition, alors un seul est préservé car l'un d'entre eux termine avant, tout en ayant même cout et production totales.

De plus, si la relation "t1 < t2 et c1 >= c2 et p1 >= p2" fonctionne, prendre les mines par 3 nous prive des éliminations qui pourraient être engendrées par une ou deux mines.

Hmm je crois que tu te trompes.

Si n chemins terminant par les mêmes 3 mines sont encore en compétition, alors un seul est préservé car l'un d'entre eux termine avant, tout en ayant même cout et production totales.

Ben non :

Les chemins [M1,A,B,C] et [M2,B,C,A] se terminent tous les 2 par le même ensemble de mines {A,B,C}, et ils n'ont pas le même coût ni la même production (selon M1 et M2).

De plus, si la relation "t1 < t2 et c1 >= c2 et p1 >= p2" fonctionne, prendre les mines par 3 nous prive des éliminations qui pourraient être engendrées par une ou deux mines.

Oui, tu mets le doigt sur le problème qui se pose :

Il n'y a pas vraiment de méthode simple pour vérifier si une liste qui est déjà optimale 2 à 2, est également optimale 3 à 3.
Donc on ne profite pas d'une élimination simple grâce à l'idéalité 2 à 2.

[Alikendarfen]

Hmm c'est quoi pour toi la différence ? :o

La différence tient dans le vocabulaire dont j'ai pris "l'habitude"... mais bon, pas de souci !

Ben non :

Les chemins [M1,A,B,C] et [M2,B,C,A] se terminent tous les 2 par le même ensemble de mines {A,B,C}, et ils n'ont pas le même coût ni la même production (selon M1 et M2).

Je parlais de n chemins dont le début est identique avant le choix pour les trois mines. Sinon, ces trois mines ne sont pas comparables en elles-mêmes, dans tous les cas.

Il n'y a pas vraiment de méthode simple pour vérifier si une liste qui est déjà optimale 2 à 2, est également optimale 3 à 3.
Donc on ne profite pas d'une élimination simple grâce à l'idéalité 2 à 2.

Pas d'accord :
- D'une part, parmi tous les chemins possibles pour 3 mines, le chemin optimal pour les 3 est également optimal 2 à 2 : donc cela élimine une partie des chemins dont on ne veut pas
- D'autre part, parmi tous les chemins possibles pour 3 mines et qui sont également optimaux 2 à 2, celui qui est optimal (pour les 3 mines) vérifie t < tx, c = cx et p = px par rapport aux autres non optimaux (ceux notés x)

Donc le dernier algo (type Dijkstra) garde bien les chemins optimaux 3 à 3 (n à n en fait) optimaux.

Par contre, il ne le fait pas de manière "directe", puisqu'à chaque itération un seul chemin est développé. Mais au final, cela revient au même.


Quelques chiffres, pour 150 mines (jeu d'elentarion)
- 193 233 itérations
- Taille max de la liste des chemins en compétition 6392
- 505 882 chemins intermédiaires générés
- 68 secondes

[Alikendarfen]

Quelques chiffres, pour 150 mines (jeu d'elentarion)
- 193 233 itérations
- Taille max de la liste des chemins en compétition 6392
- 505 882 chemins intermédiaires générés
- 68 secondes

On peut optimiser un peu avec quelques modif :
- Insertion dichotomique (pour le tri par dates) plutot que simple ajout (ce qui évite la recherche systématique du plus court chemin de la liste par un parcourt de toute la liste)
- Elimination lors de chaque insertion des chemins plus longs moins chers et moins productif (ce qui permet de faire cette recherche à partir de la position du nouveau chemin inséré et de réduire la taille de la liste des chemins encore en compétition)

Du coup on gagne sur les lignes indiquées par une * :
Quelques chiffres, pour 150 mines (jeu d'elentarion)
- 193 233 itérations
- * Taille max de la liste des chemins en compétition 3530
- 505 882 chemins intermédiaires générés
- * 27 secondes

[Baruch]

Mauvaise nouvelle !

La relation de dominance entre chemins est fausse (et je vais le prouver).
Néanmoins, peut-être que ton algorithme est exact (j'en parle après).

J'en ai eu marre d'essayer de démontrer cette fichue dominance, donc j'ai recherché des configurations qui étaient des contre-exemples, via un petit code. Bref, en voici une :

p0 = 1.04
A = {cout = 2.02 ; prod = 0.58}
B = {cout = 0.8 ; prod = 1.56}
C = {cout = 2.45 ; prod = 1.42}
D = {cout = 0.24 ; prod = 0.71}

On est bien dans une configuration de dominance du chemin [A;B] sur le chemin [C;D], en effet :

pA + pB = 2.14 > 2.13 = pC + pD
cA + cB = 2.82 > 2.69 = cC + cD
t(AB) = 2.436 < 2.453 = t(CD)

Je rappelle que si [A;B] domine vraiment [C;D], alors le chemin idéal issu de [A;B] est nécessairement meilleur que le chemin idéal issu de [C;D].

Or le chemin idéal issu de [A;B] est [A;B;D;C], de temps 3.141
Et le chemin idéal issu de [C;D] est [C;D;B;A], de temps 3.133

On remarque que [C;D;B;A] est meilleur que [A;B;D;C], ce qui contredit la propriété de dominance.


Je pense que ça montre clairement que cette relation n'est pas une relation de dominance (ou alors je n'ai pas compris).


Mais, ça ne prouve pas que ton algorithme est faux.

Les raisons pour lesquelles l'algorithme pourrait être exact ne sont pas la dominance entre mines, ni l'idéalité 2 à 2, puisque tu as testé l'algorithme sans ces 2 conditions.

Une raison possible est que les listes que tu accumules dans la banque des chemins corrects ont déjà des propriétés, comme par exemple le fait de ne pas être dominées par d'autres chemins (peut-être).

Une autre raison à ne pas exclure est peut-être la rareté des cas inexacts.



Pourrais-tu (je suis vraiment désolé xD) expliquer pas à pas comment marche ton algorithme (le premier, sans la dichotomie, sans la dominance des mines, sans l'optimalité 2 à 2), sur de petits exemples (3-4 mines) s'il-te-plaît ?


Edit : Il semblerait que pour les cas où la dominance ne marche pas (comme au-dessus), la liste idéale n'est jamais issue du meilleur chemin des 2. C'est-à-dire que même si [C;D] peut engendrer un meilleur chemin que [A;B], la liste idéale de l'ensemble {A;B;C;D} ne peut pas commencer par [C;D].
Si cette propriété est vérifiée, alors ça explique pourquoi ton algorithme marche.

Donc, ce n'est pas la bonne propriété que j'essaye de démontrer.

Ce n'est pas : Si c1 domine c2, alors le chemin idéal issu de c1 est meilleur que le chemin idéal issu de c2.

Mais ce serait donc plutôt : Si c1 domine c2, alors le chemin idéal ne peut pas être issu de c2.

Ce qui est différent.

[Alikendarfen]

Bon... d'un côté, je pressentais que cette relation de dominance n'était pas forcément bonne...

... de l'autre le contre exemple que tu as trouvé ne respecte pas l'optimalité 2 à 2 (AB n'est pas optimal 2 à 2), ce qui fait que l'algo ne tombe pas dans cette situation...

... donc quoi conclure ?

En fait, on peut prendre le raisonnement suivant : un (sous)chemin est équivalent à une mine unique à condition de noter les pi = p * ai. Ce (sous)chemin a alors un cout C = c1/1 + c2/(1 + a1) + ... + cn/(1 + a1 + a(n-1))
et sa date de fin est C/p

Dans ce sens, comparer 2 chemins revient à comparer 2 mines. Et on dit :
- Acquérir une mine-chemin C1 est plus court qu'acquérir une mine-chemin C2
- La production de C1 est supérieure à celle de C2
- Le cout de C1 est supérieur à celui de C2... mais pour le cout, on utilise somme de ci et non pas la formule du grand C ci-dessus...

Bref, c'était juste une remarque.

J'ai lancé des tests sur plusieurs millions d'occurrences (tirages aléatoires de 5 mines) et je n'ai trouvé aucun contre exemple. Par contre mon "algo Dijkstra adapté" utilise bien l'optimalité 2 à 2 (et les dominances globales).

Sans utiliser l'optimalité 2 à 2 et les dominances, voilà ce que ça donnerait (pour répondre à ta question) :

1- Au début : partant d'un chemin vide, développer des chemins hypothèses sur l'ensemble des mines restantes.
2- Ajouter chaque chemin généré, à la liste des chemins actifs
3- Trouver le plus court
4- Depuis le plus court éliminer tous les chemins plus long et dont le cout et la production sont inférieurs
5- Depuis le plus court, générer tous les chemins correspondant à l'ajout des mines restantes
6- Recommencer en 3

Sur un exemple : 4 mines A, B, C, D

1- Générer 4 chemins [A], [B], [C], [D]
2- Liste des chemins actifs L = { [A], [B], [C], [D] }
3- Trouver le plus court, par exemple [A]
4- Eliminer les chemins (à la première itération, c'est impossible sauf à avoir plusieurs mines de même cout)
5- Générer les chemins suivants [AB], [AC], [AD]. L = { [AB], [AC], [AD], [B], [C], [D] }
6- ....

Je ne sais pas si cela répond à ta question... et effectivement (d'instinct, mais ça n'est pas sûr !) il y a sans doute un contre exemple à aller chercher...

... à titre de comparaison, un des algos qu'on avait trouvé précédemment était faux 1 fois sur 100 000... peut être celui-ci l'est-il une fois sur plusieurs millions (voire d'avantage) ???

Il faut creuser encore !

PS : concernant la formule du grand C, j'espérais trouver une approche pour prouver la dominance de chemins, mais je n'ai pas réussi

[Alikendarfen]

Voici la trace des opérations pour les 4 mines de ton exemple :

p = 1.04
A = 2.02 / 0.58
B = 0.8 / 1.56
C = 2.45 / 1.42
D = 0.24 / 0.71

C'est l'algo sans aucune optim (pas de dominance, pas d'optimalité 2 à 2, pas d'usage de l'insertion triée).

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
50
51
52
53
54
55
 
Iteration 1
 
Chemins actifs restant : <vide>
 
Ajout de : 1,94230769230769[A/2,02/0,58]
Ajout de : 0,769230769230769[B/0,8/1,56]
Ajout de : 2,35576923076923[C/2,45/1,42]
Ajout de : 0,230769230769231[D/0,24/0,71]
 
Le plus court : 0,230769230769231[D/0,24/0,71]
 
Iteration 2
 
Chemins actifs restant :
	1,94230769230769[A/2,02/0,58]
	0,769230769230769[B/0,8/1,56]
	2,35576923076923[C/2,45/1,42]
 
Ajout de : 1,38505494505495[D/0,24/0,71][A/2,02/0,58]
Ajout de : 0,687912087912088[D/0,24/0,71][B/0,8/1,56]
Ajout de : 1,63076923076923[D/0,24/0,71][C/2,45/1,42]
 
Le plus court : 0,687912087912088[D/0,24/0,71][B/0,8/1,56]
 
Iteration 3
 
Chemins actifs restant :
	1,94230769230769[A/2,02/0,58]
	2,35576923076923[C/2,45/1,42]
	1,38505494505495[D/0,24/0,71][A/2,02/0,58]
	1,63076923076923[D/0,24/0,71][C/2,45/1,42]
 
Ajout de : 1,29818399123535[D/0,24/0,71][B/0,8/1,56][A/2,02/0,58]
Ajout de : 1,42809335679426[D/0,24/0,71][B/0,8/1,56][C/2,45/1,42]
 
Le plus court : 1,29818399123535[D/0,24/0,71][B/0,8/1,56][A/2,02/0,58]
 
Iteration 4
 
Chemins actifs restant :
	1,42809335679426[D/0,24/0,71][B/0,8/1,56][C/2,45/1,42]
 
Ajout de : 1,92800404264923[D/0,24/0,71][B/0,8/1,56][A/2,02/0,58][C/2,45/1,42]
 
Le plus court : 1,42809335679426[D/0,24/0,71][B/0,8/1,56][C/2,45/1,42]
 
Iteration 5
 
Chemins actifs restant :
	1,92800404264923[D/0,24/0,71][B/0,8/1,56][A/2,02/0,58][C/2,45/1,42]
 
Ajout de : 1,8551546675765[D/0,24/0,71][B/0,8/1,56][C/2,45/1,42][A/2,02/0,58]
 
Le plus court : 1,8551546675765[D/0,24/0,71][B/0,8/1,56][C/2,45/1,42][A/2,02/0,58]

[Alikendarfen]

Et voici la même trace pour le même algo mais avec dominance et optimalité 2 à 2 :

J'ai commenté cette trace à différents endroits.

Une précision vraie également pour le post précédent : quand c'est indiqué "chemins actifs restant", c'est ceux qui restent en compétition en plus du chemin le plus court.

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
 
Iteration 1
 
Chemins actifs restant : vide
 
// On n'a que B et D car B domine A et C
Ajout de : 0,769230769230769[B/0,8/1,56]
Ajout de : 0,230769230769231[D/0,24/0,71]
 
Le plus court : 0,230769230769231[D/0,24/0,71]
 
Iteration 2
 
Chemins actifs restant :
	0,769230769230769[B/0,8/1,56]
 
Ajout de : 0,687912087912088[D/0,24/0,71][B/0,8/1,56]
 
Le plus court : 0,687912087912088[D/0,24/0,71][B/0,8/1,56]
 
Iteration 3
 
Chemins actifs restant : vide // car DB élimine B seul
 
Ajout de : 1,29818399123535[D/0,24/0,71][B/0,8/1,56][A/2,02/0,58]
Ajout de : 1,42809335679426[D/0,24/0,71][B/0,8/1,56][C/2,45/1,42]
 
Le plus court : 1,29818399123535[D/0,24/0,71][B/0,8/1,56][A/2,02/0,58]
 
Iteration 4
 
Chemins actifs restant :
	1,42809335679426[D/0,24/0,71][B/0,8/1,56][C/2,45/1,42]
 
// Pas d'ajout car AC dans DBAC n'est pas optimal 2 à 2 
// Donc cela élimine DBA
 
// Et il ne reste plus que DBC qui devient le plus court
 
Le plus court : 1,42809335679426[D/0,24/0,71][B/0,8/1,56][C/2,45/1,42]
 
Iteration 5
 
Chemins actifs restant : vide
 
Ajout de : 1,8551546675765[D/0,24/0,71][B/0,8/1,56][C/2,45/1,42][A/2,02/0,58]
 
Le plus court : 1,8551546675765[D/0,24/0,71][B/0,8/1,56][C/2,45/1,42][A/2,02/0,58]