Plus court chemin , Arborescence , ACO

Version imprimable

08/08/2010, 11h42
momento85

Plus court chemin , Arborescence , ACO

Bonjours tout le monde
je voudrais que vous m'aidiez à me donner une idée, parce que je suis à sec :

Voila se que j'ai comme données :
-Une arborescence à 4 niveau
-chaque sommet donne 261 voisins (ou branche)

-Si on compte le nombre de chemins à parcourir de la racine à aux extrémités de l'arborescence on a 4 milliard de chemins possible : 261*261*216*261

-Pour connaître le poids d'un arcs il faut faire un gros calcule qui dépend des valeurs des sommet à l'extrémité de cet arc .

Objectif : trouver le plus court chemin ou bien une valeur approché.

Mon idée :
Vu la taille de mon arborescence , les méthodes exactes vont me prendre une éternité pour trouver une solution . J'ai pensé à utiliser le principe de l'algorithme de colonie de fourmis à la recherche du plus court chemin d'un point à un autre. Et en même temps, J'explicite au fur et à mesure la pondération, autrement c'est impossible de mémoriser ce monstre.

Mon Problème :

Je n'arrive pas à comprendre comment les fourmis choisissent un chemin en utilisant la loi de probabilité. J'explique :

A la première itération :
-Tout le réseau est vierge (les phénomones sont déposées à quantité très faibles et égales)
-La fourmi va emprunter le chemin où la visibilité est la plus grande (inversement proportionnelle à la distance entre père/fils ).
-Elle se déplace vers le meilleure voisin, "ou le poids de l'arc est le plus petit " , et elle réitère jusqu'à la fin de l'arborescence.
- arrivé à la fin, elle phénomène ce chemin

A la seconde itération :

- la fourmis aura un choix à faire ; elle trouve que l’un des chemin qui est devant elle a une grande visibilité (poids très petit), et en plus il est phéromoné -> elle va la choisir ...
etc etc , donc elle va re-parcourir le même chemin , et le phéromoner encore plus

si on suis ce raisonnement :

la solution trouvé n'est pas forcément la bonne ; vu qu'on n'a pas exploré tout le réseau. choisir à chaque fois le voisin le plus proche, ne va pas nous mener à la destination la plus proche , parfois bien au contraire .

Mon attente :
Une suggestion, ou une idée ,pour avoir la possibilité d'explorer tout le réseau , et qui va dissuader la fourmi de parcourir à chaque fois le même chemin , "tout en respectant le principe de l'algorithme ACO".

Remarque :

En réalité pour un noeud quelconque "x" , je serai amené à choisir une valeur comprise entre 45,0 et 71,1 ( 261 successeur de x ). "y"
et cette valeur là servira à déterminer le poids de l'arc "xy"
(Mais à chaque fois on doit choisir une valeur comprise entre [45.0 , 71.1] à chaque niveau )
08/08/2010, 13h23
[Hugo]

c'est plus une question d'algorithmique de c++, il me semble. Je ne suis pas sûr que ce soit le bon forum... sinon, je suis tout à fait incompétent, désolé !
08/08/2010, 14h19
Invité

Bonjour,
Ca me fait penser à l'algorithme de Dijkstra.
Par contre, il y a une différence très importante : dans votre problème il y 4 niveaux avec 261 choix possibles, alors que dans l'algorithme de Dijkstra il y a une infinité de niveaux, puisqu'on peut tourner en rond, par contre à chaque noeud, il n'y a qu'un nombre très limité de choix, habituellement moins d'une dizaine.
Je ne connais pas l'algorithme de la fourmi, pourriez-vous me dire où je peux trouver des infos.
Merci

