Estimation d'un Arbre de Recherche - lirmm.frleclere/enseignements/TER/2008/Rapport/8.pdf · Grâce à Windev nous avons pu créer une application Trace Verbose : L'applicatif Trace

Estimation d'un Arbre de Recherche

Université des Sciences Montpellier 2

JuryM. LeclereE. BourreauR. Girodeau

Tazi Abdelaziz(Erasmus)

Avila Mesa Pablo(Erasmus)

25 avril 2008

Index1 Introduction.......................................................................................................................32 Arbre de Recherche .....................................................................................................43 Estimateur ...........................................................................................................................54 Recherche ..........................................................................................................................5

4.1 Cahier de Charges ...............................................................................................54.2 Plateformes Uti l isées ............................................................................................6

4.2.1 Eclipse ..................................................................................................................64.2.2 Windev ................................................................................................................6

5 Developpement..............................................................................................................95.1 Problème Base: Les n Reines ...........................................................................95.2 Comme Résoudre le Problème ....................................................................10

5.2.1 Backtracking ..................................................................................................105.2.2 Branch and Bound (BB)...........................................................................10

5.3 L'Estimateur .............................................................................................................115.3.1 Weighted Backtrack Estimator ...........................................................12

5.3.1.1 Sur le Papier ..........................................................................................125.3.1.2 Implémentation...................................................................................125.3.1.3 Résultats ...................................................................................................145.3.1.4 Conclusion..............................................................................................17

5.3.2 Recursive Estimator ....................................................................................185.3.2.1 Sur le papier ..........................................................................................185.3.2.2 .Implémentation.................................................................................185.3.2.3 Résultats ...................................................................................................195.3.2.4 Conclusion..............................................................................................21

5.4 Le Fichier Log .........................................................................................................216 Conclusion........................................................................................................................237 Résumé ...............................................................................................................................238 Bibl iographie ...................................................................................................................25

Estimation d'un Arbre de RechercheAbdelaziz Tazi (Erasmus) – Pablo Avila Mesa (Erasmus)

1 Introduction

Ce rapport présente notre travail sur le problème des arbres de recherche. Ce TER nous a permis de prendre conscience des difficultées existantes pour estimer en fonctions du temps un problème donné.

Nous avons mis en oeuvres plusieurs techniques pour aboutir au résultat, que se soit l'analyse des résulats existantes ou à la mise en oeuvre de notre propre prototype. C'est 4 mois de travail nous ont permis de se rendre compte du besoin imminant de trouver une solution raisonable au problème des arbres de recherches.

3 / 23


2 Arbre de Recherche

La recherche dans un arbre binaire d'un nœud ayant une clé particulière est un procédé récursif. On commence par examiner la racine. Si sa clé est la clé recherchée, l'algorithme termine et renvoie la racine. Si elle est strictement inférieure, alors elle est dans le sous-arbre droit, sur lequel on effectue alors récursivement la recherche. De même si la clé de la racine est strictement supérieure à la clé recherchée la recherche continue sur le sous-arbre gauche. Si on atteint une feuille dont la clé n'est pas celle recherchée, on sait alors que la clé recherchée n'appartient à aucun nœud.

On peut la comparer avec la recherche dichotomie qui procède à peu près de la même manière sauf qu'elle accède directement à chaque élément d'un tableau au lieu de suivre des liens.

Cette opération requiert un temps en O(ln n) dans le cas moyen, mais O(n) dans le cas critique où l'arbre est complètement déséquilibré et ressemble à une liste chainée.

4 / 23

Exemple d'Arbre de Recherche


3 Estimateur

En statistique inférentielle, un estimateur est une valeur calculée sur un échantillon et que l'on espère une bonne évaluation de la valeur que l'on aurait calculée sur la population totale. On cherche à ce qu'un estimateur soit éfficace.

Pour résoudre le problème des arbres de recherche, nous avons utilisés deux

sortes d'estimateurs Weighted backtrack et Récursif.

