: Calcul des coûts et suivi de l'heuristique - mannequins

Souvent, vous trouvez une approche heuristique, celle qui repose sur la découverte de soi et produit des résultats suffisamment utiles (pas nécessairement optimaux, mais assez bons) est la méthode dont vous avez réellement besoin pour résoudre un problème. Obtenir l'algorithme pour effectuer une partie du travail requis pour vous permet d'économiser du temps et des efforts, car vous pouvez créer des algorithmes qui voient les modèles mieux que les humains. Par conséquent, la découverte de soi est le processus qui permet à l'algorithme de vous montrer un chemin potentiellement utile vers une solution (mais vous devez toujours compter sur l'intuition humaine et la compréhension pour savoir si la solution est la bonne). Les sections suivantes décrivent les techniques que vous pouvez utiliser pour calculer le coût d'un algorithme en utilisant l'heuristique comme méthode de découverte de l'utilité réelle d'une solution donnée.

Représentation du problème en tant qu'espace

Un espace de problème

est un environnement dans lequel une recherche de solution a lieu. Un ensemble d'états et les opérateurs utilisés pour changer ces états représentent l'espace du problème. Par exemple, considérez un jeu de tuile qui a huit tuiles dans un cadre 3-x-3. Chaque mosaïque montre une partie d'une image, et les mosaïques commencent dans un ordre aléatoire de sorte que l'image est brouillée. Le but est de déplacer une tuile à la fois pour placer toutes les tuiles dans le bon ordre et révéler l'image.

La combinaison de l'état de départ, des tuiles aléatoires et de l'état du but - les tuiles dans un ordre particulier - est l'instance de problème

. Vous pouvez représenter graphiquement le puzzle en utilisant un graphique d'espace de problème. Chaque nœud du graphe d'espace de problème présente un état (les huit tuiles dans une position particulière). Les bords représentent des opérations, telles que déplacer la tuile numéro huit vers le haut. Lorsque vous déplacez la tuile huit, l'image change - elle passe à un autre état.

Gagner la partie en passant de l'état de départ à l'état de but n'est pas la seule considération. Pour résoudre le jeu efficacement, vous devez effectuer la tâche en un minimum de mouvements, ce qui signifie utiliser le plus petit nombre d'opérateurs. Le nombre minimum de mouvements utilisés pour résoudre le puzzle est la profondeur du problème

. Vous devez tenir compte de plusieurs facteurs lorsque vous représentez un problème en tant qu'espace. Par exemple, vous devez prendre en compte le nombre maximal de nœuds pouvant entrer en mémoire, ce qui représente la complexité de l'espace

. Lorsque vous ne pouvez pas insérer tous les nœuds en mémoire à la fois, l'ordinateur doit stocker certains nœuds dans d'autres emplacements, tels que le disque dur, ce qui peut considérablement ralentir l'algorithme.Pour déterminer si les nœuds entreront en mémoire, vous devez tenir compte de la complexité temporelle,, soit le nombre maximal de nœuds créés pour résoudre le problème. En outre, il est important de prendre en compte le facteur de branchement,, qui est le nombre moyen de nœuds créés dans le graphique d'espace de problème pour résoudre un problème. Aller au hasard et être béni par la chance

Résoudre un problème de recherche en utilisant des techniques de force brute est possible. L'avantage de cette approche est que vous n'avez besoin d'aucune connaissance spécifique au domaine pour utiliser l'un de ces algorithmes. Un algorithme de force brute a tendance à utiliser l'approche la plus simple possible pour résoudre le problème. L'inconvénient est qu'une approche par force brute ne fonctionne bien que pour un petit nombre de nœuds. Voici quelques-uns des algorithmes courants de recherche en force brute:

Recherche en largeur:

Cette technique commence au niveau du nœud racine, explore d'abord chacun des nœuds enfants et ensuite seulement descend au niveau suivant. Il progresse niveau par niveau jusqu'à ce qu'il trouve une solution. L'inconvénient de cet algorithme est qu'il doit stocker tous les nœuds en mémoire, ce qui signifie qu'il utilise une quantité considérable de mémoire pour un grand nombre de nœuds. Cette technique peut vérifier les noeuds en double, ce qui fait gagner du temps, et elle trouve toujours une solution. Depth-first search:
Cette technique commence au nœud racine et explore un ensemble de nœuds enfants connectés jusqu'à ce qu'il atteigne un nœud feuille. Il progresse branche par branche jusqu'à trouver une solution. L'inconvénient de cet algorithme est qu'il ne peut pas vérifier les nœuds en double, ce qui signifie qu'il peut traverser les mêmes chemins de nœuds plusieurs fois. En fait, cet algorithme peut ne pas trouver de solution du tout, ce qui signifie que vous devez définir un point de coupure pour empêcher l'algorithme de chercher à l'infini. Un avantage de cette approche est qu'elle est efficace sur le plan de la mémoire. Recherche bidirectionnelle:
Cette technique recherche simultanément depuis le nœud racine et le nœud cible jusqu'à ce que les deux chemins de recherche se rencontrent au milieu. Un avantage de cette approche est qu'elle est efficace dans le temps car elle trouve la solution plus rapidement que beaucoup d'autres solutions de force brute. En outre, il utilise la mémoire plus efficacement que les autres approches et trouve toujours une solution. Le principal inconvénient est la complexité de la mise en œuvre, qui se traduit par un cycle de développement plus long. Utilisation d'une heuristique et d'une fonction de coût

Pour certaines personnes, le mot

heuristique semble compliqué. Il serait aussi facile de dire que l'algorithme fait une supposition éclairée, puis réessaye quand il échoue. Contrairement aux méthodes de force brute, les algorithmes heuristiques apprennent. Ils utilisent également des fonctions de coût pour faire de meilleurs choix. Par conséquent, les algorithmes heuristiques sont plus complexes, mais ils ont un avantage distinct dans la résolution de problèmes complexes. Comme avec les algorithmes de force brute, il existe de nombreux algorithmes heuristiques et chacun a son propre ensemble d'avantages, d'inconvénients et d'exigences particulières. La liste suivante décrit quelques-uns des algorithmes heuristiques les plus courants: Recherche heuristique pure:

L'algorithme développe les nœuds dans l'ordre de leur coût.Il maintient deux listes. La liste fermée contient les nœuds qu'elle a déjà explorés; la liste ouverte contient les noeuds qu'elle doit encore explorer. Dans chaque itération, l'algorithme développe le nœud avec le coût le plus bas possible. Tous ses nœuds enfants sont placés dans la liste fermée et les coûts de chaque nœud enfant sont calculés. L'algorithme renvoie les noeuds enfants à faible coût à la liste ouverte et supprime les noeuds enfants avec un coût élevé. Par conséquent, l'algorithme effectue une recherche intelligente et basée sur les coûts pour la solution. A * search:
L'algorithme suit le coût des nœuds en les explorant à l'aide de l'équation: f (n) = g (n) + h (n), où n
- est l'identifiant du nœud. g
- (n) est le coût d'accès au nœud jusqu'à présent. h
- (n) est le coût estimé pour atteindre l'objectif à partir du nœud. f
- (n) est le coût estimé du chemin de n vers le but. L'idée est de chercher d'abord les chemins les plus prometteurs et d'éviter les chemins coûteux.

Meilleure recherche gourmande: