Ordre de construction de mines

Version imprimable

Voir 40 message(s) de cette discussion en une page

01/06/2011, 12h37
Baruch

Oué dsl il est un peu long xD (mais t'avais soulevé beaucoup de questions aussi ^^)

En tout cas je pense que mon code est bien. En fait il n'y a même pas besoin d'utiliser une table de hachage, puisque les vecteurs représentants l'ensemble des mines d'une liste sont toujours ordonnés. En effet, on part de la liste 12345 et on retire petit à petit des éléments pour construire les éléments de L, donc tous ces éléments sont ordonnés (si on retire un élément à une liste ordonnée, elle reste ordonnée)

Et au fait, moi je trouve une complexité de n*2^n pour l'algo par combinaisons
01/06/2011, 13h28
Alikendarfen

Citation:

Et au fait, moi je trouve une complexité de n*2^n pour l'algo par combinaisons

Oui exact : n * 2^(n-1) pour être précis 8O

Je n'ai pas encore tout relu : j'aurai le temps en fin de journée.

En fin de journée aussi, j'essaye d'envoyer un peu de code (C#, à lire c'est presque comme java : je ne sais pas si tu connais ?). Ca pourra permettre de fixer les idées, pour le moins...

Alors, j'ai quelques bouts de programme à te communiquer.

Quelques résultats d'abord : pour 18 mines 8 itérations générant le résultat à la 9ième.

Ci-dessous le nombre de chemins gardés comme candidats à l'issue de chaque itération :
1 / 153
2 / 3060
3 / 18564
4 / 43758
5 / 43758
6 / 18564
7 / 3060
8 / 153

... on est en 2^(n-1)

En termes de perf, ça tourne en env. 40s pour 18 villes (c'est pour donner une idée).

Et au total, on examine environ 5 millions de chemins intermédiaires (les chemins calculés avant d'être éliminés).

Pour le code (C#), voici déjà quelques petits bouts : les objets de base qui sont manipulés. Après je donnerai l'algo proprement dit et ensuite des critiques de l'algo (car il engendre, je crois, quelques limitations pour être amélioré).

Une mine :
Code:

1 2 3 4 5 6 7 8 9 class Mine { public string Nom { get; set; } public double Cout { get; set; } public double Production { get; set; } public BitVector.Position Position { get; set; } }
Une mine datée : c'est à dire la mine avec sa date d'achat quand elle est dans un chemin
Code:

1 2 3 4 5 6 class MineDatee { public Mine Mine { get; set; } public double Date { get; set; } }
Un chemin :
Code:

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 class Chemin { public List<Mine> MinesNonTraitees = new List<Mine>(); public List<MineDatee> MinesDatees = new List<MineDatee>(); public double Production; public double DateFin; public BitVector Positions; public Chemin CreateCopy() { Chemin copy = new Chemin(); copy.MinesNonTraitees.AddRange( MinesNonTraitees ); copy.MinesDatees.AddRange( MinesDatees ); copy.Production = Production; copy.DateFin = DateFin; copy.Positions = new BitVector( Positions ); return copy; } public void AjouterMine( Mine mine ) { MinesNonTraitees.Remove( mine ); DateFin += mine.Cout / Production; Production += mine.Production; if ( Positions != null ) Positions[mine.Position] = true; MinesDatees.Add( new MineDatee() { Mine = mine, Date = DateFin } ); } }
Concernant les histoires d'identification des chemins ayant les mêmes mines, j'utilise une classe BitVector que j'ai créée sur la base d'un BitVector32 de la bib DotNet.
A la limite, c'est un détail : je donnerai le code si quelqu'un le demande.

Maintenant, l'algo proprement dit.

Il s'agit, pour rappel, de celui qui combine nos deux approches (cf. posts précédents).

C'est un peu long, désolé.

"Normalement" (et avec de très gros guillemets... 8-)), il n'y a "pas" de bug : j'ai testé sur quelques cas cet algo vis à vis d'un algo qui traite toutes les combinaisons sans optim (mais pour des cas ayant moins de mines...). Et les deux donnent les mêmes résultats.

L'algo principal (commenté) :

Code:

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
        public void Traiter( List<Mine> mines, double p )
        {
            // Création du chemin initial vide mais comprenant la liste des mines d'origine
            Chemin cheminInitial = new Chemin();
 
            cheminInitial.Production = p;
            cheminInitial.MinesNonTraitees.AddRange( mines );
            cheminInitial.Positions = new BitVector( mines.Count );
 
            // Initialisation pour la détection des chemins ayant les mêmes mines
            int i = 0;
            foreach ( Mine mine in mines )
            {
                mine.Position = cheminInitial.Positions.CreatePosition( i );
                i++;
            }
 
            // Liste pour les résultats finaux
            List<Chemin> resultats = new List<Chemin>();
            // Liste pour les chemins calculés en intermédiaire
            List<Chemin> chemins = new List<Chemin>() { cheminInitial };
 
            // Tant qu'on a des chemins à traiter
            while ( chemins.Count > 0 )
            {
                // On va calculer des nouveaux chemins et les mettre dans cette liste
                List<Chemin> nouveauxChemins = new List<Chemin>();
 
                foreach ( Chemin chemin in chemins )
                {
                    // S'il ne reste qu'une mine à placer
                    if ( chemin.MinesNonTraitees.Count == 1 )
                    {
                        Chemin nouveauChemin = chemin.CreateCopy();
                        nouveauChemin.AjouterMine( chemin.MinesNonTraitees[0] );
 
                        // Ajout à la liste des nouveaux chemins
                        nouveauxChemins.Add( nouveauChemin );
                    }
                    else
                    {
                        // Sinon, pour chaque couple parmi les mines non traitées
                        foreach ( Tuple<Mine, Mine> couple in chemin.MinesNonTraitees.Paires() )
                        {
                            // Calcul de la meilleure combinaison entre AB et BA pour ce couple 
                            Tuple<Mine, Mine> meilleur = MeilleurCouple( chemin, couple );
 
                            // Création du nouveau chemin avec ses deux nouvelles mines
                            Chemin nouveauChemin = chemin.CreateCopy();
                            nouveauChemin.AjouterMine( meilleur.Item1 );
                            nouveauChemin.AjouterMine( meilleur.Item2 );
 
                            // Ajout à la liste des nouveaux chemins
                            nouveauxChemins.Add( nouveauChemin );
                        }
                    }
                }
 
                // Les anciens chemins peuvent être oubliés
                chemins.Clear();
 
                // Ici on va stocker en vis à vis de chaque clé une liste de chemins ayant les mêmes mines
                Dictionary<BitVector, List<Chemin>> combinaisons = new Dictionary<BitVector, List<Chemin>>();
 
                // On place chaque nouveau chemin en vis à vis de sa clé (appelée 'Positions')
                foreach ( Chemin nouveauChemin in nouveauxChemins )
                {
                    List<Chemin> combinaison;
                    if ( combinaisons.TryGetValue( nouveauChemin.Positions, out combinaison ) == false )
                    {
                        combinaison = new List<Chemin>();
                        combinaisons.Add( nouveauChemin.Positions, combinaison );
                    }
                    combinaison.Add( nouveauChemin );
                }
 
                // Puis on reprend chacune des listes de chemins ayant les mêmes mines
                foreach ( List<Chemin> combinaison in combinaisons.Values )
                {
                    // On calcule le meilleur d'entre eux
                    Chemin meilleurChemin = MeilleurChemin( combinaison );
 
                    // Si ce chemin contient toutes les mines : c'est un résultat.
                    // Sinon il faut poursuivre
                    if ( meilleurChemin.MinesNonTraitees.Count == 0 )
                        resultats.Add( meilleurChemin );
                    else
                        chemins.Add( meilleurChemin );
                }
            }
        }

Calcul du meilleur ordre pour un couple et partant d'un chemin :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
        Tuple<Mine, Mine> MeilleurCouple( Chemin chemin, Tuple<Mine, Mine> couple )
        {
            Mine mine1 = couple.Item1;
            Mine mine2 = couple.Item2;
 
            double d1 = (mine1.Cout / chemin.Production) + (mine2.Cout / (chemin.Production + mine1.Production));
            double d2 = (mine2.Cout / chemin.Production) + (mine1.Cout / (chemin.Production + mine2.Production));
 
            if ( d1 > d2 )
                return new Tuple<Mine, Mine>( mine2, mine1 );
            else
                return new Tuple<Mine, Mine>( mine1, mine2 );
        }

Calcul du meilleur chemin parmi un ensemble (on prend arbitrairement l'un des meilleurs chemins, sans traiter les égalités entre chemins)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
        Chemin MeilleurChemin( List<Chemin> chemins )
        {
            double d = double.MaxValue;
            Chemin meilleur = null;
 
            foreach ( Chemin chemin in chemins )
            {
                if ( chemin.DateFin < d )
                {
                    meilleur = chemin;
                    d = chemin.DateFin;
                }
            }
 
            return meilleur;
        }

... bon reste qu'avec ça, on va plafonner à 20 mines grosso modo.

Quelques critiques de l'algo à suivre

01/06/2011, 19h37
Alikendarfen

Donc, cet algo semble être ce qu'on a trouvé de mieux (mais peut être que l'approche par algo génétiques que proposait prgasp77 au tout début serait meilleure... ? ... il faudra qu'on y revienne pour voir d'autant que j'ai qq questions, mais bon, c'est une autre histoire).

Cela dit, il n'est pas super :
- Avant, on plafonnait à env. 12 mines (cf. ce que disait Vakhyw)
- Maintenant on arrive à 18
Mais c'est pas la gloire !

Mais surtout voici les critiques sur sa structure :

1- L'algo nécessite qu'on explore les possibilités par nombre de mines placées

Ca, c'est parce qu'il faut, à chaque fois réunir tous les chemins ayant les mêmes mines.

2-Du coup, une approche de type Dijkstra-like (pour optimiser) me semble impossible

3-Par contre, on doit certainement pouvoir y intégrer la notion de dominance... le seul "problème" est que l'algo tel quel mise que tous les chemins en cours d'éval ont la même taille (sinon aucun sens d'analyser les combinaisons)

Pour les dominances, on a vu qu'il y en avait de deux sortes :
- Celles qui sont absolues, non relatives à p
- Celles qui sont relatives à p

Les dominances absolues permettent de ne commencer l'algo que par les mines dominantes et de n'intégrer les mines dominées qu'une fois les dominantes placées. Donc ça doit pouvoir marcher, mais il faut traiter cette notion de dominance pour chaque chemin dans l'algo (pas forcément très efficace car c'est une relation d'ordre partielle : peut être faudrait il que la dominance soit l'articulation majeure, auquel cas, l'algo est à refaire).

Pour les relatives, même combat... ?

Bon... j'attends un peu vos retours.

... j'ai toujours espoir qu'on traite 100 mines un jour !! :lol:
01/06/2011, 20h04
Baruch

Euh attends je me perds un peu :

Le code que tu donnes correspond bien à l'algo par combinaisons, dont j'ai proposé un "code" ya qq posts ?

Bon moi je suis pas un programmeur (à vrai dire, je ne sais pas programmer vraiment en C, ni en java ^^).
Je résume un peu tout ce qu'on a fait depuis le début :

De l'énoncé original du problème, on a tiré des propriétés :

1) Si L1@L2 est idéale, alors L1 et L2 le sont.
2) On connaît la règle pour ordonner 2 mines connexes, en fonction de p (ou pas, dans certains cas).
3) On a essayé de démontrer une relation de dominance (peut-être dépendant de p), ça n'est pas encore vérifié

Ce qui a été réalisé :

- Sans ces propriétés, on crée l'algo naturel d'exploration de toutes les combinaisons, mais on est limité à 12 mines environ.

- Avec la propriété 1), on crée l'algo par combinaisons, qui est limité à 18 mines environ.

Les pistes de développement :

- Les dominances :

Continuer la démo de la dominance (le lien est dans un de mes posts), et voir où ça mène : à rien, ou à une relation de dominance, ou à une relation de dominance dépendant de p (si on arrive pas à virer les p*, ça ne sert à rien).
Si on a des dominances totales (indépendantes de p), on peut déjà les utiliser dans l'algo par combinaisons : au début de chaque itération, on supprime les élément impossibles de L.
Mais au lieu de faire ça, on peut commencer par faire une étude de dominance, afin de voir si d'éventuelles coupures de l'ensemble des mines peuvent être effectuées, ce qui réduit grandement le problème. Je pense que c'est assez rare, mais assez utile pour être exploité.
On peut également, s'il n'y a pas de coupures à faire, partir de la liste des éléments ordonnés par dominance, puis trier les autres éléments par dessus avec une autre méthode.

- L'idéalité 2 à 2 :

L'algo que j'ai proposé n'étant pas très efficace, je pense que cette voie n'est pas prioritaire. Les idées relatives à cette méthode sont :
On a une formule toute faite pour trouver l'ordre d'un couple de mines, ce qui permet de trier tous les couples rapidement.
Pour certains couples de mines, on montre que si ces mines sont connexes, alors leur ordre est toujours le même. Ca c'est une idée qui n'est pas négligeable je trouve.

- Dijkstra :

A voir si on peut l'appliquer on futures méthodes proposées, mais ce n'est qu'une heuristique.

- Algos génétiques

A voir (je m'y connais pas du tout).
01/06/2011, 20h18
Alikendarfen

Citation:

Le code que tu donnes correspond bien à l'algo par combinaisons, dont j'ai proposé un "code" ya qq posts ?

euh... non !!

J'ai poursuivi mon idée plutôt (relis mes posts) !

Pour être clair : je n'ai pas vu de possibilité d'implémentation efficace de ton algo (mais j'ai peut être raté un truc).

Dans tous les cas, ça n'est pas l'identification des combinaisons (ni son implémentation) qui génére la combinatoire (bien qu'on gagne en combinatoire avec cette méthode)... donc ça n'est pas le combat

Pour le reste, je suis d'accord : il faut intégrer les dominances.
Mais alors, les résultats concrets ne vont dépendre que des jeux d'essai...
01/06/2011, 20h23
Alikendarfen

Autre truc :

Quand tu dis :

Citation:

1) Si L1@L2 est idéale, alors L1 et L2 le sont.

...

- Avec la propriété 1), on crée l'algo par combinaisons, qui est limité à 18 mines environ.

ça ne me semble pas être exactement ça. L'algo utilise :

1/ Prendre le meilleur chemin parmi tous les chemins ayant les mêmes mines

2/ Traiter les mines par deux : c'est à dire directement prendre le meilleur entre E+[AB] et E+[BA] (qui est aussi une façon "locale" de traiter 1/)
01/06/2011, 20h27
Baruch

Ah bon ben on parle d'algos différents ^^ Le "code" que j'ai donné ne traite pas les mines par 2.
Et mon algo est prêt à être implémenté non ?
02/06/2011, 00h07
Alikendarfen

"Ton algo", comme tu dis... à mon sens, non il n'est pas prêt à être implémenté (la raison principale est que tu n'explicites pas assez, selon moi, le principe de réduction de la liste ordonnée des mines, ni la comparaison de ces listes une fois réduites). Dans tous les cas, c'est une version de l'algo à combinaisons que je proposais (et sans le traitement des mines 2 à 2) : donc pas d'amélioration de la complexité (on sera en 2^n, dans tous les cas).

C'est dommage que tu ne procèdes pas à une implémentation concrète de ton côté, dans le langage de ton choix (tu connais peut être un langage fonctionnel, caml ou autre ?). C'est juste qu'à un moment, ça me semble important pour se rendre compte !

Si on revient à notre affaire : comment progresser ??

De mon côté, je n'ai pas su aller plus loin dans ta démo mathématique concernant la dominance (je ne sais si tu as pu avancer de ton côté ?).

Pour la dominance, on a deux éléments (que tu considères ne pas être démontrés, mais qui semblent pourtant très logiques et, ok, la logique ne suffit pas toujours) :

- Dominance absolue : Si c1 < c2 et p1 > p2 alors M1 domine M2

- Dominance locale : Partant de E et un ensemble de Ti liés à l'ajout de Mi à E sont déterminés

- si pour 2 mines Mj Mk dans ces Mi, telles que Tj < Tk, il est possible d'acquérir Mj + Ml avant Tk et que P(Mj) + P(Ml) > P(Mk)

- alors Mj domine Mk

- sinon Mk domine Mj

(à prouver tout ça)

Il y a d'autres éléments à considérer :

1- L'algo qu'on cherche doit il être étendu à un problème à n ressources : n productions et n couts ?

2- Doit il être parallélisable (traité sur n machines ou sur n coeurs) ?

3- Quel contexte concret doit il traiter : y a-t-il des relations particulières entre les mines ou leurs (c,p) dans un domaine d'application significatif ?

...

Sur le plan concret, on peut également envisager les algo génétiques (post de prgasp77) qui répondent au moins aux points 1- et 2- ci-dessus.

Par contre, on se retrouve dans une situation comparable au voyageur de commerce : pour un gène donné, un élément ne doit figurer qu'une fois.

Du coup, la combinaison de deux gènes n'a pas de sens... et on se retrouve qu'avec des mutations dans la pratique (prgasp77 si tu as des billes là dessus, je suis preneur !).

Et a priori, ça diminue l'efficacité de ce type d'algo.

Cela dit, par le passé, j'avais eu des résultats plutôt bons jusqu'à 50 villes pour le voyageur de commerce (et ça fait quelques années déjà). Donc pourquoi pas essayer de nouveau pour le problème des mines ?

Bon, évidemment, dans ce cadre, pas de preuve ou de démonstration : on teste et on constate que ça marche (ou pas)... un peu comme dans la vie !! :roll:

A suivre... (?)
02/06/2011, 09h48
Alikendarfen

Retour sur les math...

Partant de :
-n mines à placer
-p0, la production initiale
-M1(c1,p1) et M2(c2,p2)
-P la production totale des n-2 mines restantes (donc hors p1 et p2)

L'idée est de démontrer s'il y a des conditions pour lesquelles si M1 et M2 se succèdent immédiatement, l'une de ces deux mines doit toujours être avant l'autre.

... je ne sais pas encore précisément ce qu'on pourra en tirer après ça

Voici la démo :

T(M1M2) < T(M2M1)
<=>
c1/p + c2/(p+p1) < c2/p + c1/(p+p2)

Toutes les valeurs sont réelles et strictement positives :
En effet, si ci = 0, on peut acheter Mi tout de suite.
Et si pi = 0, aucun intérêt à acheter cette mine.

On peut donc multiplier chaque membre par p * (p + p1) * (p + p2)

Ce qui au final donne (à vérifier !) :

pc1p2 + c1p1p2 > pc2p1 + c2p1p2

ou encore :

c1p2 * (p + p1) > c2p1 * (p + p2)

d'où

c1p2 / c2p1 > (p + p2) / (p + p1)

Si on dérive f(p) = (p + p2) / (p + p1) selon p, on a : f'(p) = (p1 - p2) / (p + p1)²

Donc selon p1 et p2 connus, f est soit croissante, soit décroissante.

Pour le problème qui nous occupe p appartient à I = [p0 ; P + p0]

Donc, si on détermine px tel que f(px) = c1p2 / c2p1
alors si f(p) est croissante :
- et px < p0 : M2 avant M1
- et px appartient à I : on ne peut conclure
- et px > P + p0 : M1 avant M2
(inverse si f(p) décroissante)

... bon ça faisait très longtemps que je n'avais pas fait de math :aie:: donc je ne suis pas sûr à 100% des calculs

De là ... y a-t-il quelque chose d'intéressant à en faire ?
02/06/2011, 13h23
Baruch

Pour les maths, tu veux trouver les conditions pour lesquelles 2 mines successives sont toujours dans le même ordre ? Ca je l'ai déjà fait ^^

Soit p* = (c2-c1)/(c1/p1-c2/p2)

si p<p* , alors la moins rentable est avant
si p>p* , alors la plus rentable est avant

(comprendre la rentabilité au sens p/c)

Donc pour que l'ordre de 2 mines consécutives ne varie jamais, il faut et il suffit que p*<= 0. Dans ce cas, p est toujours supérieur à p* (puisque p>0), et donc la plus rentable des 2 mines est toujours avant.
Et p*<=0 ça équivaut à dire que la mine la plus chère est aussi la moins rentable.
02/06/2011, 13h32
prgasp77
Une idée m'est passée par la tête, une autre voie d'étude serait : la topologie. « Ho noooOoOOoOOOONNNNNNNNNNNNNNNNNN ! » « Si ».

Soit U l'ensemble des ordres possibles de construction es mines. On défini la distance d de U² dans N qui est le nombre de déplacement de mines dans l'ordre de construction pour passer de l'un à l'autre.
Ainsi, soient les ordres u=[A B C D], v=[A D C B] et w=[B A C D] ; d(u,v)=2 ; d(u,w)=1 et d(v,w)=2. Je laisse le soin au lecteur de démontrer que d est effectivement une distance (trivial).

Une fois en possession d'un espace métrique, il ne nous reste plus qu'à faire quelques calculs :
- Soient u et v de U tels que d(u,v)=1. On appelle M la mine à déplacer pour passer de u à v. En fonction de M, déterminer la différence T(u) - T(v)
- Conclure que deux ordres proches ont un temps proche
- Conclure qu'une recherche par gradient (à adapter pour le cas discret) est efficace
Bien entendu, tout cela n'est que conjecture. Je peux me tromper.
02/06/2011, 14h49
Alikendarfen

@Baruch,

Citation:

donc si on note p* = (c2-c1)/(c1/p1-c2/p2)
p* ne dépend que des caractéristiques de M1 et M2, et p* est symétrique (si on échange 1 et 2, p* ne change pas).

on montre ceci :

si p<p* , alors le moins rentable est avant
si p>p* , alors le plus rentable est avant

J'ai bien vu que tu avais abordé le sujet, mais je n'ai pas compris ta démo... :(

... ni (donc) pourquoi j'ai un résultat différent (qui est dépendant de la production de toutes les mines, ce qui n'est pas le cas de ta solution) ?

Donc, si tu peux m'éclairer ?
02/06/2011, 14h58
Alikendarfen

@prgasp77,

Citation:

Bien entendu, tout cela n'est que conjecture. Je peux me tromper.

La tout de suite, j'ai un peu l'impression d'être là que pour me tromper ! :D

... d'autant que ton approche, je ne la comprends pas : tu pourrais développer un peu (ou indiquer quelques liens qui expliqueraient) ?

Et sinon :

Citation:

(à adapter pour le cas discret)

Baruch indiquait qu'on n'est pas dans un cas discret (ou alors tu ne parles pas de la même chose ?).
02/06/2011, 15h57
Baruch

Content de te revoir prgasp77 ^^

Alors pour ton idée :

J'ai pas bien compris ce que tu appelais distance :

Citation:

Ainsi, soient les ordres u=[A B C D], v=[A D C B] et w=[B A C D] ; d(u,v)=2 ; d(u,w)=1 et d(v,w)=2.

d(u,v) n'est pas le nombre de permutations à effectuer pour passer de u à v ?
Alors c'est quoi exactement ? (d(u,v) n'est-il pas égal à 1 ?)

Citation:

Soient u et v de U tels que d(u,v)=1. On appelle M la mine à déplacer pour passer de u à v. En fonction de M, déterminer la différence T(u) - T(v)
Conclure que deux ordres proches ont un temps proche
Conclure qu'une recherche par gradient (à adapter pour le cas discret) est efficace

Oui c'est intéressant tout ça. J'avais déjà un peu réfléchi à un truc dans le genre : permuter 2 mines, c'est progressivement (continûment) modifier les caractéristiques des 2 mines (p et c). Mais j'étais pas allé plus loin que ça.

Néanmoins, je sais pas si ce que je vais dire a un rapport avec ton approche, mais je le dis quand même :

Quand on cherche à obtenir un ordre idéal 2 à 2 à partir d'un ordre de départ, une méthode possible est :

On détecte tous les couples de mines consécutives qui ne sont pas dans le bon ordre (et donc qui si on les permute, le temps résultant total pour la liste est diminué), et on les permute (dans quel ordre, à déterminer).
Donc au fur et à mesure des permutations de mines consécutives, on diminue le temps total.
Mais le problème, c'est qu'il y a plusieurs solutions idéales 2 à 2.
C'est pour ça que j'ai quelques réserves sur ta méthode, mais après tout tu as à peine développé ^^.