L'utilisation d'un estimateur nous a permis d'estimer de façon plus ou moins précise l'évaluation de notre arbre au cour de son deploiement.

Nous avons testé nos deux estimateurs sur le problème de N-Reines en Backtracking et en Branch and Bound.

4 Recherche

4.1 Cahier de Charges

Un cahier de charge a été mis en place au début de notre projet dans lequel nous avons exposé le problème et définit les objectifs à atteindre.

Un diagramme de gant a été mis en place pour répartir les tâches pour les 4 mois du projet.

Notre premier objectif a été d'analysé et de comprendre le sujet, nous avons étudier pendant plusieurs semaines les résultats existants que se soit « Lobjois » ou encore « Knuth » nous avons fait plusieurs lectures sur leurs recherches jusqu'à se faire une idée générale du problème.

Ensuite nous avons commencé à réfléchir à une méthode qui s'approche de celle de « Lobjois » et « Knuth » pour définir notre propre estimateur.

5 / 23


4.2 Plateformes Utilisées

4.2.1 Eclipse

Nous avons opté pour Java comme langage de programmation pour la simplicité d'utiliser un outil tel que Eclipse que nous connaissons bien.

Eclipse IDE est un environnement de développement integré libre extensible, universel et polyvalent, permettant potentiellement de créer des projets de développement mettant en oeuvre n'importe quel langage de programmation. Eclispe IDE est principalement écrit en Java, et ce langage, grâce a des bibliothèques spécifiques, est égalemnt utilisé pour écrire des extensions.

La spécification d'Eclipse IDE vient du fait de son architecture totalement développée autour de la notion de plug-in : toutes les fonctionnalités de cet atelier de logiciel sont développées en tant que plug-in.

Plusieurs logiciels dommerciaux sont basé sur ce logiciel libre, comme par exemple IBM Lotus Notes 8, IBM Symphony ou Websphere Studio Application Developer.

4.2.2 Windev

Un de nos objectifs a été aussi de pouvoir représenter sous forme 2D ou 3D le résultat du déploiement de notre arbre.Pour cela nos premières idées étaient de penser à java3d ou jogl avant de se tourner vers Windev.

Windev est un atelier de génie logiciel.

Grâce à Windev nous avons pu créer une application Trace Verbose :

L'applicatif Trace Verbose à pour objectif la visualisation sous format graphique de différentes valeurs numériques reçus en entrée.

Les valeurs (stockées dans un fichier texte) représentent différentes estimations en temps d’exécution d’un processus récursif de recherche dans un arbre.

Les valeurs sont lues et représentées graphiquement sur un intervalle d’abscisses défini au préalable par l’utilisateur.

Ci-joint une description technique de l’applicatif Trace Verbose :

6 / 23


Trace verbose charge en entrée un fichier au format texte formaté de la manière suivante :

● [numérique] min : [numérique] max : [numérique] t :[numérique]

● Toute autre ligne ne commençant pas par un numériques est ignorée.

● Les valeurs min et max sont lues ligne par ligne est sont stockées dans une table

Le fichier est chargé dans une base de données qui est exploitée par la suite pour représenter la valeur moyenne sur un graphe.

Schéma de la base de données qui stocke le fichier chargée

7 / 23

Base de Données


Lors du chargement du fichier la valeur moyenne est calculée.

Les valeurs sont représentées par l’algorithme ci-dessous.

Toute les valeurs comprises entre les valeurs : « Valeur_de », « Valeurs_a » sont représentées sur le graphe

8 / 23

Extrait du Code de Windev

Extrait du Code de Windev


5 Developpement

5.1 Problème : Les n Reines

Le problème des N-reines est une généralisation du problème original des 8 reines, qui est une devinette proposée par le joueur d'échecs allemand Max Bezzel en 1848 .

Dans le jeu d'échecs la reine menace à une pièce qui se trouve dans la même file, colonne ou diagonale. Les 8 reines consiste à placer sur un tableau d'échecs huit reines sans qu'elles s'attaquent les unes aux autres.

