Discussion :

[momento85]

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 )

[[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é !

[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
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.

[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.

[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) ??????

[momento85]

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 .

[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.

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.

[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.

[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 )

[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 ?

[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 :

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

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 :

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

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

[screetch]

as tu lu ce que j'ai ecrit, notemment le nombre de calculs a effectuer?
Combien de temps prend un calcul individuel?

[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

On en te fera pas ton exercice, mais par contre, on peut t'aider à comprendre le problème.

[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.

[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)