Citation:

donc si on note p* = (c2-c1)/(c1/p1-c2/p2)
p* ne dépend que des caractéristiques de M1 et M2, et p* est symétrique (si on échange 1 et 2, p* ne change pas).

on montre ceci :

si p<p* , alors le moins rentable est avant
si p>p* , alors le plus rentable est avant

Effectivement je n'ai publié la démo (excuse moi en passant, j'ai pas pris la peine de vérifier ta démo) :

On part de T(M1M2)<T(M2M1)
<=> c1/p + c2/(p+p1) < c2/p + c1/(p+p2)
on multiplie tout par p(p+p1)(p+p2), on simplifie, on obtient :
p * (c1p2-c2p1) < p1p2(c2-c1)

si c1p2-c2p1 > 0 alors p < p1p2(c2-c1)/(c1p2-c2p1) = (c2-c1)/(c1/p1-c2/p2)
si c1p2-c2p1 < 0 alors p > (c2-c1)/(c1/p1-c2/p2)

on pose p* = (c2-c1)/(c1/p1-c2/p2)

on a alors :
T(M1M2)<T(M2M1) équivaut à

c1p2-c2p1 > 0 et p < p*
ou
c1p2-c2p1 < 0 et p > p*

De même, si on permute 1 et 2, p* étant invariant, on a :

T(M1M2)>T(M2M1) équivaut à

c1p2-c2p1 < 0 et p < p*
ou
c1p2-c2p1 > 0 et p > p*

Donc en fait,
si p<p*, alors c1p2-c2p1 > 0 et T(M1M2)<T(M2M1), ou alors c1p2-c2p1 < 0 et T(M1M2)>T(M2M1)
or c1p2-c2p1>0 <=> p1/c1<p2/c2 <=> M1 moins rentable que M2
donc on résume à : si p<p*, alors le moins rentable est avant
et de même, si p>p*, le plus rentable est avant
02/06/2011, 16h49
Alikendarfen

ok, je comprends merci Baruch.

Mais si je ne me trompe pas, cette démo considère p "juste avant" M1M2 ??

Ce que j'ai essayé de démontrer, c'est une relation valable quelle que soit le position de M1M2 parmi les n mines du problème...

Edit : C'est à dire en fonction de p0 et de P = somme(pi).

Comme je disais, je ne sais pas si on peut en tirer qq chose d'un point de vue pratique, mais ça me semble un peu différent ? (et à condition que la démo soit juste)

Par ailleurs, je partage tes questions auprès de prgasp77.
Pour le gradient, on trouve des explications un peu partout... mais ça dépasse mes compétences et je n'ai aucune idée de ce que pourrait être la fonction à minimiser en l'occurrence !
02/06/2011, 17h09
Baruch