Le problème des N-reines consiste à placer les N reines dans un tableau d'échecs de dimension N * N. Ce problème es un problème classique de recherche et a été utilisé comme test pour le développement et mesure de la vitesse des algorithmes de recherche. Une des formes classiques de résoudre ce problème est d'utiliser le backtracking, mais sa complexité est presque exponentielle à la taille du problème, ce qui fait que autres méthodes ont été développées pour le résoudre comme le branch and bound entre autres.

Nous avons choisi ce problème parce c'est un un problème très étudié avec l'idée de faire un estimateur online (sans savoir à l'avance le numéro de nœuds) extrapolable après aux problèmes de taille inconnu.

9 / 23

Mouvement

Une solution avec 8 reines


5.2 Comment Résoudre le Problème

Comme nous l'avons expliqué, nous avons utilisés deux techniques pour résoudre le problème, backtracking et branch and bound.

5.2.1 Backtracking

Backtracking est une stratégie pour trouver les solutions aux problèmes. Le terme “backtrack” a été utilisé par le mathématicien américain D.H Lehmer dans les années 1950.

Les problèmes qui doivent satisfaire un type déterminé de contraintes sont des problèmes complets, ou l'ordre des éléments de la solution n'importe pas.

Ce type d'algorithme est une recherche en profondeur. Pendant la recherche, si on trouve une alternative incorrecte, la recherche recule jusqu'au pas antérieur et prends l'alternative suivante. Quand tous les possibilitées sont finies on retourne et on prend l'option suivante (fils si on parle d'un arbre). S'il n'y a plus d'alternatives la recherche échoue. De cette manière, on crée un arbre implicite, ou chaque nœud est un état de la solution (solution partielle dans le cas des nœuds intérieurs ou solution totale si sont nœuds feuille).

Normalement on implémente ce type d'algorithme d'une manière récursive Donc dans chaque appel ou procédure on prend une variable et on l'assigne a tous les possibles valeurs, on appelle en même temps la procédure pour chacun des noeuds états.

Nous avons résolu le problème en essayant de placer une reine après l'autre d'une manière brute. On place la première reine dans la case (0,0) et après on essaie la suivante dans la file suivante (1,0), (1,1) etc. jusqu'à ce qu'on trouve une position valide. S'il n'y a eu aucune position valide on retourne à la pièce antérieure et nous essayons dans la colonne suivante.

5.2.2 Branch and Bound (BB)

La stratégie de Branch and Bound est une variante du Backtracking mais qui l'améliore substantiellement. Le terme Branch and Bound est appliqué la plus part du temps pour résoudre les problèmes d'optimisations.

La technique de BB est un arbre de solutions ou chaque branche mène a une possible solution ultérieure a l'actuelle. La caractéristique principale de cette technique consiste dans le fait que l'algorithme se prépose de trouver dans laquelle branche les solutions trouvées et ne pas continuer en perdant

10 / 23


ressources et processus qui sont écartés de la solution optimale.

Le BB dans sa version plus simple peut suivre, à différence du backtracking, un parcours en largeur (Last In Last Out) ou en profondeur (First In First Out) ou utiliser le calcule des fonctions de coût pour choisir le nœud plus prometteur. Aussi le BB utilise cotes pour savoir si la solution partielle (chaque nœud) arrive a une solution valide.

En résumé, on peut dire que cette technique à la possibilité de disposer de différentes stratégies d'exploration d'un arbre de recherche.

Nous avons développé cet technique avec une stratégie FIFO et on a implémenté la fonction pour savoir si un nœud est prometteur de la manière suivante:

// s es un tableau qui garde les solutionspublic boolean esPrometedor(int i) {

// On connait la file i, donc on essaie pour chaque colonnefor (int j = 0; j < col; j++)// Si est dans une file déjà utilise// Si est dans les diagonales d'une case déjà utiliseif ((s[j] == i) || (Math.abs(s[j] - i) == Math.abs(col -

j)))return false;return true;

}

5.3 L'Estimateur