PS Pardon si je dis une bêtise :oops:
Au niveau 3, c'est à dire l'avant dernier niveau, chaque noeud (261) comporte 261 possibilités. Parmi celles-ci il y en une qui est meilleure, donc, les 260 autres peuvent être éliminées.
Il en est de même au rang 2 si chaque élément du rang 3 a gardé l'information de la meilleure possibilité.
Autrement dit il ne faut pas commencer la recherche par le début (le somment de l'arborescence) mais par la fin, en éliminant tous ceux qui n'ont aucune chance d'être les meilleurs.
08/08/2010, 14h41
Flob90

Pour les graphes et les algorithmes il y a une livres écrit par Michel Gondran (qui a poussé un peu plus loin l'algorithme de Dijkstra) et Michel Minoux (qui a travaillé sur une autre cathégorie d'algorithmes associé aux graphes) : Graphes et Algorithmes, aux éditions R&D EDF. L'algorithme est un présenté, il fait partie des derniers algo de recherche de chemins, ces derniers algo sont inspiré du biologique (ici les fourmis, dans un autre cas le comportement des molécules avec utilisation de la constante de Boltzmann).

La différence entre Dijkstra et celui des fourmi est la notion probabiliste (celui de Dijkstra est exact, son dérivé le A* un peu moins mais toujours pas probabiliste). L'idée est que les fourmies vont marquer le chemin qu'elles empreintent, au premier elle vont tout droit, puis après elles devient légérement avec une certaines probabilité, et ainsi de suite jusqu'à converger vers le chemin le plus court. (@op: non elles ne réempruntent pas forcément le chemin car il y a une probabilité qu'elles devie, ce qui permet de prendre d'autre chemins, ce que je ne me souvient plus c'est comment modélisé les chemins noté pour que ca finisse par converger)

L'algo des fourmis permet de trouver le chemin d'un point à un autre je crois, or d'après ta structure il n'y a qu'un chemin pour aller d'un point à un autre (je suppose ton graphe sans circuit 0-absorbant). Si tu veus le chemin le plus court sur ton abre, je voit difficilement comment faire autrement que de tout tester (quoique si tes valuation ont des valeurs minimales, avec un peu de chance tu peus élager certaines branches d'un coup). La plus part des algo de recherche de chemin (à part Dijkstra) cherche le plus court d'un point à un autre, toi tu veus le plus court d'un point à une feuille (ou alors j'ai mal compris ?) tu pourrais appliquer Dijkstra mais dans ce cas là ca revient à tout tester.
09/08/2010, 14h55
momento85

réponse pour Pierre Dolez

Tu ne peux pas commencer par la fin ,parce que tu n'as aucune donnés sur les dernières feuilles de l'arbre .Le résultat de chaque sommet dépend du chemin parcouru précédemment .
09/08/2010, 15h44
Invité

Après lecture de nombreux articles ...
L'algorithme de la colonie de fourmis permet de déterminer le chemin le plus probablement meilleur entre un point et en autre.
Pour la fourmis ce sera le chemin le plus "court" entre la fourmilière et une source nouriture, pour un Lillois, ce sera le meilleur chemin entre Lille est une très jolie plage de St Tropez.
La notion de meilleure est définie par le principe que c'est le chemin que le plus de monde emprunte.
Pour un repris de justice, le chemin le meilleur en Lille et St Tropez ne sera certainement pas le même que celui de M. Toutlemonde.

Dans le cas présent, il n'y a pas UNE destination, mais autant de destinations que de trajets possibles : de la racine à chacune des feuilles.

Cet Arbre a été construit à partir de la racine.

Citation:

Le résultat de chaque sommet dépend du chemin parcouru précédemment.

Donc, l'information contenue dans chaque feuille dépend des informations contenues dans les sommets successifs conduisant à cette feuille.

Voila comment j'imagine les choses et je ne pense pas qu'il y ait beaucoup de rapport avec l'algorithme de la colonie de fourmis.
09/08/2010, 15h59
momento85

Momento85

Cycle hamiltonien ou pas, l’Algorithme fourmi est applicable ici, du moment où ont cherche le plus court chemin d’un point à un autre. Le principe même d’ACO c’est la recherche du plus court chemin de la nourriture au nid. Imaginons seulement, que nous avons plusieurs endroits ou est entreposé la nourriture, et que les fourmis vont cherche la nourriture la plus proche.

C’est juste que le principe du choix (trouver le juste compromis entre visibilité et phéromone que je n’arrive pas à comprendre) et je m’en suis aperçu quand j’ai commencé à écrire le code.
Sa parait logique de chercher un compromis ( visibilité/phéromone) ,mais il manque quelque chose que je n’arrive pas à voir dans ce principe , Pour ne pas tomber dans une solution local (voir fausse , vu que les phéromone n’auront aucun rôles) ; du moment où à chaque fois les fourmis vont suivre le premier chemin parcouru , « où la visibilité entre deux sommets et la plus grande, dans tout le chemin » , et vont phéromoner à chaque fois ce même chemin .

