Discussion :

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

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

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.

[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 , si tu ne veux pas m'aider , rien ne t'y oblige Ok ? . je te remercie quand même pour ton aide

[screetch]

je répète la question: combien de temps ca prend pour un calcul?

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

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

[white_tentacle]

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

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

[white_tentacle]

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

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

[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

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