Oui c'est bien ce que j'ai fait, enfin presque :

J'ai montré que l'ordre de 2 mines consécutives dépend de la comparaison entre p, la production juste avant ces 2 mines, et p*, une valeur intrinsèque à ces 2 mines.
si p<p*, on a l'ordre 1
si p>p*, on a l'ordre 2

Si on veut avoir toujours le même ordre, indépendamment de la position des 2 mines consécutives dans la liste, il faut que quels que soient les p rencontrés, ces p vérifient tous p<p*, ou alors p>p*.
Or les différentes valeurs de p varient entre p0, et la somme de p0 avec les productions de toutes les autres mines que les 2 considérées. Notons cette somme pmax. On a p0 <= p <= pmax.
Donc si p0>p*, on aura toujours l'ordre 2
et si pmax<p*, on aura toujours l'ordre 1

Effectivement je n'avait pas évoqué cet aspect ci, puisque j'avais considéré que p variait entre 0 et +inf.
02/06/2011, 17h24
Alikendarfen

1 pièce(s) jointe(s)

J'ai essayé de "visualiser" cette histoire de gradient et de permutation au travers d'un exemple.

Voici ce que ça donne :

P 5
Cout Production
A 2 3
B 2 4
C 6 4
D 1 1
E 7 10

Pour info, la meilleure solution est BADEC avec un temps de 1,5 et quelques.