Estimer un arbre de recherche consiste à trouver un mécanisme pour savoir à l'avance combien de temps il faut pour trouver une solution valide au problème.

Nous avons essayé de trouver une méthode pour « estimer » le numéro possible de nœuds que l'arbre aura.

11 / 23


Il existe déjà une méthode connu comme la méthode de Knuth qui est basé sur une formule mathématique N=2d1−1 . Mais le problème de cet

méthode est qu'elle est offline, ce qui veut dire qu'on doit savoir à l'avance la taille du problème.

Notre objectif était de trouver une méthode online pour estimer l'arbre de recherche. Nous avons trouvé deux méthodes online avec lesquelles nous avons travaillé principalement: Le Weighted Backtrack Esitamator et le Recursive Estimator, ce sont des recherches réalisées par un groupe de professeurs de l'université de Camberra (Australie)[1]

5.3.1 Weighted Backtrack Estimator

5.3.1.1 Sur le Papier

Cette méthode consiste à estimer N (numéro total de nœuds) dans quelques points pendant le « backtrack » :

∑ d∈D probd ∗2d1−1∑ d∈D prob d

Ou D est un « multi-ensemble » des longueurs des branches déjà visitées en profondeur pendant le backtracking, et c'est la probabilité aléatoire de visiter la branche d.

5.3.1.2 Implémentation

Nous avons implémenté cet estimateur d'un manière pseudo-externe au problème, comme une classe en java différente aux classes qui l'englobent.Nous l'avons utilisé pour le backtracking et pour le branch and bound.

L'importance de cette implémentation est d'extraire différentes données du problème. On a pris comme éléments remarquables: le numéro de nœuds traités, la niveau de profondeur actuel, le numéro de feuilles qu'ont a trouvé a chaque niveau et le numéro de fils qu'à chaque nœud.

Avec tous les données on a essayé de calculer la formule sur le papier.

On a inséré la formule dans l'algorithme. Et on calcule le numéro de noeuds qui restent à analizer en appliquant la formule.

12 / 23


{...}float arriba = 0;float abajo = 0;float division = 0;for (int i=0; i<ee_hojasProf.length; i++){

// Je prends le numéro de feuilles qu'il y a a chaque niveauint hojasNivel = ee_hojasProf[i];// i est le niveau et hojasNivel est le numéro des branches

(multiplicité)arriba += hojasNivel * Math.pow(2, -i) *

(Math.pow((FACTEUR),i+1) - 1);abajo += hojasNivel * Math.pow(, -i);

}if (arriba == 0 && abajo == 0) division = 0;else division = arriba / abajo;{...}

Nous avons gardé dans un tableau le numéro de feuilles qu'ont trouve dans chaque branche: ee_hojasProf[maxprof] et nous avons déclaré une constante facteur = 2.211 qui est un facteur de correction.

5.3.1.3 Résultats

Comme on l'a déjà dit auparavant, trouver un estimateur online pour savoir la taille d'un arbre de recherche est une idée un peut prétentieuse, donc nous avons essayé de nous approcher à un résultat connu à l'avance.

Les résultats qu'on a obtenu avec l'estimateur Weighted Backtrack ont été très différentes.

On a fait plusieurs tests, mais trois représentatifs sont: 4-reines, 8-reines et 20-reines.

Backtracking

4-reines

------------------------------------Noueds Traites: 16Feuilles: 4Profondeur actuel: 3Profondeur maximum: 4Estimation: 10.058344Percentage: 159%------------------------------------Total Backtracks: 4[1, 3, 0, 2]

Ici l'estimateur sous-estime le numéro total de nœuds, il pense que le numéro de nœuds qu'il y a dans l'arbre est 10. Le tableau montre la première solution trouvée.

13 / 23


8-reines

------------------------------------Noueds Proceses: 226Feuilles: 105Profondeur actuel: 7Profondeur maximum: 8Estimation: 82.94653Percentage: 272%------------------------------------Total Backtracks: 105[0, 4, 7, 5, 2, 6, 1, 3]

