Stratégies Informées et Algorithmes de Recherche (PDF)

Stratégies informées ❑ Utilisent un ensemble de règles qui permettent d’évaluer la probabilité qu’un chemin allant du nœud courant au nœud solution soit meilleur que les autres. ❑ Cette information permet l’estimation des coûts des divers chemins avant de les parcourir afin d’améliore le proces...

Stratégies informées ❑ Utilisent un ensemble de règles qui permettent d’évaluer la probabilité qu’un chemin allant du nœud courant au nœud solution soit meilleur que les autres. ❑ Cette information permet l’estimation des coûts des divers chemins avant de les parcourir afin d’améliore le processus de recherche. ❑ Les algorithmes de recherche heuristique utilisent des fonctions appelées fonctions heuristiques. h : E –>R  Algorithmes de Recherche pour la Résolution de Problèmes 1 Heuristique ❑ Informations supplémentaires pour orienter la recherche ▪ Une mesure associée à un état donné qu’on notera h(Ei). ❑ Utilité ▪ Choisir le nœud à développer : le plus prometteur ▪ Déterminer les successeurs à engendrer : quels opérateurs ▪ Décider des nœuds à ignorer ❑ Elle fournit rapidement une solution réalisable, pas nécessairement optimale, pour un problème d'optimisation difficile.  Algorithmes de Recherche pour la Résolution de Problèmes 3 Stratégies informées ❑ Meilleur d'abord ▪ Algorithmes gloutons ❑ Algorithme A∗  Algorithmes de Recherche pour la 4 Résolution de Problèmes Recherche gloutonne ❑ La mesure d’utilité ne dépend pas du chemin parcouru jusque là mais uniquement de l’état considéré ❑ Par exemple dans recherche du plus court chemin entre deux villes,  ▪ distance à vol d’oiseau entre les villes Algorithmes de Recherche pour la Résolution de Problèmes 6 Caractéristiques de la recherche gloutonne ❑ Incomplète (car boucles) ▪ Complet si on ajoute des tests sur les états répétés. ❑ Complexité en temps : O(b ) m ❑ Complexité en espace : O(b ) m ❑ Non optimale. Algorithmes de Recherche pour la Résolution de Problèmes 7 Exemple: Pièces de monnaie ❑ On considère le problème où l’on doit rendre la monnaie pour une certaine somme S avec le moins possible de pièces de monnaies. ❑ On a des pièces de 1, 2, 5, 10, 20. Quelle est la solution optimale? Avec S=26 Algorithmes de Recherche pour la 8 Résolution de Problèmes Exemple: Pièces de monnaie ❑Trier les types de pièces par valeurs décroissantes. ❑Pour chaque valeur de pièce, maximiser le nombre de pièces choisies. ❑ Répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante tant que celle-ci n’est pas nulle. Algorithmes de Recherche pour la 9 Résolution de Problèmes Exemple: Pièces de monnaie  Avec S=26 (3 pièces) – 1 pièce de 20 – 1 pièce de 5 – 1 pièce de 1 10 Algorithmes de Recherche pour la Résolution de Problèmes Exemple: Pièces de monnaie S = 26 à payer en pièces de 7, 6, 1 Algorithme glouton (8 pièces) – 3 Pièces de 7 – 5 pièces de 1 Solution optimale (4 pièces) – 2 pièces de 7 – 2 pièces de 6 11 Algorithmes de Recherche pour la Résolution de Problèmes Exemple2: trouver un chemin entre 2  villes Algorithmes de Recherche pour la Résolution de Problèmes 12 Algorithme A* ❑ Améliorer la recherche gloutonne en prenant en compte le coût déjà dépensé ❑ f (n) = g(n) + h(n) ▪ g(n) coût de l’état initial jusqu’à n ▪ h(n) heuristique estimant le coût de n à un état final ▪ f (n) fonction pour prioriser les états Algorithmes de Recherche pour la Résolution de Problèmes 13 Admissibilité de l’heuristique ❑ h est admissible si pour tout état n on a 0 ≤ h(n) ≤ h∗(n) où h pour aller de n à un ∗ (n) est le vrai coût état final ❑ Exemple d’heuristique admissible : – distance à vol d’oiseau (inégalité triangulaire) Algorithmes de Recherche pour la Résolution de Problèmes 14 Exemple: trouver un chemin entre 2 villes Algorithmes de Recherche pour la Résolution de Problèmes 15 Caractéristiques de l’algorithme A* ❑ On suppose l’heuristique admissible – Complète – Complexité en temps : O(bm) – Complexité en espace : O(bm) – Optimale Algorithmes de Recherche pour la  Résolution de Problèmes 16 Exemples d’heuristiques pour le taquin ❑ h1(n) = nombre de pièce mal placées ❑ h2(n) = sommes des distances de chaque pièce à sa position finale ❑ h3(n) = h2(n) + 3s(n) ▪ avec s(n) = somme des scores pour chaque case : case périphérique : 2 si pas suivie par son successeur, 0 sinon case centrale : 1 si pas no 4, 0 sinon Algorithmes de Recherche pour la  Résolution de Problèmes 17 Heuristique pour le score ❑Les cases doivent se succéder dans le bon ordre sur les bords ❑La case du milieu doit être la bonne. Sur les bords, pénalité de 1 si ▪ pas bon successeur ▪ pas bon prédécesseur Au milieu, pénalité de 1 si pas no 4  Algorithmes de Recherche pour la Résolution de Problèmes 18 CONCLUSION ❑ Les algorithmes de recherche aveugle sont les algorithmes les plus coûteux évidemment en temps ou en espace car ils ont tendance à développer l’arbre complet pour aboutir à une solution où à l’ensemble de solutions. ❑ Les algorithmes heuristiques permettent d’élaguer un ensemble de branches de l’arbre et de converger rapidement vers une solution si cette solution existe. 19 Algorithmes de Recherche pour la Résolution de Problèmes