Plus court chemin , Arborescence , ACO

Version imprimable

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

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 )

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