Voici la démarche :

on part de ABCDE, puis on fait circuler A
ça donne : ABCDE, BACDE, BCADE, BCDAE, BCDEA
A chaque fois on calcule le temps du chemin.

puis on recommence pour B :
ça donne : BACDE, ABCDE, ACBDE, ACDBE, ACDEB
On calcul les temps également.

Idem pour C, D et E

A la fin, on obtient le tableau suivant (les nombres sont arrondis) :

A B C D E
1 1,62 1,60 2,06 1,63 1,96
2 1,60 1,62 1,79 1,62 1,70
3 1,69 1,79 1,62 1,61 1,54
4 1,70 1,80 1,61 1,62 1,63
5 1,73 1,86 1,53 1,63 1,62

Ce qu'on voit (j'espère que j'utilise le mot gradient à bon escient) :
- Le gradient pour A le met en seconde position
- Celui pour B en première
- Celui pour C en dernière
- Pour D et E, il y a conflit sur la position 3, par contre D est bien "campé" sur 3 alors que E "penche" vers 4 et 5 (calcul correct à trouver pour ça...)

Donc au final, on a bien BADEC... c'est possiblement un hasard mais ça mérite peut être de se pencher sur la question ? Si oui merci prgasp77 !!

PS : comme les tableaux s'alignent mal en affichage texte, je vous ai mis un xls en pj
02/06/2011, 18h15
Baruch

Et pourquoi es-tu parti de ABCDE ? Si tu pars d'un autre ordre, les résultats sont-ils les mêmes ?

Voir 40 message(s) de cette discussion en une page