Discussion :

[méphistopheles]

Bounjour.
j'ai une fonction récursive qui fait des vérifications en séries de la manière suivante:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 fonction Verify {tableau d'appel: SPC} 
si SPC complet, alors 
   ajouter SPC à la liste BONSPC(globale)
   sortir de la fonction
sinon
   chercher case incompletes(boucle)
   Boucle for jusqu'à nombre de possibilités
       remplir case incomplete par variable dans nouveau tableau STC
       regarder si la case est valable dans STC
       si oui, appeler verify {STC}
   fermer la boucle
fermer la condition

On obtiens donc un arbre de possibilité un peu comme ça:

Code :

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

1
2
3
4
5
6
7
 
   ____________________________|____________________________________
 __|____  ___|____        _|__        |         ____|___         |
 |    __|__ | __|___      |           *         |       |       *
 *   *      * |     |
 
ext (* veut dire non trouvé, aret de la procédure)

Sachant que je peut connaitre le niveau maximal de récursivité (nombre de niveau possibles de l'"arbre" (=nombre de cases vides)) mais que ce niveau n'est pas forcément atteint, j'aimerais faire une barre qui indique l'état de progression de la procédure.
j'usque-ici, j'utilisais une barre de progression logarythmique mais ce n'étais pas trés satisfaisant. (ralentit au fur et à mesure).

si vous avez une idée... Merci

[FrancisSourd]

Pour avoir une "évolution progressive", il faut avoir un moyen d'estimer la taille de ton arbre (son nombre de noeuds ou son nombre de feuille: je ne sais pas si s'est faisable pour ton problème.

Sinon, tu peux rajouter deux paramètres min et max à ta procédure récursive. Dans ta fonction récursive, tu évalues d'abord le nombre k d'appels récursif à faire (avant de les faire). Puis, pour tes k appels récursifs, tu passes les valeurs

• * 1er appel : (min, min + (max-min)/k)
  * 2e appel : (min + (max-min)/k, min + 2(max-min)/k)
  ...
  * ke appel: (min + (k-1)(max-min)/k, max)

A la racine, tu appelles la procédure avec min=0 et max=100.
A tout moment min donne une évaluation du pourcentage de l'évolution. En pratique, l'évolution sera irrégulière si l'arbre n'est pas équilibré.

[méphistopheles]

merci francis.

le problème, est que je ne connais que le k maximum de la fonction, ainsi que le nombre maximal de possibilité (disons que j'en connais la factorisation, le resultat êtant de l'ordre de 10^77 au maximum et 10^40 en général ce qui est difficilement calculable en vb).
pour ce qui est du nombre de neuds, je le connais par étage et au total(mais également en factorisation le nombre total de neuds êtant à peu pres le 5eme du nombre total de possibilités).
inutile de te dire que le nombre de neuds par étage est précisément ma factorisation du nombre maximum de possibilité.
le problème, êtant que même en supposant que je puisse évaluer le total, je ne vois pas comment calculer ce que je dois retirer au nième degré de la branche si une branchen+1 est coupée (impossible).

merci d'avance.

[FrancisSourd]

Le même problème se pose dans les calculs de type de branch-and-bound (que je connais bien): ils sont très longs et on a vraiment envie de montrer l'avancée du calcul mais il n'y a à ma connaissance pas de solution satisfaisante lorsque des coupes peuvent apparaître à de faible profondeur, ce qui déséquilibre très fortement l'arbre.

Pour calculer le k que j'ai défini dans mon post précédent, on peut modifier ton code comme ceci afin de faire un passage à vide pour évaluer k avant d'appeler la récursion:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 fonction Verify {tableau d'appel: SPC, réel: min, réel: max} 
si SPC complet, alors 
   ajouter SPC à la liste BONSPC(globale)
   sortir de la fonction
sinon
   chercher case incompletes(boucle)
   k=0
   Boucle for jusqu'à nombre de possibilités
       remplir case incomplete par variable dans nouveau tableau STC
       regarder si la case est valable dans STC
       si oui, augmenter k
       vider la case incomplete
   fermer la boucle
   i=0
   Boucle for jusqu'à nombre de possibilités
       remplir case incomplete par variable dans nouveau tableau STC
       regarder si la case est valable dans STC
       si oui
         appeler verify {STC, min + i(max-min)/k, min + (i+1)(max-min)/k}
         augmenter i
       finsi
   fermer la boucle
fermer la condition

[méphistopheles]

Désolé, mais ce n'est malheureusement pas possible, la fonction la plus longue êtant justement la vérification de la validité de la case (250 000 instructions). ce n'est donc pas ce que je recherche.

à la limite, je pourrais m'en sortir si je pouvais calculer mon nombre total, mais comment composer un nombre superieur à 10^77?

merci

[FrancisSourd]

Désolé, mais ce n'est malheureusement pas possible, la fonction la plus longue êtant justement la vérification de la validité de la case (250 000 instructions). ce n'est donc pas ce que je recherche.

Eventuellement, il serait possible de stocker les résultats de la première passe "à vide" pour éviter de la recalculer dans la seconde.

à la limite, je pourrais m'en sortir si je pouvais calculer mon nombre total, mais comment composer un nombre superieur à 10^77?

merci

C'est effectivement dur d'ajouter 1 à 10^77. Il est quand même possible d'utiliser des libraires d'entiers longs (très longs) mais je ne sais pas si c'est la meilleure solution.
Si ta structure s'y prête, tu peux peut-être décomposer le calcul, selon chaque dimension par exemple...

[méphistopheles]

Eventuellement, il serait possible de stocker les résultats de la première passe "à vide" pour éviter de la recalculer dans la seconde.

En fait , je veut dire qu'il est impossible de faire une passe "à vide" êtant donné que la procédure même consiste à trouver les "branches à éliminer" et que le stoquage dans une variable globale des solution ne prend pas de temps.
tu remarquera d'ailleurs que la procédure à vide que tu à proposé est presque aussi longue que la pleine. (à peu près, les fonctions de 100 lignes ne représentant rien face à la fonction de recherche).
en fait, je réfléchit acuellement à la deuxième solution.

C'est effectivement dur d'ajouter 1 à 10^77. Il est quand même possible d'utiliser des libraires d'entiers longs (très longs) mais je ne sais pas si c'est la meilleure solution.
Si ta structure s'y prête, tu peux peut-être décomposer le calcul, selon chaque dimension par exemple...

si tu connais ces librairies en vb, je suis preneur. sinon, j'ai réussi à trouver une procédure pour le diviser simplement, mais je garde des nombres de l'ordre de 10^20. j'essaye donc de stocker des ajouts dans des variables provisoiresmais je n'arrive pas à determiner quand elles sont asser grandes pour les ajouter.
j'ai égualement un problème pour calculer combien je dois ajouter à la progression lorsque je coupe une branche.

merci

salut

[FrancisSourd]

Désolé, je n'ai plus d'idée.
Sur le premier point, je ne vois pas le problème.
Pour le second, je ne connais pas VB. Ces librairies permettent de représenter des chiffres dans des tableaux de n octets (ou des listes a priori non bornées en taille) au lieu de simples mots ou double mots. Et elles implantent les opérateurs classiques. Si tu as uniquement besoin d'incrémenter, c'est très simple à implanter.

Pour t'aider, voici un sujet de TD
http://www.enseignement.polytechnique.fr/profs/informatique/Philippe.Chassignet/01-02/X-UPS/td_2.html

[méphistopheles]

Sur le premier point, je ne vois pas le problème.

A vrai dire, je dirais juste que je ne peut faire un passage à vide car il serais trop long et que donc le calcul du temps n'aurais aucuns interet (et le deuxième passagenon plus).

merci beaucoup, malheureusement, je dois aussi manipuler (diviser, mukltiplier, décrémenter) ce nombre donc ça va être difficile.

salut

[méphistopheles]

grace à ce forum, j'ai pu créer une bibliotèque de grands nombres et résoudre mon problème.

merci à tous