Podcast
Questions and Answers
Les stratégies informées utilisent un ensemble de règles pour évaluer la probabilité qu'un chemin soit meilleur que les autres.
Les stratégies informées utilisent un ensemble de règles pour évaluer la probabilité qu'un chemin soit meilleur que les autres.
True
Les heuristiques permettent d'estimer le coût des divers chemins avant de les parcourir.
Les heuristiques permettent d'estimer le coût des divers chemins avant de les parcourir.
True
Quel est le but des algorithmes de recherche heuristique?
Quel est le but des algorithmes de recherche heuristique?
Le but des algorithmes de recherche heuristique est d'utiliser des fonctions heuristiques pour améliorer le processus de recherche.
La recherche gloutonne est une stratégie qui tient compte du chemin parcouru jusque-là.
La recherche gloutonne est une stratégie qui tient compte du chemin parcouru jusque-là.
Signup and view all the answers
Donnez un exemple de mesure d'utilité utilisée dans la recherche gloutonne.
Donnez un exemple de mesure d'utilité utilisée dans la recherche gloutonne.
Signup and view all the answers
La recherche gloutonne est toujours optimale.
La recherche gloutonne est toujours optimale.
Signup and view all the answers
L'algorithme A* est une amélioration de la recherche gloutonne.
L'algorithme A* est une amélioration de la recherche gloutonne.
Signup and view all the answers
Expliquez la formule f(n) = g(n) + h(n) utilisée dans l'algorithme A*
Expliquez la formule f(n) = g(n) + h(n) utilisée dans l'algorithme A*
Signup and view all the answers
Une heuristique est admissible si elle sous-estime le coût réel pour atteindre l'état final.
Une heuristique est admissible si elle sous-estime le coût réel pour atteindre l'état final.
Signup and view all the answers
Une heuristique admissible permet toujours de trouver la solution optimale.
Une heuristique admissible permet toujours de trouver la solution optimale.
Signup and view all the answers
L'algorithme A* est un algorithme de recherche aveugle.
L'algorithme A* est un algorithme de recherche aveugle.
Signup and view all the answers
L'heuristique h1(n) pour le taquin compte le nombre de pièces mal placées.
L'heuristique h1(n) pour le taquin compte le nombre de pièces mal placées.
Signup and view all the answers
L'heuristique h2(n) pour le taquin calcule la somme des distances entre chaque pièce et sa position finale.
L'heuristique h2(n) pour le taquin calcule la somme des distances entre chaque pièce et sa position finale.
Signup and view all the answers
Study Notes
Stratégies Informées
- Ces stratégies utilisent un ensemble de règles pour évaluer la probabilité qu'un chemin soit meilleur que les autres, partant d'un nœud courant vers un nœud solution.
- Elles permettent d'estimer le coût de différents chemins avant leur exploration, améliorant ainsi le processus de recherche.
- Les algorithmes de recherche heuristique emploient des fonctions heuristiques (h : E → R).
Heuristique
- Fournit des informations supplémentaires pour guider la recherche, représentées par une mesure h(Ei) associée à chaque état.
- Aide à choisir le nœud le plus prometteur à développer, à déterminer les successeurs à engendrer et à identifier les nœuds à ignorer.
- Permet de trouver rapidement une solution réalisable, même si non optimale, pour des problèmes d'optimisation complexes.
Stratégies Informées - Spécifiques
- Meilleur d'abord : utilise des algorithmes gloutons.
- Algorithme A*: un algorithme amélioré en considérant le coût déjà dépensé.
Recherche Gloutonne
- La mesure de l'utilité ne dépend que de l'état courant, et non du chemin parcouru.
- Par exemple, dans une recherche du chemin le plus court entre deux villes, la mesure d'utilité pourrait être la distance à vol d'oiseau.
- Cette approche est incomplète car elle peut se retrouver coincée dans des boucles. Elle peut être rendue complète en vérifiant si des états ont déjà été visités.
Caractéristiques de la recherche gloutonne
- Incomplète (boucles)
- Complète si on ajoute des vérifications pour les états déjà explorés.
- Complexité en temps : O(bm)
- Complexité en espace : O(bm)
- Non optimale
Exemple : Pièces de monnaie
- Problème : rendre la monnaie pour un montant donné (S) avec le moins de pièces possible.
- Exemple : pièces de 1, 2, 5, 10... pour un montant de 26.
- Méthode : trier les pièces par valeurs décroissantes, choisir la pièce de plus grande valeur qui ne dépasse pas le montant restant et répéter jusqu'à ce que le montant restant soit nul.
- Avec les pièces de 1, 2, 5, 10 (pas de 20, example du slide): pour un montant de 26, l'algorithme glouton peut donner 6 pièces (2 * 10 + 6 * 1), alors que la solution optimale serait de 3 pièces (2* 10 + 6 * 1).
Algorithme A*
- Améliore la recherche gloutonne en tenant compte du coût déjà dépensé.
- Utilise une fonction de coût : f(n) = g(n) + h(n)
- g(n) : coût de l'état initial jusqu'à l'état n.
- h(n) : estimation heuristique du coût pour atteindre l'état final depuis l'état n.
- Fonction f(n) pour prioriser les états.
- Admissible si l'heuristique h(n) est toujours inférieure ou égale au coût réel pour atteindre l'état final depuis l'état n. Exemple: distance à vol d'oiseau.
- Complète et optimale quand l'heuristique est admissible.
- Complexité en temps: O(bm).
- Complexité en espace: O(bm).
Conclusion
- Les algorithmes de recherche aveugles sont très coûteux en temps ou espace car ils explorent tous les chemins.
- Les algorithmes heuristiques élaguent l'arbre de recherche et convergent plus rapidement vers une solution si elle existe.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Découvrez les stratégies informées utilisées dans les algorithmes de recherche heuristique. Ce quiz explore les techniques d'évaluation des chemins et l'utilisation de fonctions heuristiques pour améliorer le processus de recherche d'une solution. Testez vos connaissances sur des concepts comme l'algorithme A* et d'autres approches heuristiques.