J’ai pensé au Random, pour faire bouger la fourmi aléatoirement. Mais dans ce cas la ,comment faire intervenir en même temps un compromis (visibilité/phéromone) ??????
09/08/2010, 16h00
screetch

pourquoi ne pas:
* calculer bêtement le premier chemin (mettons coût 8 + 24 + 72) en prenant le premier des noeuds de premier niveau, puis le premier des noeuds de deuxieme niveau, puis etc etc.
Cette approche n'est bien sure pas optimale.
tu obtiens alors la suite n1, n2, n3, n4
tu sais que n2->n3->n4 est deja de 119 (je crois...)
tu peux alors chercher a partir de n2 tous les noeuds tels que n2->n3'->n4' < 119
sachant que le plus gros pourrait être retiré dés que n3' OU n4' >= 119
en gros tu retires tous les noeuds tels que n2->n3' > 119, ca doit en éliminer un paquet

bon mettons que tu trouves n2->n3"->n4" de 37
alors tu repars de n1 et tu cherches dans n1 tous les chemins tels que
n1->m2->m3->m4 < 37
tu peux virer tous les m2 tels que m2 > 37, ce qui, pareillement, doit éliminer le plus gros.

C'est une adaptation (je crois) de l'élagage alpha beta (http://fr.wikipedia.org/wiki/%C3%89lagage_alpha-beta) : si le min d'une branche en cours est supérieur au max déjà trouvé, alors toute la sous-branche est bonne a jeter.
Vu que tu as très peu de niveau, et beaucoup d'arcs, cet algorithme est certainement le plus optimal.
09/08/2010, 17h07
screetch

pourquoi?
dans le pire des cas, oui, tu vas faire le calcul 4 milliard de fois. C'est le cas si tous les arcs ont la même valeur.
En revanche, tu n'as pas bien compris (et sans doute je ne me suis pas bien exprimé) concernant l'élagage; cela consiste en une methode de force brute jusqu'a ce que tu te rendes compte que la branche entière est moisie.

En gros:
a l'étage 0, tu calcules 261 valeurs, tu les tries
pour la première tu descends, cela te renvoie un résultat de, mettons, 127.
Puis tu passes au deuxieme arc, qui a une valeur de 68, donc tu dois descendre dedans. Nouveau chemin le plus court: 112.
puis au troisieme, qui a une valeur de 137.
137 etant deja pire que 112, tu n'as même pas besoin de continuer: apres les 3 premiers noeuds tu as déjà trouvé ton meilleur chemin (exact).

A chaque étage tu peux appliquer cet algo.

Je ne sais pas combien de calculs tu devras effectuer en vrai, c'est beaucoup moins que 4 milliards a priori mais ca dépend de la distribution de tes valeurs.

voila ce dont je parlais (avec du vilain code C/C++ cradoc)

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <stdlib.h>
#include <time.h>
 
struct Node
{
    unsigned int id;
    unsigned int cout;
};
 
static int node_compare(const void* _n1, const void* _n2)
{
    const Node* n1 = (const Node*)_n1;
    const Node* n2 = (const Node*)_n2;
    if(n1->cout < n2->cout)
    {
        return -1;
    }
    else if(n1->cout > n2->cout)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
static unsigned int numCalculs = 0;
static unsigned int srand_time = time(0);
static unsigned int calculer(unsigned int n1, unsigned int n2)
{
    /* simule le calcul du coût de n1 a n2 */
    numCalculs++;
 
    srand(n1+n2^srand_time);
    unsigned result = rand() & 0xffff;
//    std::cout << n1 << ", " << n2 << " : " << result << std::endl;
    return result;
}
 
 
// descend dans ce noeud, remplis result avec le chemin le plus avantageux
// retourne la longeur du meilleur chemin trouvé
static unsigned int descendre(unsigned int n, unsigned int profondeur, unsigned int max, Node* result)
{
    Node enfants[256];
    // pour chaque enfant, calcule le cout
    for(int i = 0; i < 256; ++i)
    {
        enfants[i].id = (n << 8) + i;
        enfants[i].cout = calculer(n, enfants[i].id);
    }
    // trie
    qsort(enfants, 256, sizeof(Node), &node_compare);
 
    // si on est au bout de la chaîne, alors forcément le meilleur chemin c'est le plus simple
    if(profondeur == 3)
    {
        result[3] = enfants[0];
        return enfants[0].cout;
    }
    else
    {
        // au mieux, on trouvera max
        unsigned int longueur = max;
        for(size_t i = 0; i < 256; ++i)
        {
            for(unsigned j = 0; j < profondeur + 1; ++j)
                std::cout << "  ";
            std::cout << i << "(" << longueur << ") {" << enfants[i].cout << "}" << std::endl;
            // si le cout de cet enfant est pire que le max deja trouvé, pas besoin de continuer
            if(enfants[i].cout >= longueur)
                break;
            // sinon, descend dans cet enfant, voit si il y a un noeud plus avantageux que celui déjà trouvé
            Node temp[4];
            unsigned int cetteLongueur = enfants[i].cout + descendre(enfants[i].id, profondeur + 1, longueur - enfants[i].cout, temp);
            if(cetteLongueur < longueur)
            {
                // on a trouvé un noeud encore meilleur, on installe ce résultat temporaire dans le final
                longueur = cetteLongueur;
                for(unsigned int p = profondeur+1; p < 4; ++p)
                {
                    result[p] = temp[p];
                }
                result[profondeur] = enfants[i];
            }
        }
        return longueur;
    }
}
 
int main(int argc, char *argv[])
{
    std::cout << "start" << std::endl;
    unsigned int longueur = (unsigned)-1;
    Node result[4];
    for(unsigned int i = 0; i < 256; ++i)
    {
        std::cout << i << std::endl;
        longueur = descendre(i, 0, longueur, result);
    }
    std::cout << "plus court chemin: " << result[0].id << "->" << result[1].id << "->" << result[2].id << "->" << result[3].id << std::endl;
    std::cout << "cout:" << result[0].cout + result[1].cout + result[2].cout + result[3].cout << std::endl;
    std::cout << "Nombre d'appels a calculer: " << numCalculs;
}

cela simule 3 étages de noeuds ayant chacun 256 fils (par simplicité).
la fonction de calcul renvoie la valeur de l'arc entre n1 et n2 en fonction de n1 et n2.

lance ce programme (et dirige le résultat vers un fichier car il est très verbeux), il affiche tout ce qu'il fait.
il affiche aussi le nombre d'appels a la fonction de calcul. je n'ai pas compris si dans ton programme il y avait 4 ou 5 étages (ca dépend si on parle de noeud ou si on parle d'arc), celui ci a 4 etages de noeuds (donc 3 étages d'arc), soit 256*256*256 possibilités = 16 millions
il effecture le calcul en moyenne 200 000 a 400 000 fois (au lieu de 16 millions).
Apres tout dépend de la répartition de tes valeurs d'arc, si elles sont trop proches alors il se peut que cet algorithme soit sous-optimal.
On voit notemment que des branches entières ne sont même pas considérées parce que leur racine est déjà plus couteuse que le meilleur chemin trouvé.

09/08/2010, 17h36
screetch

je me suis trompé en plus, mon code a bien 4 étage d'arcs :-/ (5 etages de noeuds), donc il effectue 200 a 400 000 opérations au lieu de 4 milliards.

Si j'ai bien compris, on a grosso modo la structure suivante :
Code:

1 2 3 4 5 6 7 8 Niveau 0 / \ Niv 1 Niv 1 / \ / \ Niv2 Niv2 Niv2 Niv2 / \ / \ / \ / \ N3 N3 N3 N3 N3 N3 N3 N3
Et le but est de trouver le n3 le plus proche de N1 ?

Ce n'est même pas un min/max alpha beta, c'est beaucoup plus simple. Tu calcules le coût de la première branche, ça te donne min. Ensuite, tu remontes à N2, et tu redescends sur toutes les branches. A chaque fois, tu compares le coût total avec min, et tu mets à jour min en fonction. Une fois ceci terminé, tu remontes en N1, et tu appliques la même approche descendante : la subtilité est qu'ici, tu vas t'arrêter dès que tu dépasses min, sans avoir besoin d'aller jusqu'au N3 : ceci devrait t'éliminer un certain nombre de branches. Tu fais ensuite le même chose en remontant en N0, puis redescendant sur chacun des N1...

Dans le cas le plus défavorable, tu feras tes 4 milliards de calculs. Mais avec une distribution homogène de valeurs aléatoires, tu en élimines un sacré bon paquet (calculer le temps moyen mis par l'algorithme est un exercice de probabilité intéressant :) ).

09/08/2010, 17h56
Flob90

Je suis d'accord avec Pierre, je ne voit pas comment appliquer la colonnie de fourmie ici, j'ai plus le livre que je citais en ma possesion, mais je suis presque certain que c'était d'un point à un autre.

Et pour la facon de résoudre le problème, j'aurai fait comme white_tentacle, à part si la structure est spécifique (par exemple si on savait que le plus court chemin était "au centre"), je ne voit pas d'autre moyen que de tout parcourir en élagant au maximum, le complexité pire cas est assez mauvaise (moyenne aussi je suppose), mais bon ...
09/08/2010, 17h57
screetch

bah c'est un alpha beta :-/
et c'est ce que j'explique plus haut (avec un beau dessin)
EDIT: ah non l'alpha beta a une subtilité en plus, mais ca reste le même principe que ce que j'ai ecrit plus haut
09/08/2010, 18h02
Flob90

Oui le principe est le même, et c'est ce que j'entendais en disans :

Citation:

je voit difficilement comment faire autrement que de tout tester (quoique si tes valuation ont des valeurs minimales, avec un peu de chance tu peus élager certaines branches d'un coup)

Et ca marche que sous certaines conditions. (basiquement pas de poids négatifs, c'est la signification de sans circuit 0-absorbant).
10/08/2010, 09h45
white_tentacle

Citation:

Envoyé par screetch

bah c'est un alpha beta :-/
et c'est ce que j'explique plus haut (avec un beau dessin)
EDIT: ah non l'alpha beta a une subtilité en plus, mais ca reste le même principe que ce que j'ai ecrit plus haut

Le min/max est adapté aux jeux de stratégie à deux joueurs (type dame, échec), ou il faut choisir le minimum à une étape (le coup que joue l'adversaire) et le maximum à une étape (le coup que je joue moi). Alpha et beta sont là pour éliminer rapidement des branches, sans les explorer totalement (inutile d'explorer toute la branche si je sais que mon adversaire a un coup gagnant). Ici, il n'y a pas d'adversaires, juste un trajet à minimiser.
10/08/2010, 10h04
screetch

oui je n'avais pas capté que alpha beta correspondait au min max. Je pensais juste que c'était le principe de l'élagage de branche, comme on a expliqué plus haut.
10/08/2010, 11h44
Invité

Bonjour,
J'ai un petit doute sur l'exposé réel du problème. Je le reformule.
Soit une arborescence. On appelle noeud l'extrémité d'un arc. On appelle arc la liaison entre 2 noeuds.
Un arbre est orienté donc un noeud peut avoir 0 entrées (la racine) ou une entrée (tous les autres noeuds), et 0 sorties (les feuilles) ou au moins 2 sorties (tous les autre noeuds). Les noeuds n'ont pas d'autre caractéristique que de connaitre l'arc d'entrée et les arcs de sortie.
Les arcs constituent la liaison entre 2 noeuds. Le noeud d'origine et le noeud de fin. Les information relatives aux longueurs, distances, temps, etc sont contenues dans l'arc.
Etant donné cette définition, aucun retour en arrière, aucun bouclage n'est possible. La notion de rang d'un noeud, resp d'un arc, est parfaitement définie.

Au moment de l'étude d'un arbre, toutes les informations sont connues (noeuds et arcs).
Soit un ensemble de feuilles (donc des noeuds sans sortie) dont l'origine des arcs est un même noeud. On peut établir un classement des différents arcs suivant un critère. En général, il y a un certain nombre d'arcs qui ne satisfont pas ce critère. Ces arcs peuvent alors être éliminé (élagués). Si le critère choisi est du type min ou max, il ne restera qu'un arc avec sa feuille qui satisfont à la condition (sauf le cas particulier des ex aequo)

Donc, dans ce cas qui nous intéresse, en partant des feuilles, on peut élaguer toutes les branches sauf une, à chaque niveau. Le chemin le meilleur est donc celui qui reste.
10/08/2010, 12h36
momento85

Momento85

Oui, je suis d'accord avec toi dolez ,se sont des définitions de la théorie des graphes.
Mais ton idée est valable pour des réseaux d'une taille très petite.
pour arriver à comparer toutes les feuilles de l’arborescence, il faudra faire beaucoup de calcules .

j'ai déjà essayé de faire un algorithme par la programmation dynamique,qui n'est autre que principe de Bellman , tout en faisant des élagages et supprimant les résultats inutiles , mais sans résultat, je suis resté une journée à attendre ... mais en vain
Moi je veux un résultat rapide ! et éviter les "méthodes bulldozer" :aie: .

Pourriez vous me donner une idée pour adapter l'algorithme fourmi à mon problème, j’en suis sure qu'il me manque un petit truc de rien du tout, que je n'arrive pas à voir …:aie:

Donnez moi juste une idée pour donner à une entité la notion de liberté de mouvement (Random) , et en même temps la notion compromis (phéromone / visibilité)
10/08/2010, 12h58
momento85

Momento85

en réalité pour un noeud quelconque "x" , je serai amené à choisir une valeur comprise entre 45,0 et 71,1 ( 261 successeur de x ). "y"
et cette valeur là servira à déterminer le poids de l'arc "xy"
(Mais à chaque fois on doit choisir une valeur comprise entre [45.0 , 71.1] à chaque niveau )
10/08/2010, 13h11
white_tentacle

J'ai un peu de mal à comprendre ton problème, quand même.

Quelles sont les données dont tu disposes ?

==> je doute que tu aies une liste de 4 milliards de noeuds, donc ta structure ne serait-elle pas plutôt un graphe ?
10/08/2010, 13h53
Invité

Là j'ai pas du tout compris.
Soit un noeud X et 261 fils Y. Oui - Non
1ère hypothèse
La valeur d'un arc X->Yn ( 0<n<262 ) doit être comprise entre 45.0 et 71.1 2ème hypothèse
Pour une extrémité d'arc X->Yn ( 0<n<262 ) le cumul au stade Yn doit être comprise entre 45.0 et 71.1

Quelle serait la définition d'un poids?
Pour moi, un poids Pi est tel qu'on peut écrire la relation pondérée
Relation = f(Xi,Pi) où i va de 1 à n.
Application fréquente
Somme Pondérée = Somme(Xi . Pi) / Somme(Pi)

Momento85

Nous pouvons avoir le choix entre deux structures si vous voulez , mais elles sont similaires :

1-Un graphe avec une source S , et à la fin 261 puits P

ou bien
Tout expliciter en un graphe en peigne :

2-Une arborescence , avec une racine R ,comme je l'ai expliqué au tout début .

Que ce soit la première structure de graphe ,ou bien la deuxième , c'est la même chose ,c'est juste que la première structure regroupe chaque niveau en un seul bloque de 261 valeurs

Au niveau de chaque sommet "x" nous allons choisir l'un de ses 261 successeurs "y"
et à l'aide d'une formule physique , cette valeur va déterminer le poids de l'arc (x,y) .

Code:

1
2
3
4
5
6
7
8
9
10
11
Structure 1
 
              S (42.2)         <-------- source 
        /      /          \
     45.0    45.1  ... 71.1       
       |  \   \     \ ... \ /   
     45.0    45.1  ... 71.1  <------- 71.1 par exemple est relié avec 
        |  \   \    \ ... \ /                 45.0 ,45.1 ....et 71.1
     45.0    45.1  ... 71.1
       |  \   \     \ ... \ /
     45.0    45.1  ... 71.1  <-------261 puits

Code:

1
2
3
4
5
6
7
8
9
10
La structure 2
 
                                      R (42.2) 
                                  /      /          \
                              45.0    45.1  ... 71.1                         
          /         /      /          \  /     /   /   /     \            \        \       \
     (45.0    45.1  ... 71.1)    (45.0    45.1  ... 71.1) ... (45.0    45.1  ... 71.1)      
 
 
 etc

10/08/2010, 14h39
screetch

as tu lu ce que j'ai ecrit, notemment le nombre de calculs a effectuer?
Combien de temps prend un calcul individuel?
10/08/2010, 14h43
white_tentacle

En fait, c'est pour un exercice et on te demande explicitement d'utiliser l'algorithme de colonie de fourmi, c'est bien ça ? Autant le dire tout de suite :mrgreen:

On en te fera pas ton exercice, mais par contre, on peut t'aider à comprendre le problème.
10/08/2010, 14h43
Invité

J'ai toujours pas compris.
Un arbre est un cas très particulier de graphe.
En l'occurrence, il s'agit d'un arbre (racine -> branches -> feuilles) ou d'un graphe qui n'a normalement ni racine ni feuilles ?
Un graphe définit des relations entre les noeuds qui le composent. Ces relations sont des arcs qui peuvent être suivant les cas en sens unique ou pas.

Qu'appelez-vous poids?

Vous parlez aussi de vecteur (colonne). Si j'ai bien compris, il ne s'agit pas de vecteur mais de liste.
Un vecteur est un être mathématique qui possède une origine, une longueur etc.
On peut faire différentes opération sur des vecteurs, l'addition, la multiplication etc.
L'ensemble des éléments d'une liste ne constitue pas un vecteur.
Par contre, chaque arc peut être considéré comme un vecteur à une dimension, ce qui n'est pas vraiment intéressant.
10/08/2010, 14h54
momento85

Momento85

Absolument pas monsieur white_tentacle , c'est un défi que je dois relever, et puis c'est loin d'être un simple exercice :lol: , si tu ne veux pas m'aider , rien ne t'y oblige Ok ? ;). je te remercie quand même pour ton aide :mrgreen:
10/08/2010, 14h59
screetch

je répète la question: combien de temps ca prend pour un calcul?
10/08/2010, 15h20
screetch

43 opérations de quel genre? additions/multiplications?
le code posté un peu plus haut simule exactement ton problème. Chaque noeud ayant 255 fils, une fonction est appelée avec le noeud "père" et le noeud "enfant" et calcule le poids de l'arc en fonction des noeuds. Il y a 4 étage comme toi.
Le nombre d'appels a la fonction de poids est d'environ 500000 au lieu de 4 milliards, et le calcul s'effectue en moins d'une seconde. Si tu veux mieux que ca, la, je ne comprends pas.
10/08/2010, 15h20
Invité

@memento85
Si vous voulez qu'on vous aide, la moindre des choses est que vous répondiez aux questions qu'on vous pose. Nous, on essaye de comprendre ce qui vous tracasse ;)
Par exemple, l'intitulé du défi nous aiderait bien.

PS Vous savez, si vous modifiez (sauf faute d'orthographe) des post précédents, en particulier les premiers, nous, pauvres lecteurs pas très intelligents, on risque d'être perdus, d'autant que, dès le départ, on a posé des questions auxquelles vous n'avez pas répondu.

S'il y a des choses confidentielles et que vous ne pouvez pas donner certains détails, malgré toute notre bonne volonté, il est probable qu'on ne pourra pas vous aider.

Autre chose, le fait qu'il y ait 43 opérations pour déterminer la longueur d'un arc, ce que vous appelez un poids, m'interpelle un peu. 43 opérations sous-entend, en gros, 42 opérandes. D'où viennent-ils? La représentation en arbre est-elle celle qui convient. Au commencement du calcul, que contiennent les arcs. Beaucoup de questions, mais on fait de notre mieux. :oops:
10/08/2010, 16h34
white_tentacle

Citation:

Envoyé par momento85

Absolument pas monsieur white_tentacle , c'est un défi que je dois relever, et puis c'est loin d'être un simple exercice :lol: , si tu ne veux pas m'aider , rien ne t'y oblige Ok ? ;). je te remercie quand même pour ton aide :mrgreen:

Tu as mal compris ce que je voulais dire. Je n'ai aucun problème à aider les gens à faire leurs exercices, du moment qu'ils comprennent ce qu'ils ont fait (différence entre donner un poisson et apprendre à pêcher ;) ).

Ce qui m'interpelle ici, c'est pourquoi tu tiens absolument à utiliser l'algorithme de colonie de fourmi, alors que celui suggéré par screetch (parcours avec élagage de branche) semble largement aussi adapté, au moins en première approche.

Et s'il s'agit simplement de code un colonie de fourmi, je ne comprends pas ce que viennent faire tes histoires de calcul compliqué sur le poids de l'arc (dont je n'ai toujours pas compris si c'est un graphe avec 1 point de départ, 261 point d'arrivée et 4 étages successifs reliés à chacun des noeuds de l'étage suivant ou un vrai arbre avec 4G feuilles à la fin).
10/08/2010, 16h41
white_tentacle

Citation:

Envoyé par screetch

43 opérations de quel genre? additions/multiplications?
le code posté un peu plus haut simule exactement ton problème. Chaque noeud ayant 255 fils, une fonction est appelée avec le noeud "père" et le noeud "enfant" et calcule le poids de l'arc en fonction des noeuds. Il y a 4 étage comme toi.
Le nombre d'appels a la fonction de poids est d'environ 500000 au lieu de 4 milliards, et le calcul s'effectue en moins d'une seconde. Si tu veux mieux que ca, la, je ne comprends pas.

Une remarque quand même : dans ton test, l'écart entre Pmax et Pmin est un rapport de 1 à 65000.

Ici on n'a même pas un rapport de 1 à 2.

Ca change peut-être suffisamment la donne pour que l'élagage ne soit plus du tout efficace, en fait (à vérifier, mais trivialement tu peux montrer que le chemin théorique minimal (180) n'élague au mieux que le dernier niveau de branche, pas sur toutes les branches). Cela dit, je suis dubitatif aussi sur l'histoire de la colonie de fourmi. S'il y a 4G arcs, ça sera tout aussi inefficace (colonie de fourmi est efficace pour gérer de nombreux chemins, pas de nombreux arcs).
10/08/2010, 16h47
screetch

c'est l'écart entre les noeuds ici qui est faible. Mais on ne sait toujours rien de cette fonction de distance, qui pourrait renvoyer une valeur entre 1 et 4 milliards.
Effectivement, cette methode marche bien a condition que l'on puisse avoir une fonction de distance telle que la somme des distances entre 4 arcs peut être (et même j'espère statistiquement assez souvent) supérieure a la distance entre 2 arcs.
Si chaque distance est entre 10 et 20 par exemple, ca ne marchera pas car la distance totale minimale (40) va toujours être supérieure a la distance entre deux arcs (20 max) ce qui va forcer a descendre dans de nombreux fils.
plus d'info sur la fonction de distance donc...
10/08/2010, 16h51
screetch

nouvelle question:
le poids entre 45,5 et 57,1 par exemple, dépend il de ce que l'on a vu avant?

par exemple: prenons le chemin
51,2->45,5->57,1->68,3
le poids est il le même que
64,1->45,5->57,1->55,0
??
de même, est ce que le poids dépend de l'endroit dans la branche?
51,2->68,3->45,5->57,1
64,1->45,5->57,1->55,0
10/08/2010, 16h54
screetch

Citation:

Envoyé par screetch

c'est l'écart entre les noeuds ici qui est faible. Mais on ne sait toujours rien de cette fonction de distance, qui pourrait renvoyer une valeur entre 1 et 4 milliards.
Effectivement, cette methode marche bien a condition que l'on puisse avoir une fonction de distance telle que la somme des distances entre 4 arcs peut être (et même j'espère statistiquement assez souvent) supérieure a la distance entre 2 arcs.
Si chaque distance est entre 10 et 20 par exemple, ca ne marchera pas car la distance totale minimale (40) va toujours être supérieure a la distance entre deux arcs (20 max) ce qui va forcer a descendre dans de nombreux fils.
plus d'info sur la fonction de distance donc...

je viens de penser: si la distance est entre 10 et 20 a coup sûr, une grosse optimisation est de retirer 10 a la distance, afin de retirer le poids "constant" de cette distance.
par exemple, plus haut, si l'on retire 10 a la distance qui est entre 10 et 20, on se retrouve avec une distance entre 0 et 10.
En trouvant un chemin de 41, et en retirant la partie constante, on se retrouve avec un chemin de cout 1
on peut élaguer tous les fils dont le cout (apres elagage de la constante) sont de 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, soit un gros élagage.