Stratégies Informées en Recherche Heuristique

True (A)

True (A)

Le but des algorithmes de recherche heuristique est d'utiliser des fonctions heuristiques pour améliorer le processus de recherche.

<p>False (B)</p> Signup and view all the answers

<p>Un exemple de mesure d'utilité utilisée dans la recherche gloutonne est la distance à vol d'oiseau.</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

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

<p>Dans cette formule, g(n) représente le coût de l'état initial jusqu'à n, h(n) est l'heuristique estimant le coût de n à l'état final, et f(n) est une fonction pour prioriser les états.</p> Signup and view all the answers

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

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

<p>False (B)</p> Signup and view all the answers

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

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

Ces stratégies utilisent des règles pour évaluer la probabilité qu'un chemin vers la solution soit meilleur que les autres.

Fonction utilisée dans les algorithmes heuristiques pour estimer le coût d'un état donné.

L'algorithme choisit le nœud le plus prometteur pour le développer en se basant sur l'heuristique.

L'heuristique aide à déterminer quels opérateurs appliquer pour générer les successeurs d'un nœud.

L'heuristique permet de décider quels nœuds ignorer, réduisant ainsi le temps de recherche.

L'heuristique fournit une solution réalisable rapidement, mais pas nécessairement optimale, pour un problème complexe.

Algorithmes qui cherchent la meilleure solution à chaque étape, sans tenir compte du chemin parcouru.

Algorithme qui combine l'heuristique avec le coût du chemin déjà parcouru.

La mesure d'utilité de l'algorithme glouton ne dépend que de l'état actuel, pas du chemin.

Exemple de mesure d'utilité en recherche gloutonne : la distance à vol d'oiseau entre deux villes.

L'algorithme glouton peut être incomplet car il peut créer des boucles.

La complexité en temps de la recherche gloutonne est exponentielle en fonction du nombre d'états.

La complexité en espace de la recherche gloutonne est exponentielle en fonction du nombre d'états.

La solution trouvée par la recherche gloutonne n'est pas nécessairement optimale.

Exemple de problème d'optimisation : trouver la meilleure combinaison de pièces pour un montant donné.

La stratégie gloutonne consiste à choisir la pièce de plus grande valeur possible à chaque étape.

La solution optimale pour rendre 26 unités avec des pièces de 1, 2, 5, 10, 20 est 1 pièce de 20, 1 pièce de 5 et 1 pièce de 1.

Illustration du comportement de la recherche gloutonne : ne trouve pas toujours la solution optimale.

L'heuristique A* est admissible si l'estimation du coût est toujours inférieure ou égale au coût réel.

L'algorithme A* est complet, ce qui signifie qu'il trouvera toujours une solution si elle existe.

La complexité en temps de l'algorithme A* est exponentielle en fonction du nombre d'états.

La complexité en espace de l'algorithme A* est exponentielle en fonction du nombre d'états.

L'algorithme A* est optimal, ce qui signifie qu'il trouvera toujours la solution la moins coûteuse si elle existe.

Exemple d'heuristique utilisée pour le jeu du taquin, qui compte le nombre de pièces mal placées.

Exemple d'heuristique pour le taquin, qui calcule la somme des distances de chaque pièce à sa position finale.

Exemple d'heuristique pour le taquin, qui combine h2 avec un score basé sur la position des pièces sur les bords et au centre.

Les algorithmes de recherche aveugle peuvent être très coûteux en temps et en espace.

Les algorithmes heuristiques permettent de réduire le temps de recherche en éliminant les branches non prometteuses.