Ici aussi l'estimateur sous-estime le numéro total de nœuds, il pense qu'il a 83, mais comme on peut voir dans les résultats, il y a 226.

20-reines

------------------------------------Noueds Proceses: 399270Feuilles: 199615Profondeur actuel: 19Profondeur maximum: 20Estimation: 65116.91Percentage: 613%------------------------------------Total Backtracks: 199615[0, 2, 4, 1, 3, 12, 14, 11, 17, 19, 16, 8, 15, 18, 7, 9, 6, 13, 5, 10]

Branch and Bound

4-reines

------------------------------------Nœuds Proceses: 9Feuilles: 2Profondeur actuel: 4Profondeur maximum: 4Estimation: 19.552431Percentage: 46%------------------------------------[1, 3, 0, 2]

Notre estimateur sous-estime presqu'à la moitié des numéros de nœuds entre l'estimation et la réalité.

14 / 23


8-reines

------------------------------------Nœuds Proceses: 114Feuilles: 42Profondeur actuel: 8Profondeur maximum: 8Estimation: 193.27232Percentage: 58%------------------------------------[0, 4, 7, 5, 2, 6, 1, 3]

Ici on peut voir qu'il a sous-estime moins que dans le test antérieur.

20-reines

------------------------------------Nœuds Proceses: 199636Feuilles: 72079Profondeur actuel: 20Profondeur maximum: 20Estimation: 190156.48Percentage: 104%------------------------------------[0, 2, 4, 1, 3, 12, 14, 11, 17, 19, 16, 8, 15, 18, 7, 9, 6, 13, 5, 10]

Ici l'estimation est presque parfaite,

Qu'est-ce qu'il se passera si on essaye avec 24 ?

------------------------------------Nœuds Proceses: 411609Feuilles: 148825Profondeur actuel: 24Profondeur maximum: 24Estimation: 1834323.9Percentage: 22%------------------------------------[0, 2, 4, 1, 3, 8, 10, 13, 17, 21, 18, 22, 19, 23, 9, 20, 5, 7, 11, 15, 12, 6, 16, 14]

Nous avions raison, l'estimateur a sur-estime l'arbre...donc la cote serai entre 20 et 24 reines.

15 / 23


5.3.1.4 Conclusion

Cet estimateur à été difficile d'implémenter et il n'est pas très fiable si on ne connait pas la taille du problème

Aussi, on peut dire que ce n'est pas complètement un estimateur online, parce que pour garder les feuilles qu'il y a dans chaque niveau il est nécessaire de savoir à l'avance la taille maximum de l'arbre.

Donc, avec cet pseudo-estimateur online et certaines améliorations ne doit être très loin une solution plus optimal avec un autre estimateur meilleur.

16 / 23


5.3.2 Recursive Estimator

5.3.2.1 Sur le papier

Le deuxième estimateur online est basé sur un schéma simple de récursion

On suppose que nous sommes dans un processus de parcourir l'arbre en profondeur et de gauche à droite. On sait exactement la taille de la partie depuis la position actuelle vers la gauche parce qu'on l'a déjà visité, donc la meilleure manière d'estimer l'arbre entier est la somme de la partie correcte et une estimation de la partie qui manque.

5.3.2.2 .Implémentation

L'implémentation de cet estimateur a été plus facile que la précédente. On a fait un tableau long info[6] pour garder les caractéristiques suivantes:

0 - Niveau Actuel1 – Fils dans cet moment2 - Frères qui manque par traiter3 - Nœuds Traités4 - Nœuds Estimés5 - Minimum numéro de nœuds

Pour savoir les nœuds estimées on applique la formule suivante:

17 / 23

Pseudo-code Estimateur Recursif

