Introduction à la Recherche Heuristique

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Qu'est-ce qu'une heuristique ?

Une heuristique est une règle empirique, une simplification ou une supposition éclairée qui réduit ou limite la recherche de solutions dans des domaines difficiles et mal compris. Contrairement aux algorithmes, les heuristiques ne garantissent pas de solutions viables et sont souvent utilisées sans garantie théorique.

Que signifie "recherche gloutonne" ?

La recherche gloutonne est une stratégie de recherche qui choisit à chaque étape l'option qui semble la meilleure à ce moment-là, sans tenir compte des conséquences futures. Elle vise à trouver la meilleure solution locale possible, mais elle n'est pas toujours optimale.

La recherche gloutonne garantie toujours la solution optimale.

False

Qu'est-ce que la recherche A* ?

La recherche A* est une technique de recherche qui utilise une heuristique admissible pour estimer le coût de l'état actuel à l'état final. Elle essaie de trouver un chemin optimal en minimisant le coût total estimé. Signup and view all the answers

La recherche A* est toujours optimale si l'heuristique utilisée est admissible.

True Signup and view all the answers

Nommez deux types d'heuristiques.

Deux types d'heuristiques sont la distance de Manhattan et le nombre de pièces mal placées. Signup and view all the answers

En quoi consiste la recherche locale ?

La recherche locale est une technique de recherche qui modifie l'état actuel en l'améliorant au fur et à mesure jusqu'à atteindre un état optimal. Elle ne prend pas en compte le chemin suivi pour arriver à la solution, elle est axée sur l'état lui-même. Elle nécessite une fonction qui mesure l'utilité de chaque état. Signup and view all the answers

Expliquez comment fonctionne l'algorithme d'ascension du gradient.

L'algorithme d'ascension du gradient est une forme de recherche locale qui commence à partir d'un état initial et se déplace vers un état voisin ayant une valeur plus élevée, jusqu'à ce qu'il trouve un maximum local. Il ne garantit pas de trouver le maximum global. Signup and view all the answers

Quelle est la principale différence entre l'ascension du gradient et la recherche A* ?

L'ascension du gradient est une technique de recherche locale qui ne retient que l'état actuel, tandis que la recherche A* garde en mémoire un ensemble de nœuds explorés et utilise une heuristique pour estimer le coût jusqu'à la solution. Signup and view all the answers

En quoi consiste la technique de Branch and bound ?

Branch and bound est une technique d'énumération intelligente de l'arbre de recherche qui combine la séparation et la réduction pour trouver la solution optimale. Elle élimine des nœuds de l'arbre de recherche en utilisant des bornes supérieures et inférieures pour évaluer le coût des solutions. Signup and view all the answers

Quel est le but de la technique "Branch and bound" ?

Le but de la technique "Branch and bound" est de trouver la solution optimale à un problème d'optimisation en explorant intelligemment l'arbre de recherche et en éliminant des branches inutiles. Signup and view all the answers

Study Notes

Introduction à la Recherche Heuristique

La recherche heuristique est une méthode utilisée pour trouver des solutions à des problèmes complexes.
Elle repose sur des règles d'ordre, des estimations et des simplifications.
Elle ne garantit pas toujours une solution optimale, mais elle est souvent plus rapide que les méthodes exhaustives.
Une heuristique est une règle ou une astuce qui peut aider à résoudre un problème, mais qui n'est pas garantie de trouver le meilleur résultat.
Les heuristiques sont souvent utilisées dans des problèmes où une solution exacte est difficile à trouver ou trop coûteuse en temps ou en ressources.

Recherche du Meilleur d'abord

Cette approche cherche le nœud le plus prometteur selon une fonction heuristique.
La fonction heuristique (F) évalue la désirabilité d'un nœud (ou l'état).
Exemples : Recherche gloutonne et Recherche A*.

Recherche Gloutonne

Une fonction d'évaluation (f(n)) utilise uniquement l'heuristique (h(n)).
L'estimation du cout (h(n)) représente la distance (par exemple, le vol d'oiseau) du nœud actuel à l'état final.
Développe le nœud qui semble le plus proche de la solution.
Cette approche n'est pas complète ni optimale.
Sa complexité temporelle est O(bm) et sa complexité spatiale est O(bm).

Recherche A*

Évite de développer des chemins déjà considérés coûteux.
Fonction d'évaluation : f(n) = g(n) + h(n)
- g(n) : coût de l'état initial jusqu'au nœud n.
- h(n) : coût estimé du nœud n jusqu'à l'état final.
f(n) représente le coût total estimé.
Utilise une heuristique admissible (h(n) <= h*(n)).
(h*(n))est le coût réel pour atteindre l'état final depuis le nœud n.
Une heuristique admissible ne surestime jamais le coût réel.
Si h(n) = 0 pour tout n, alors A* est équivalent à Dijkstra.
h1 domine h2 si h1 et h2 sont admissibles et h1(n) >= h2(n) pour tout nœud n.
Complète et optimale si l'heuristique est admissible.
Complexité temporelle et spatiale de O(b^m) où m représente la profondeur moyenne de la solution.

Exemples d'Heuristiques

h₁(n): nombre de pièces mal placées (exemple du puzzle).
h₂(n): distance de Manhattan (somme des différences en abscisses et ordonnées des positions actuelles et finales des pièces).

Recherche Locale

Dans de nombreux problèmes d'optimisation, le chemin vers la solution n'est pas important ; seul l'état final est important.
L'idée est de modifier l'état actuel pour l'améliorer.
Espace d'états : ensemble des configurations possibles des états.
Recherche d'une fonction qui mesure l'utilité d'un état.

Recherche Locale - Exemple

Le problème des huit dames : Placer huit pièces sur un échiquier de façon qu'aucune pièce n'attaque une autre.

Problèmes de la Recherche Locale

Peut rester bloqué localement (maximum local) au lieu de trouver le maximum global.
Risque de ne pas converger vers une solution optimale.
Nécessite souvent de nombreux essais.

Algorithme d'Ascension du Gradient (Hill Climbing)

Cherche le prochain état voisin qui améliore la fonction de valeur.
Si aucun voisin n'est meilleur, on retourne l'état courant.
Risque de ne pas converger vers une solution optimale.

Recherche Branch and Bound

Une recherche intelligente de l'arbre de recherche.
Chaque nœud intermédiaire représente une solution partielle.
Les feuilles représentent les solutions complètes.
Branching (séparation) : Comment partitionner l'espace de solutions ?
Sélection du nœud :
- Recherche en profondeur d'abord (rapidité).
- Recherche en largeur d'abord.
- Recherche en meilleure limite (dépend de l'heuristique et de la limite inférieure).
Upper bound : Coût d'une solution réalisable (ex. coût d'une solution complète).
Lower bound : Estimation du coût d'une solution simplifiée (ou partielle).

Branche et Limitation - Exemple

Affectation de tâches aux employés, où les éléments de l'arbre indiquent la tâche attribuée à chaque employé.
Cette solution comprend des concepts provenant des diapositives.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Ce quiz explore les concepts fondamentaux de la recherche heuristique, une méthode essentielle pour résoudre des problèmes complexes. Il aborde les méthodes telles que la recherche gloutonne et la recherche A*, ainsi que l'utilisation de fonctions heuristiques pour évaluer les nœuds. Testez vos connaissances sur ces techniques et leur application.