Introduction à la Recherche Heuristique
11 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

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 (B)

Qu'est-ce que la recherche A* ?

<p>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é.</p> Signup and view all the answers

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

<p>True (A)</p> Signup and view all the answers

Nommez deux types d'heuristiques.

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

En quoi consiste la recherche locale ?

<p>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.</p> Signup and view all the answers

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

<p>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.</p> Signup and view all the answers

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

<p>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.</p> Signup and view all the answers

En quoi consiste la technique de Branch and bound ?

<p>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.</p> Signup and view all the answers

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

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

Flashcards

Qu'est-ce qu'un algorithme heuristique ?

Un algorithme heuristique est une stratégie de résolution de problèmes qui utilise des règles empiriques et des approximations pour trouver une solution acceptable, plutôt que de garantir la solution optimale.

Définition d'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 complexes et mal compris.

Recherche heuristique: Définition

La recherche heuristique est une technique utilisée dans la résolution de problèmes d'intelligence artificielle pour trouver des solutions acceptables à des problèmes complexes. Elle utilise des fonctions heuristiques pour estimer la qualité d'une solution potentielle.

Recherche "meilleur d'abord"

La recherche "meilleur d'abord" est une stratégie de recherche heuristique qui explore les nœuds les plus prometteurs d'abord, en utilisant une fonction heuristique pour estimer la distance à la solution.

Signup and view all the flashcards

Recherche gloutonne

La recherche gloutonne est une stratégie de recherche heuristique qui fait toujours le choix localement optimal à chaque étape, sans regarder l'impact à long terme. Elle peut ne pas trouver la solution optimale.

Signup and view all the flashcards

Fonction d'évaluation (Recherche gloutonne)

La fonction d'évaluation dans la recherche gloutonne utilise uniquement l'heuristique pour estimer le coût de la solution. Elle n'inclut pas le coût déjà parcouru.

Signup and view all the flashcards

Completude et Optimalité de la recherche gloutonne

La recherche gloutonne n'est pas nécessairement complète, car elle peut ne pas explorer tous les nœuds possibles. Elle peut également ne pas être optimale, car elle peut manquer une solution meilleure.

Signup and view all the flashcards

Complexité temporelle (Recherche gloutonne)

La complexité temporelle de la recherche gloutonne est de O(bm), où 'b' est le facteur de branchement et 'm' est la profondeur maximale de l'arbre de recherche. Elle explore de nombreux noeuds.

Signup and view all the flashcards

Complexité spatiale (Recherche gloutonne)

La complexité spatiale de la recherche gloutonne est de O(bm), où 'b' est le facteur de branchement et 'm' est la profondeur maximale de l'arbre de recherche. Elle explore de nombreux noeuds.

Signup and view all the flashcards

Algorithme A*

L'algorithme A* est une stratégie de recherche heuristique qui utilise une fonction d'évaluation f(n) = g(n) + h(n) pour estimer le coût total d'un nœud. Il trouve généralement une solution optimale.

Signup and view all the flashcards

Coût du chemin déjà parcouru (A*)

Dans l'algorithme A*, g(n) représente le coût du chemin déjà parcouru du nœud initial au nœud courant n.

Signup and view all the flashcards

Coût estimé (A*)

Dans l'algorithme A*, h(n) représente le coût estimé pour atteindre la solution à partir du nœud courant n.

Signup and view all the flashcards

Fonction d'évaluation (A*)

La fonction d'évaluation f(n) dans l'algorithme A* représente le coût total estimé pour atteindre la solution en passant par le nœud courant n. Elle est la somme de g(n) et h(n).

Signup and view all the flashcards

Heuristique admissible

Une heuristique est dite admissible si elle ne surestime jamais le coût réel pour atteindre la solution.

Signup and view all the flashcards

Garantir l'optimalité (A*)

L'algorithme A* est garanti de trouver une solution optimale si l'heuristique est admissible et que le coût du chemin est monotone.

Signup and view all the flashcards

Exemple d'application: Affectation de tâches

L'affectation de tâches aux employés est un exemple d'application de l'algorithme A* utilisé pour maximiser l'efficacité et le rendement.

Signup and view all the flashcards

Recherche heuristique: Importance

La recherche heuristique est une branche de l'intelligence artificielle qui vise à développer des techniques pour trouver des solutions acceptables pour des problèmes complexes.

Signup and view all the flashcards

Applications de la recherche heuristique

Les algorithmes heuristiques sont utilisés dans de nombreuses applications d'intelligence artificielle, notamment la planification, l'apprentissage automatique et le traitement du langage naturel.

Signup and view all the flashcards

Recherche heuristique: Futur

La recherche heuristique est un domaine de recherche actif qui vise à développer des techniques plus efficaces et plus robustes pour résoudre des problèmes complexes.

Signup and view all the flashcards

Fonction d'évaluation

Une fonction d'évaluation mesure la qualité d'un nœud dans un espace de recherche. Elle est utilisée pour guider le processus de recherche vers des solutions prometteuses.

Signup and view all the flashcards

Recherche heuristique: Techniques de recherche

La recherche heuristique utilise des techniques de recherche pour explorer les espaces de recherche et trouver des solutions acceptables aux problèmes.

Signup and view all the flashcards

Avantages de la recherche heuristique

La recherche heuristique permet de trouver des solutions en utilisant des règles empiriques et des approximations, offrant ainsi des solutions acceptables mais pas nécessairement optimales.

Signup and view all the flashcards

Domaines d'applications de la recherche heuristique

La recherche heuristique peut être utilisée dans différents domaines tels que la planification, l'optimisation, la robotique et la résolution de problèmes informatiques complexes.

Signup and view all the flashcards

Recherche heuristique: Conclusion

La recherche heuristique est une approche pragmatique pour résoudre des problèmes complexes qui permet de trouver des solutions acceptables, même si elles ne sont pas optimales.

Signup and view all the flashcards

Objectif de la recherche heuristique

La recherche heuristique utilise des techniques pour explorer un espace de recherche et trouver des solutions acceptables, même si elles ne sont pas toujours optimales.

Signup and view all the flashcards

L'heuristique pour les problèmes complexes

L'heuristique peut être utilisée pour résoudre des problèmes qui n'ont pas de solution algorithmique connue ou pour réduire le temps de calcul pour trouver une solution.

Signup and view all the flashcards

La recherche heuristique et l'exploration

La recherche heuristique utilise des techniques de recherche pour explorer un espace de recherche et trouver des solutions acceptables, même si elles ne sont pas toujours optimales.

Signup and view all the flashcards

La recherche heuristique: un domaine en évolution

La recherche heuristique est un domaine de recherche actif qui vise à développer des techniques plus efficaces et plus robustes pour résoudre des problèmes complexes.

Signup and view all the flashcards

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.

Quiz Team

Related Documents

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.

More Like This

Use Quizgecko on...
Browser
Open
Browser
Browser