On veut parcourir ce graphe par le chemin le plus court pour atteindre l’état final en partant de l’état initial pour cela, trois fonctions heuristiques sont proposées:

1. f(x): On parcours toujours la plus petite distance.
2. g(x): On cherche toujours à minimiser la distance à vol d’oiseau.
3. h(x): On minimise f(x)+g(x)

Effectuer l’exécution de l’algorithme best first search en prenant comme fonction d’évaluation les 3 fonctions f(x), g(x), h(x) présentées précédement. Écrivez le nom de tous les noeuds parcourus, même si il y a de boucles ou des retours en arrières.

TP

Série 2 : Complexité & Recherche Aveugle

Les tours de Hanoï

Les deux figures ci-après sont identiques, elles représentent une partie de l'arbre de recherche pour le problème des tours de Hanoï. Vous devez compléter ces figures en étiquettant les noeuds avec les nombres 1;2;3... qui indiquent l'ordre dans lequel les noeuds sont traités. Première figure: recherche en profondeur. Deuxième figure: recherche en largeur.

1.1 Questions

1. Pour chacun des deux algorithmes, dessiner l'état de la FILE à chaque état jusqu'à ce que le noeud N en soit extrait.

En profondeur	En largeur
1: (B, C)	1: (C, B)
2: (D, E, F, C)	2: (B, D, E, F)
3: (J, K, E, F, C)	3: (D, E, F, G, H, I)
4: (K, E, F, C)	4: (E, F, G, H, I, J, K)
5: (E, F, C)	5: (F, G, H, I, J, K)
6: (F, C)	6: (G, H, I, J, K)
7: (C)	7: (H, I, J, K)
8: (G, H, I)	8: extraction du noeud H!
9: extraction du noeud G!

2. Définissez la complexité en temps et en espace des deux stratégies (en fonction de b, d et m)

profondeur: O(b^m) = O(2^∞)
largeur: O(b^d) = O(2³)

3. Quels problèmes voyez-vous pour chacune des stratégies de recherche? Y a t'il un moyen de les résoudre?

profondeur: Sera complète seulement si l'arbre n'est ni infini ni cyclique. Solution: Recherche par approfondissement itératif.
largeur: La recherche devient vite exponentielle, trop grande, répétitive.

4. Laquelle des deux stratégies pensez-vous la plus adaptée pour résoudre ce problème? Répondez à la question en parlant des concepts de complétude, optimalité.

La meilleure recherche serait par approfondissement itératif, car elle est optimale et complète, et économe en espace. Mais entre largeur et profondeur, je ne sais pas.

1.2 Notation Grand O

Pour chacune des égalités, transformer le "=" en "< > ou ≠" quand cela est nécessaire. En cas d'égalité, donner explicitement le C qui satisfait l'égalité.

1. 1 = 100

même puissance
lim 1 = C * lim O(100)
1 = C * 100
¹⁄₁₀₀ = C

2. 1 = O(n)

1 < O(n)

3. n = O(10n + 5)

même puissance
^lim_n->∞(n) ≤ C * ^lim_n->∞(10n + 5)
^∞/_∞ ≤ C

4. n² = O(100n)

n² > O(100n)

5. n = O(n²)

n < O(n²)

6. 10n³ + n² - 5n + 100 = O(n³)

même puissance
^lim_n->∞(10n³ + n² - 5n + 100) = C * ^lim_n->∞(n³)
C=¹/₁₀

7. n⁵⁰⁰⁰⁰ + 1000000 = O(2ⁿ)

n⁵⁰⁰⁰⁰ + 1000000 < O(2ⁿ)

8. n2ⁿ = O(2ⁿ)

même puissance
^lim_n->∞(n2ⁿ) ≤ C * ^lim_n->∞(2ⁿ)
C = 1

Résumé du cours