function search(node,depth)1: if leaf(node) then2: if goal(node) then3: return .success.4: else return 15: else6: left[depth] := .estimated.7: result := search(left(node),depth+1)8: if result=.success. then9: return .success.10: else11: left[depth] := result12: result := search(right(node),depth+1)13: if result=.success. then14: return .success.15: else return 1 + left[depth] + resultfonction estimate(node,depth)1: if leaf(node) then2: return 13: else4: if left[depth]=.estimated. then5: leftsize := estimate(left(node),depth+1))6: rightsize := F(right(node))7: else8: leftsize := left[depth]9: rightsize := estimate(node(right),depth+1)10: return 1 + leftsize + rightsize


private int calcular(int minimo2, int hijos2, int hermanosfaltan2) {int prod1 = hijos2 * hermanosfaltan2/2;int prod2 = hijos2/2 * hermanosfaltan2/2;int sum = minimo2 + hijos2 + prod1 + prod2;

return sum;}

Où minimo2 est le minimum des numéros de nœuds dont nous sommes certains qu'ils existent (traités + numéro de fils du node actuel), aussi hijos2 est le numéro de fils du node actuel, et hermanosfaltan2 est la quantité des frères à droite qui manquent à traiter.

Donc notre formule est:

MinimunFilsFils∗ FreresManquent2

Fils2

∗ FreresManquent2

Si le résultat de l'estimation est plus petit que le minimum, l'estimation serait la minimum (Cette situation passe quand le nœud n'a pas de fils)

Cet estimateur fait deux calculs en même temps:

● le Pourcentage en profondeur

● le Pourcentage en numéro de nœuds

Finalement, on doit ajouter que pour « harmoniser » le Pourcentage des estimations, on a calculé la moyenne entre les valeurs d'un intervalle qu'on a gardé comme constante.

5.3.2.3 Résultats

On a testé seulement avec l'algorithme de branch and bound.

On a choisi un interval de 2 nœuds , parce que quand l'algorithme a trouvé une solution, cet estimateur se met à jour avec les résultats finaux, il est intéressant de savoir exactement ce qui se passe au le moment juste avant la fin de l'execution.

18 / 23


4 – reines

-----------------------------------Niveau Actuel: 3Processes: 8Estimes: 11Percentage Nœuds: 72%Profondeur: 75%----------------------------------------------------------------------Niveau Actuel: 4Processes: 9Estimes: 9Percentage Nœuds: 100%Profondeur: 100%-----------------------------------[1, 3, 0, 2]

On peut voir les deux dernièrs mouvements et conclure que cette estimation est assez correct pour notre objectif.

8 – reines

-----------------------------------Niveau Actuel: 6Processes: 112Estimes: 130Percentage Nœuds: 86%Profondeur: 75%----------------------------------------------------------------------Niveau Actuel: 8Processes: 114Estimes: 114Percentage Nœuds: 100%Profondeur: 100%-----------------------------------[0, 4, 7, 5, 2, 6, 1, 3]

ce résultat est assez bon, notre Pourcentage de nœuds a été plus proche à la solution que le Pourcentage de profondeur.

19 / 23


20 – reines

-----------------------------------Niveau Actuel: 18Processes: 199634Estimes: 199835Percentage Nœuds: 99%Profondeur: 90%----------------------------------------------------------------------Niveau Actuel: 20Processes: 199636Estimes: 199636Percentage Nœuds: 100%Profondeur: 100%-----------------------------------[0, 2, 4, 1, 3, 12, 14, 11, 17, 19, 16, 8, 15, 18, 7, 9, 6, 13, 5, 10]

On peut dire que notre estimateur a été très proche, presque parfait, mais on a noté que dans un moment du parcours vers la moitié de l'arbre notre estimateur s'approche trop a des valeurs plus grandes que 90%. Le motif de ce problème est notre formule, on a choisi un formule qui estime d'une manière proportionnelle la taille de la moitié des fils qui manquent, et pour l'autre mopitié il estime comme la moitié de la proportion.

5.3.2.4 Conclusion

Cet estimateur a été plus facile d'implémenter que l'autre, et plus fiable.

Dans ce cas on peut être satisfait car notre estimateur est vraiment online si on veux seulement calculer l'estimation avec le numéro de nœuds.

Pour améliorer cet estimateur, il est possible d'optimiser la formule de calcule, et aussi utiliser la formule de l'estimateur Weighted Backtrack.

5.4 Le Fichier Log

Chacun de nos estimateurs permet de générer un fichier log, et grâce a un autre programme généré par Windev nous pouvons importer des fichiers log et repésenter les résultats graphiquement.

20 / 23


Forme du fichier log :

100 min : 4 max : 37 t:1204833494750200 min : 15 max : 35 t:1204833495328300 min : 13 max : 36 t:1204833495937400 min : 10 max : 31 t:1204833496750500 min : 12 max : 31 t:1204833497578600 min : 14 max : 30 t:1204833498468700 min : 13 max : 31 t:1204833499218800 min : 11 max : 27 t:1204833499921900 min : 18 max : 30 t:12048335005781000 min :19 max : 31 t:12048335012501100 min : 15 max : 31 t:12048335019211200 min : 20 max : 34 t:12048335024531300 min : 15 max : 33 t:12048335030151400 min : 17 max : 31 t:12048335036091500 min : 20 max : 32 t:12048335042811600 min : 18 max : 30 t:12048335049681700 min : 12 max : 32 t:12048335057501800 min : 20 max : 33 t:12048335065151900 min : 19 max : 32 t:12048335071402000 min : 15 max : 33 t:12048335079062100 min : 20 max : 36 t:1204833508390

21 / 23


6 Conclusion

Nous avons réalisé deux estimateurs différents pour calculer la taille d'un arbre de recherche pour un problème connu dans le cadre du TER correspondant au M1 du Master en Informatique.

Nous avons essayé de nous approcher le plus possible à une solution optimale du problème, mais après avoir fait des recherches sur le sujet, nous avons trouvé que le sujet est assez compliqué.

Nous avons commence par étudier les conclusions que Knuth a trouvé pour les problèmes complets de recherche d'une manière offline, et suivant cette basse nous sommes arrivé au moment ou Lemaittre et Lobjois optimisèrent l'estimateur de Knuth. Finalement, nous nous sommes basé sur l'article « Estimating Search Tree Size » des professeurs Kilby, Slaney, Thiebaux et Walsh de l'universite de Camberra (Australie) de l'annee 2006.

Nous sommes parvenu à la conclusion qu'estimer la taille d'un arbre de recherche d'une taille maximale inconnu d'une manière online c'est un processus assez complexe du à la diversité des arbres aux formes très différentes qui peuvent exister selon les différents problèmes de recherche.

7 Résumé

Ce projet a été l'occasion pour nous de s'approcher des conditions réelles de réalisation d'un projet et nous a permis de mettre le doigt sur nos forces et nos faiblesses.

Ainsi, pour ce projet, la connaissance et le choix de java et windev,l'élaboration d'un planning nous ont permis d'atteindre nos objectifs.

Nous sommes fiers de notre approche qui nous a permis d'obtenir une vue d'ensemble structurée et explicite de notre projet tout au long de sa conception. Grâce à cela, la réutilisation de notre travail devrait être plutôt aisée tant pour nous que pour une autre équipe qui pourrait avoir en charge, par exemple, de trouver une solution au problème d'ETERNITY II.

22 / 23


8 Bibliographie

[1.] Estimating Search Tree Size: Kilby, Slaney, Thiébaux, Walsh. University of Camberra (Australia), 2006

[2.] Wikipedia.org

[3.] Facultad de Informática de la Universidad Politécnica de Valencia (Espagne)

[4.] Facultad de Informática de la Universidad Complutense de Madrid (Espagne)

[5.] Facultad de Informática de la Universidad de Murcia (Espagne)

[6.] Windev Help

[7.] Branch and Bound Tree Size Estimation: Wasu Glankwamdee. COR@L Seminar September 28, 2006

23 / 23

Documents

Estimation d'un Arbre de Recherche - lirmm.frleclere/enseignements/TER/2008/Rapport/8.pdf · Grâce à Windev nous avons pu créer une application Trace Verbose : L'applicatif Trace