Algorithmes de recherche non informée et informée

Un problème de recherche décrit des choix avant qu’un algorithme ne commence à les faire. Sa formulation détermine à la fois ce que signifie une solution et le nombre de possibilités que l’algorithme doit examiner.

Définir le problème

Il comporte six éléments :

• Les états décrivent les situations possibles.
• L’état initial est celui où la recherche commence.
• Les actions sont les choix disponibles dans un état.
• Le modèle de transition, $\text{R}\acute{\text{E}}\text{SULTAT}(s,a)$, donne l’état après l’action $a$.
• Le test de but reconnaît un état acceptable.
• La fonction de coût d’action, $c(s,a,s^{\mathrm{\prime }})$, attribue un coût à chaque étape.

Tous les coûts d’action sont ici strictement positifs. Une solution à un problème de recherche de chemin est une séquence d’actions qui mène à un but. Additionne les coûts de ses actions pour obtenir son coût de chemin. Une solution optimale en coût minimise cette somme. Nommer simplement la destination n’indique pas à un agent comment l’atteindre.

Formuler le taquin à 8 cases

Une grille contient huit tuiles numérotées et une case vide. L’état indique les neuf positions. L’état initial est la configuration fournie ; le but est « 1 2 3 / 4 5 6 / 7 8 case vide ». Une action déplace la case vide à gauche, à droite, en haut ou en bas lorsque ce déplacement reste dans la grille. La transition échange la case vide avec la tuile voisine, et chaque déplacement coûte 1. Un coin permet deux actions ; le centre en permet quatre.

Une solution est une séquence comme « gauche, haut, droite », si ces déplacements sont autorisés et atteignent le but. Comme chaque déplacement a le même coût, minimiser le coût revient à minimiser le nombre de déplacements.

Choisir l’espace d’états

Représente les états par les sommets d’un graphe orienté et les actions par des arcs associés à leur coût. Une route à double sens donne deux arcs orientés. Pour une recherche d’itinéraire, un état peut être le lieu courant et le coût d’une étape peut être la distance routière en kilomètres.

L’abstraction laisse de côté les détails sans importance. La musique qui joue dans une voiture n’a pas besoin de faire partie d’un état pour un itinéraire. Une solution abstraite doit rester réalisable. Supprimer un détail qui change les actions autorisées modifierait le problème au lieu de simplement simplifier sa description.

La formulation peut économiser plus de travail qu’une file plus rapide. Placer huit dames sur n’importe quelles cases vides donne $64\times 63\times \cdots \times 57\approx \mathrm{1,8}\times {10}^{14}$ séquences ordonnées de placement possibles. Placer chaque nouvelle dame dans la colonne vide la plus à gauche, sur une case non attaquée, laisse 2 057 états accessibles. Ce sont deux constructions différentes d’une même condition de but.

Générer les possibilités au besoin

Le taquin à 8 cases possède $9!\mathrm{/}2=181440$ états accessibles depuis un départ fixé. Le taquin à 15 cases en possède $16!\mathrm{/}2\approx \mathrm{1,05}\times {10}^{13}$. Une représentation complète des 8 dames avec une dame par colonne comporte $8^8=16777216$ états.

Ces espaces sont généralement fournis de façon implicite : la recherche reçoit un état initial et des procédures pour les actions et les transitions. Elle génère la partie pertinente au cours de son exécution. Pour un problème de chemin, conserve la séquence d’actions. Pour un problème d’optimisation comme le placement des dames, la disposition finale elle-même peut être la réponse.

L’espace d’états décrit ce qui est possible. L’arbre de recherche représente les chemins que l’algorithme a essayés. Plusieurs nœuds peuvent décrire le même état parce qu’ils y sont arrivés par des chemins différents.

Stocker un chemin dans un nœud

Un nœud stocke un état, son nœud parent, l’action issue de ce parent et le coût de chemin $g(n)$. La profondeur peut aussi être stockée. La racine n’a pas de parent et son coût de chemin est de 0. Développer un nœud consiste à appliquer toutes les actions autorisées à son état et à générer ses enfants.

Sur une carte à double sens, les chemins « S, A » et « S, B, C, A » aboutissent au même état mais donnent des nœuds différents. Même une carte finie peut générer un arbre de recherche infini : « S, A, S, A, … » produit sans cesse des chemins plus longs.

La frontière contient les nœuds générés qui attendent d’être développés. L’ensemble des états atteints enregistre les états générés et le meilleur nœud trouvé pour chacun. Il comprend aussi bien les états encore dans la frontière que ceux déjà développés. Un ensemble fermé ou exploré désigne généralement seulement les états développés.

Exécuter la procédure générale du meilleur d’abord

1. Placer la racine dans la frontière et la table des états atteints.
2. Si la frontière est vide, renvoyer un échec.
3. Retirer le nœud dont la valeur d’évaluation $f(n)$ est la plus faible.
4. Si son état est un but, renvoyer ce nœud.
5. Le développer. Ajouter chaque nouvel état ; pour un état déjà atteint, ne remplacer son nœud enregistré que si le nouveau chemin est moins coûteux.
6. Recommencer à l’étape 2.

Un chemin moins coûteux vers un état déjà développé peut nécessiter sa réouverture. Les retours de coût égal n’apportent aucune amélioration. Avec un tas, une ancienne entrée peut rester physiquement présente ; elle doit être reconnue comme périmée et ignorée lors de son extraction.

La règle de gestion de la frontière détermine la stratégie. Une file FIFO sélectionne les nœuds de faible profondeur pour la recherche en largeur d’abord. Une pile LIFO sélectionne les nœuds profonds pour la recherche en profondeur d’abord. Des files de priorité ordonnées selon $g$, $h$ et $g+h$ donnent respectivement la recherche à coût uniforme, la recherche gloutonne et A*.

Suivre les nœuds sur la carte routière

Utilise ces routes à double sens, avec des distances en kilomètres : S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 et D–G 2. Pars de S et cherche G. Départage les ex æquo par ordre alphabétique.

Le développement de S génère A de coût 2, B de coût 3 et D de coût 9. Chacun a S pour parent. La frontière contient A, B et D ; la table des états atteints contient aussi S. Plus tard, C peut être atteint par A pour un coût de 6 ou par B pour un coût de 4. Ce sont deux nœuds pour un seul état, et le moins coûteux doit représenter C.

Pour reconstituer une solution, suis à rebours les liens vers les parents depuis le nœud but renvoyé et inverse les actions. Mettre à jour le coût sans mettre à jour le parent laisserait un chemin qui ne correspondrait pas au coût indiqué.

Décider quoi mémoriser

La recherche dans un graphe mémorise les états atteints pour éviter de répéter du travail. La recherche en arbre ne possède pas de table globale des états atteints ; elle peut se limiter à rejeter les cycles sur le chemin courant. Elle économise de la mémoire mais peut générer le même état par de nombreux chemins.

La procédure générale teste les buts à l’extraction. La recherche en largeur d’abord peut les tester à la génération, car celle-ci suit l’ordre des profondeurs. Une recherche fondée sur le coût doit attendre l’extraction : le premier but généré peut avoir un chemin plus coûteux qu’un but trouvé plus tard.

Un algorithme peut être fiable tout en étant trop coûteux à exécuter. Évalue ses garanties séparément de sa consommation de ressources, puis vérifie si ces garanties correspondent au problème que tu dois réellement résoudre.

Poser quatre questions différentes

La complétude signifie trouver une solution dès qu’il en existe une. Dans un espace d’états accessibles fini, épuiser toutes les possibilités peut aussi prouver l’échec. Un espace infini sans solution peut être exploré indéfiniment, même par un algorithme complet.

L’optimalité en coût signifie renvoyer une solution dont le coût de chemin est le plus faible. Elle ne dit rien de la vitesse d’exécution de l’algorithme. Une méthode peut trouver une solution de façon fiable tout en renvoyant un itinéraire coûteux.

La complexité temporelle compte les nœuds générés ou développés. Précise quel décompte est utilisé lorsque tu compares des mesures. La complexité spatiale mesure le nombre maximal de nœuds conservés simultanément, y compris la frontière et les informations de recherche stockées.

Identifier les paramètres

Pour un espace de recherche implicite, utilise :

Pour un graphe explicite déjà en mémoire, les nombres de sommets et d’arcs sont généralement plus utiles. Une borne de parcours en $\mathrm{\mid }V\mathrm{\mid }$ et $\mathrm{\mid }E\mathrm{\mid }$ répond à une question différente de celle d’une borne pour la génération d’un arbre encore inconnu.

Comprendre pourquoi la profondeur coûte cher

Un arbre complet jusqu’à la profondeur $d$ contient

nœuds pour $b\mathrm{\ne }1$. Avec un facteur de branchement de 10 et une profondeur de 5, cela fait 111 111 nœuds, racine comprise. Augmenter la profondeur de un ajoute une couche qui comporte dix fois plus de nœuds que la précédente.

À raison d’un million de nœuds par seconde et de 1 kilooctet par nœud, les ordres de grandeur changent rapidement :

Ce sont des unités de stockage décimales : 1 Go vaut ${10}^9$ octets. La mémoire peut rendre une recherche impossible bien avant que son temps d’exécution ne semble déraisonnable.

Lire les garanties avec leurs conditions

La recherche en largeur d’abord atteint à terme toute profondeur finie lorsque le branchement est fini. La recherche en profondeur d’abord peut passer un temps infini sur une seule branche et ne jamais essayer un but proche. Cette différence explique leurs résultats en matière de complétude.

La recherche en largeur d’abord trouve un chemin avec le moins d’actions. Si un itinéraire de deux étapes coûte 11 km et un itinéraire de trois étapes coûte 9 km, l’itinéraire le moins profond n’est pas optimal en coût. Des coûts d’étape égaux font correspondre profondeur et coût ; des coûts différents peuvent les dissocier.

Une borne grand O dans le pire des cas ne prédit pas chaque exécution. Deux méthodes ayant la même borne peuvent différer par leurs constantes, leur traitement des doublons et le nombre de branches utiles. Une heuristique peut grandement améliorer une exécution habituelle sans supprimer le pire des cas exponentiel.

La recherche en largeur d’abord explore par couches. Le prochain nœud développé est celui de plus faible profondeur qui attend encore : ainsi, chaque chemin à une action est examiné avant qu’un chemin à deux actions soit développé.

Maintenir l’ordre de la file

La frontière fonctionne selon le principe premier entré, premier sorti : retirer en tête et ajouter les enfants en fin de file. Enregistre les états lorsqu’ils sont générés. Si l’état d’un enfant a déjà été atteint, ignore-le ; sinon, deux parents différents pourraient placer le même état dans la file.

Teste l’état initial avant la recherche. Pour les nœuds suivants, la recherche en largeur d’abord peut utiliser un test de but à la génération. Le premier but généré est de profondeur minimale, car l’algorithme génère les enfants couche par couche. L’ordre au sein d’une couche peut départager des solutions de même profondeur, mais ne peut pas faire apparaître en premier une solution plus profonde.

Suivre le déroulement sur la carte

Les routes à double sens sont S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 et D–G 2 km. Pars de S, cherche G et génère les voisins par ordre alphabétique. Dans le tableau, le prochain nœud à retirer est à gauche.

Lorsque B est développé, C et D sont déjà atteints. Ils ne changent pas de place dans la file. Lorsque D génère G, sa chaîne de parents est G–D–S. Inverse-la pour retrouver S–D–G, avec deux routes et une distance totale de $9+2=11$ km.

C a déjà été généré, mais n’a pas été développé. Son itinéraire vers G comporterait trois routes. La recherche en largeur d’abord peut s’arrêter sans l’explorer, car trois routes ne peuvent pas améliorer le nombre d’actions d’une solution à deux routes.

Savoir ce que le résultat minimise

La recherche en largeur d’abord est complète pour un branchement fini, même si l’espace est infini : chaque couche finie est traitée avant la suivante. Elle est optimale en coût lorsque toutes les actions ont le même coût. Dans un taquin où chaque déplacement coûte 1, une solution de profondeur minimale est aussi une solution de coût minimal.

Sur cette carte routière, S–B–C–G coûte $3+1+5=9$ km. La recherche en largeur d’abord renvoie l’itinéraire de 11 km parce que la distance n’est pas son critère d’ordonnancement. Il faut donc préciser l’unité de « plus court chemin » : le moins de routes et le moins de kilomètres sont des objectifs différents.

Tenir compte de la mémoire

Avec un test de but à la génération, la recherche en largeur d’abord a des complexités temporelle et spatiale en $O(b^d)$. Elle peut générer presque tous les nœuds jusqu’à la profondeur du but et conserver la frontière ainsi que les informations sur les états atteints. Si les buts ne sont testés qu’à l’extraction, le développement d’autres nœuds de profondeur $d$ peut générer la profondeur $d+1$, ce qui donne la borne habituelle $O(b^{d+1})$ pour cette version.

Avec un facteur de branchement de 10 et 1 kilooctet par nœud, stocker un arbre jusqu’à la profondeur 10 prend environ 11 To. La recherche en largeur d’abord est utile pour les problèmes de faible profondeur à coûts égaux lorsque la mémoire est suffisante, comme les chemins à nombre minimal de sauts dans un réseau ou les taquins à nombre minimal de déplacements. Une file FIFO n’utilise pas les coûts numériques des arcs, même lorsqu’ils sont inscrits sur le graphe.

La recherche à coût uniforme ordonne les chemins selon le coût déjà engagé. Elle peut laisser de côté une destination proche mais coûteuse pendant qu’elle examine des itinéraires plus longs composés d’étapes peu coûteuses.

Retirer le chemin le moins coûteux

Pose $f(n)=g(n)$ et utilise une file de priorité. Lorsqu’un développement trouve un chemin moins coûteux vers un état atteint, mets à jour son coût et son parent. Un chemin de coût égal n’améliore pas l’enregistrement. La recherche à coût uniforme est la forme de recherche de l’algorithme de Dijkstra ; elle s’arrête lorsqu’elle retire un but.

Le test de but à l’extraction est essentiel. Générer un but prouve qu’un itinéraire existe. Retirer ce but en tant que nœud le moins coûteux de la frontière prouve qu’aucun itinéraire inachevé moins coûteux ne peut le surpasser, puisque les coûts des actions sont strictement positifs.

Suivre le déroulement sur la carte

Utilise les routes à double sens S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 et D–G 2 km. Départage les coûts égaux par ordre alphabétique. Les entrées de la frontière ci-dessous indiquent l’état et le coût du chemin.

Le remplacement de C est décisif : $3+1=4$ est meilleur que $2+4=6$. Le parent de G est C, celui de C est B et celui de B est S. L’itinéraire renvoyé S–B–C–G coûte 9 km. D est retiré avant G uniquement parce que la règle de départage est alphabétique.

Si une route directe S–G de 12 km était ajoutée, S générerait immédiatement un but. Un test à la génération renverrait 12 km avant de découvrir l’itinéraire de 9 km. La file de priorité ne peut pas préserver l’optimalité si la règle d’arrêt la contourne.

Expliquer la garantie

Avec un branchement fini et un coût pour chaque action au moins égal à un certain $ϵ>0$, seul un nombre fini d’étapes d’un chemin peut tenir sous une borne de coût fixe. La recherche à coût uniforme finit donc par retirer un but dès qu’il en existe un. Les coûts strictement positifs garantissent que prolonger un chemin ne peut pas le rendre moins coûteux, ce qui étaye la preuve d’optimalité.

Les coûts nuls demandent de l’attention. La recherche en arbre peut parcourir indéfiniment un cycle de coût nul. La recherche dans un graphe rejette les retours de coût égal vers un même état, mais une chaîne infinie d’états distincts dont le coût cumulé est borné peut encore retarder indéfiniment un but. Des coûts d’étape négatifs invalident l’argument habituel d’optimalité de la recherche à coût uniforme.

Comprendre le coût

La borne habituelle des complexités temporelle et spatiale dans le pire des cas est $O(b^{1+\lfloor C^{\ast }\mathrm{/}ϵ\rfloor })$. Sur cette carte, $C^{\ast }=9$ et $ϵ=1$, ce qui donne $O(b^{10})$. C’est une borne large, et non le nombre de nœuds réellement développés sur la carte à six états.

De nombreux chemins peu coûteux menant à des impasses peuvent obliger la recherche à coût uniforme à effectuer beaucoup de travail avant de prendre une action utile coûteuse. Lorsque tous les coûts d’étape sont égaux, son test de but à l’extraction donne la borne habituelle $O(b^{d+1})$. A* avec $h=0$ effectue exactement les mêmes comparaisons de priorité que la recherche à coût uniforme.

La recherche en profondeur d’abord suit une branche avant d’essayer les autres. Ce choix peut réduire considérablement la mémoire nécessaire, mais une branche mal choisie peut retarder l’examen de toutes les autres possibilités.

Suivre une branche en profondeur

La recherche en profondeur d’abord utilise une pile dernier entré, premier sorti. Dans une version en arbre, rejette les états déjà présents sur le chemin courant pour éviter de former immédiatement un cycle. Stocke le chemin courant et les frères non développés de ses nœuds. Pour essayer les successeurs par ordre alphabétique avec une pile, empile-les dans l’ordre alphabétique inverse.

Sur la carte à double sens S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 et D–G 2 km, pars de S et cherche G. En essayant les voisins par ordre alphabétique et en testant les buts à l’extraction, on obtient S, A, C, B, D, G. En C, B est le premier voisin qui ne figure pas déjà sur le chemin. L’itinéraire renvoyé S–A–C–B–D–G coûte $2+4+1+6+2=15$ km.

La recherche en profondeur d’abord n’est pas optimale en coût. Elle est complète dans un espace fini avec détection des cycles sur le chemin, mais elle peut suivre une branche infinie indéfiniment. Sa complexité temporelle dans le pire des cas est en $O(b^m)$ et le stockage des chemins et des frères nécessite un espace en $O(bm)$. Le retour arrière qui génère un enfant à la fois réduit le stockage à $O(m)$. Avec un facteur de branchement de 10 et une profondeur maximale de 12, le stockage du chemin et des frères représente environ 120 nœuds, contre environ un billion pour la recherche en largeur d’abord jusqu’à la profondeur 12. Une table globale des états atteints utiliserait de la mémoire supplémentaire.

Limiter la profondeur

La recherche à profondeur limitée cesse de développer les nœuds à la profondeur $\mathrm{\ell }$. Un but à cette profondeur peut tout de même être reconnu. Elle distingue trois résultats :

• Une solution a été trouvée.
• Coupure : la profondeur limite a empêché une recherche complète.
• Échec : les possibilités pertinentes ont été épuisées sans but ni coupure.

Une coupure ne prouve pas qu’il n’existe aucune solution. Si le but de profondeur minimale est à la profondeur 7, une limite de 5 ne permet pas de l’atteindre. Dans le pire des cas, les complexités temporelle et spatiale sont respectivement en $O(b^{\mathrm{\ell }})$ et $O(b\mathrm{\ell })$.

Augmenter progressivement la limite

La recherche par approfondissement itératif exécute des recherches à profondeur limitée avec les limites 0, 1, 2 et ainsi de suite. Elle trouve une solution de profondeur minimale sans stocker une frontière de recherche en largeur. Avec un branchement fini, elle est complète ; avec des coûts d’action égaux, elle est optimale en coût. Sa complexité temporelle est en $O(b^d)$ et sa complexité spatiale en $O(bd)$.

La plupart des nœuds d’un arbre large se trouvent dans la dernière couche ; répéter les couches supérieures est donc souvent peu coûteux. Pour $b=10$ et $d=5$, comptons les nœuds générés sous la racine :

La recherche en largeur d’abord génère 111 110 nœuds de ce type jusqu’à la profondeur 5. L’approfondissement itératif effectue environ 11 % de générations en plus tout en ne stockant que les données d’une recherche en profondeur. Les visites répétées de la racine sont exclues de ces deux décomptes particuliers.

Pour des facteurs de branchement supérieurs à 1, le surcoût dans un arbre large tend vers le facteur $b\mathrm{/}(b-1)$. Cet avantage est moindre pour une chaîne étroite, où les préfixes répétés dominent. L’approfondissement itératif est un choix non informé utile lorsque la profondeur de la solution est inconnue et qu’une frontière complète ne tiendrait pas en mémoire. Dans les espaces comportant de nombreux chemins vers un même état, l’absence d’un ensemble global des états atteints peut entraîner de nombreuses régénérations.

Une stratégie utile correspond au résultat recherché et aux ressources disponibles. La recherche non informée utilise la définition du problème sans estimation de la distance restante. Elle peut néanmoins être systématique et soigneusement ordonnée.

Comparer sur une base commune

Supposons un branchement fini et les conditions de coûts strictement positifs pour la recherche à coût uniforme. La ligne de la recherche en largeur d’abord utilise le test de but à la génération ; celle de la recherche en profondeur d’abord utilise la détection des cycles sur le chemin, sans table globale des états atteints.

La recherche en largeur d’abord et l’approfondissement itératif minimisent aussi le coût lorsque celui-ci est une fonction non décroissante de la seule profondeur. Le mot « seule » compte : tous les chemins d’une profondeur donnée doivent avoir le même coût pour que cette condition plus générale soit satisfaite. Des arcs de coût strictement positif ne suffisent pas à rendre la recherche en largeur d’abord optimale en coût.

Chercher depuis les deux extrémités

La recherche bidirectionnelle progresse vers l’avant depuis le départ et à rebours depuis le but. Si les recherches se rencontrent près du milieu, chacune atteint environ la profondeur $d\mathrm{/}2$. Le travail est alors d’environ $2b^{d\mathrm{/}2}$ au lieu de $b^d$. Avec un facteur de branchement de 10 et une solution de profondeur 6, la comparaison des couches principales donne environ 2 000 nœuds contre 1 000 000.

Elle nécessite un état but explicite et un moyen de générer les prédécesseurs. Des routes réversibles à double sens rendent le développement à rebours facile. Une propriété de but comme « aucune dame n’est attaquée » peut décrire trop d’états buts pour fournir un point de départ commode à la recherche inverse.

Avec des recherches en largeur d’abord ou fondées sur le coût, des règles de rencontre et d’arrêt adaptées peuvent préserver la complétude et l’optimalité. Sur une carte pondérée, ne t’arrête que lorsqu’aucune liaison moins coûteuse n’est encore possible. Le premier croisement entre les deux recherches n’est pas nécessairement la liaison la moins coûteuse.

Choisir selon le problème

Pour obtenir le moins de déplacements dans un petit taquin, des coûts de déplacement égaux rendent la recherche en largeur d’abord appropriée si la mémoire est suffisante. Pour un trajet de distance minimale avec des longueurs de route différentes et sans heuristique, choisis la recherche à coût uniforme. Pour un immense taquin à coûts égaux et de profondeur de solution inconnue, l’approfondissement itératif évite une immense frontière. Dans un espace fini comportant de nombreux buts profonds où toute solution convient, la recherche en profondeur d’abord peut être pratique. Un départ et un but connus avec des actions réversibles rendent la recherche bidirectionnelle intéressante à envisager.

La consommation de mémoire doit inclure ce que stocke la version choisie. Une recherche en profondeur d’abord avec une table globale des états atteints n’a plus le même profil de stockage que sa version en arbre. Il ne faut pas comparer un déroulement de recherche en largeur avec test de but à l’extraction à une borne de complexité avec test à la génération comme si les versions étaient identiques.

Même le meilleur choix non informé peut se heurter à une croissance exponentielle. Lorsque des connaissances utiles du domaine sont disponibles, une heuristique peut réduire l’exploration inutile. Lorsque seule une configuration finale compte, la recherche locale peut éviter de conserver un arbre de recherche.

Une heuristique attribue à un état une estimation du coût restant minimal jusqu’à un but. On la note $h(n)$ pour l’état du nœud $n$. Elle dépend de l’état, et non du chemin emprunté pour l’atteindre, et vaut zéro pour un but.

Estimer ce qui reste

La distance à vol d’oiseau estime la distance routière restante. Sur une grille avec des déplacements horizontaux et verticaux d’une case, la distance de Manhattan additionne les différences de coordonnées :

De la case (1 ; 1) à la case (4 ; 5), cela donne $3+4=7$ déplacements. La distance à vol d’oiseau entre les mêmes coordonnées est $\sqrt{3^2+4^2}=5$. Les estimations répondent à des questions différentes sur les déplacements dans des problèmes relaxés. Une heuristique doit utiliser les mêmes unités que le coût qu’elle estime ; des kilomètres n’estiment pas directement un temps de trajet sans modèle de conversion adapté.

La recherche informée utilise une estimation pour guider le développement. L’estimation n’a pas besoin d’indiquer à l’algorithme quelle action effectuer. Elle évalue les états produits par les actions autorisées, et la règle de gestion de la frontière détermine quel chemin en attente examiner ensuite.

Suivre la plus petite estimation

La recherche gloutonne pose $f(n)=h(n)$. Sa file de priorité retire l’état qui semble le plus proche du but, sans tenir compte du coût déjà engagé.

Utilise les routes à double sens S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 et D–G 2 km. Les estimations heuristiques jusqu’à G sont S 8, A 7, B 5, C 4, D 2 et G 0 km.

1. Développer S. La frontière contient A avec une estimation de 7, B avec 5 et D avec 2.
2. Retirer D car 2 est la plus petite valeur. Le développement de D génère G avec une estimation de 0. Le coût du chemin jusqu’à G est de $9+2=11$ km.
3. Retirer G et renvoyer S–D–G.

Seuls S et D ont été développés. L’itinéraire S–B–C–G de 9 km était disponible, mais l’estimation de 5 pour B semblait moins bonne que celle de 2 pour D. La recherche gloutonne n’a jamais inclus les 9 km déjà parcourus pour atteindre D dans sa comparaison.

Distinguer guidage et garanties

Même une heuristique qui ne surestime jamais ne rend pas la recherche gloutonne optimale en coût. Les estimations de l’exemple sont admissibles, mais l’itinéraire renvoyé est trop coûteux. La recherche gloutonne utilise uniquement l’estimation restante ; elle peut donc payer trop cher avant d’atteindre un état prometteur.

La recherche dans un graphe est complète sur un espace d’états fini lorsqu’elle traite correctement les doublons. La recherche gloutonne en arbre peut boucler sur des états répétés qui semblent prometteurs, et un espace infini peut continuer à proposer des estimations faibles mais trompeuses. Dans le pire des cas, les complexités temporelle et spatiale sont en $O(b^m)$, même si une estimation utile peut raccourcir une exécution réelle.

Un lieu peut être proche d’une destination à vol d’oiseau mais nécessiter un long détour autour d’une rivière. De faibles valeurs heuristiques ne garantissent pas de bons itinéraires au total. Le calcul de l’heuristique prend aussi du temps : réduire le nombre de développements n’aide que si l’évaluation de ces estimations n’absorbe pas le temps économisé.

A* évalue l’ensemble du parcours proposé : le coût déjà engagé plus une estimation de ce qui reste. Sa priorité est

Utilise une file de priorité, remplace les chemins plus coûteux et teste un but lorsqu’il est retiré. Pour un but, $h=0$ : sa priorité est donc son coût de chemin réel.

Suivre la règle du coût plus l’estimation

Les routes à double sens sont S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 et D–G 2 km. Les estimations heuristiques jusqu’à G sont S 8, A 7, B 5, C 4, D 2 et G 0. Départage les ex æquo par ordre alphabétique.

A est retiré avant G en raison de la règle de départage. A* développe quatre nœuds qui ne sont pas des buts et ne développe jamais D. La recherche à coût uniforme sur la même carte développe aussi D. Mettre toutes les estimations heuristiques à zéro supprimerait ce guidage et reproduirait la recherche à coût uniforme.

Expliquer pourquoi une estimation optimiste fonctionne

Une heuristique admissible ne dépasse jamais le coût restant réel $h^{\ast }(n)$. Pour A* avec réouverture, l’admissibilité garantit l’optimalité en coût ; A* en arbre offre la même garantie dans les conditions de recherche à coûts strictement positifs.

Supposons qu’un but moins bon de coût $C>C^{\ast }$ soit sur le point d’être retiré. Un nœud d’un chemin optimal doit encore être en attente. Pour le préfixe de son chemin optimal,

La file doit choisir ce nœud avant le but moins bon. Cela contredit le point d’arrêt supposé. La réouverture compte, car un préfixe moins coûteux découvert plus tard doit pouvoir continuer par un état déjà développé.

Une heuristique cohérente rend $f$ non décroissante le long des chemins. Elle garantit que le premier développement d’un état utilise un chemin de coût minimal pour l’atteindre. A* peut alors fermer définitivement les états développés. Avec la seule admissibilité, un ensemble fermé permanent peut écarter une amélioration essentielle.

Comprendre l’élagage et ses limites

Avec la cohérence, A* développe chaque nœud pertinent dont $f<C^{\ast }$, peut développer des nœuds ex æquo à $C^{\ast }$ et n’en développe aucun au-dessus de cette valeur avant de renvoyer le résultat. La priorité 11 de D dépasse le coût de solution 9 : il reste donc non développé. Dans la classe des algorithmes qui construisent des chemins vers l’avant en utilisant les mêmes informations heuristiques, A* est optimalement efficace, hormis les cas d’ex æquo. C’est une comparaison des développements nécessaires, et non l’affirmation que son code s’exécute toujours le plus rapidement.

Une surestimation peut invalider l’argument. Remplace l’estimation de B par 9 alors que son coût restant réel est de 6. B a maintenant une priorité de 12. A*, en suivant S, A, C et D, renvoie S–A–C–G au coût de 11 tandis que B attend encore.

A* conserve un pire des cas exponentiel et stocke les informations de recherche générées.

Lorsque la frontière ne tient plus en mémoire ou qu’une réponse arrive trop lentement, choisis la ressource ou la garantie sur laquelle faire un compromis. Les variantes axées sur la vitesse modifient les priorités ou écartent des candidats. Les variantes axées sur la mémoire régénèrent des chemins qu’elles n’ont pas pu conserver.

Donner plus de poids à l’estimation

A pondéré* utilise $f=g+Wh$ avec $W>1$. Il favorise généralement davantage la progression vers un but. Avec une heuristique admissible, les mises à jour des meilleurs chemins et la réouverture de la procédure générale, le coût renvoyé est au plus $W{C}^{\ast }$. Cette borne permet une solution moins bonne, sans l’imposer.

Sur la carte routière de référence, utilise les estimations S 8, A 7, B 5, C 4, D 2 et G 0, et un poids de 2. Depuis S, les priorités sont B 13, D 13 et A 16. L’ordre alphabétique départage les ex æquo en faveur de B. Son enfant C a $4+2(4)=12$ ; C génère ensuite G avec une priorité de 9. L’itinéraire de coût 9 est renvoyé après trois développements de nœuds qui ne sont pas des buts. La garantie autorise jusqu’à 18 km, même si cette exécution trouve l’optimum.

Dans la même formule, un poids de 0 donne la recherche à coût uniforme et un poids de 1 donne A*. Lorsque le poids devient grand, l’estimation domine de plus en plus les comparaisons et le comportement se rapproche de la recherche gloutonne.

La recherche en faisceau ne conserve que les $k$ meilleurs nœuds en attente et écarte les autres. La frontière conservée est bornée, mais un candidat écarté peut contenir la seule solution. Elle ne garantit donc ni la complétude ni l’optimalité.

Approfondir selon un seuil de coût estimé

IDA* effectue une recherche en profondeur d’abord avec une coupure sur $f=g+h$. Le premier seuil de coupure est la valeur de la racine. Élague tout nœud au-dessus de ce seuil en enregistrant la plus petite valeur qui le dépasse. Cette valeur devient le seuil suivant ; elle n’est pas nécessairement égale à l’ancien seuil plus 1. Utilise la détection des cycles sur le chemin.

Pour la carte de référence, le premier seuil est 8. A à 9 et D à 11 sont élagués ; B et C à 8 sont explorés, mais G à 9 est élagué. Le seuil suivant est 9. Dans cette itération, le chemin par A produit C à 10, qui est élagué. Le chemin S–B–C–G reste dans la limite de 9 et réussit.

Avec l’admissibilité, IDA* préserve l’optimalité en coût et ne nécessite que le stockage d’un chemin en profondeur. Ses passages répétés peuvent être coûteux lorsque les coûts produisent de nombreux seuils distincts. De petits coûts entiers rendent souvent le nombre de seuils plus facile à gérer.

Utiliser la mémoire limitée de façon plus sélective

La recherche récursive du meilleur d’abord (RBFS) stocke la meilleure priorité possible pour une autre branche à chaque niveau. Elle suit la branche la plus prometteuse jusqu’à ce que cette autre possibilité devienne meilleure, puis revient en arrière. Elle utilise une mémoire linéaire mais peut régénérer des branches oubliées.

SMA* utilise la mémoire disponible, supprime la pire feuille de la frontière lorsqu’elle est pleine et reporte sa valeur dans son parent. Cet enregistrement permet une régénération ultérieure. Avec une heuristique admissible, il est optimal en coût si un chemin solution optimal tient en mémoire. Sinon, il peut renvoyer une solution moins bonne ou échouer si aucun chemin solution ne tient en mémoire.

Choisis A* pour une réponse optimale lorsque le stockage suffit. Choisis IDA* ou une variante adaptée à mémoire limitée lorsque l’optimalité compte mais que la frontière ne tient pas en mémoire. A* pondéré offre une borne numérique sur la qualité ; la recherche en faisceau offre un élagage poussé sans cette borne.

Une heuristique peut être globalement optimiste tout en changeant trop brusquement entre des états voisins. L’admissibilité et la cohérence correspondent à ces vérifications distinctes, et chacune permet de justifier une version différente de A*.

Comparer les estimations aux coûts réels

Une heuristique admissible satisfait $0\le h(n)\le h^{\ast }(n)$ dans chaque état. Pour un but, le coût restant réel est nul ; son estimation doit donc aussi être nulle. Admissible ne signifie pas précis : une valeur nulle partout est fiable mais ne fournit aucune direction.

Sur la carte routière de référence, les estimations et les distances restantes minimales exactes jusqu’à G sont :

Chaque estimation est au plus égale à son coût réel. Dans un grand problème, calculer ces coûts exacts peut être aussi difficile que la recherche initiale. Une preuve fondée sur la structure du problème est alors plus utile qu’un tableau exhaustif.

Vérifier chaque action

La cohérence, aussi appelée monotonie, exige $h(n)\le c(n,a,n^{\mathrm{\prime }})+h(n^{\mathrm{\prime }})$ pour chaque action, ainsi qu’une valeur nulle pour les buts. L’estimation courante ne peut pas dépasser le coût d’une étape plus l’estimation du successeur.

Sur la carte routière, A→C donne $7\le 4+4$, C→B donne $4\le 1+5$ et D→G donne $2\le 2+0$. Les routes à double sens exigent de vérifier les deux directions. Les 16 vérifications orientées sont satisfaites pour ces estimations.

Additionner les inégalités le long d’un chemin vers un but annule les estimations intermédiaires. Sur un chemin optimal, on obtient $h(n)\le h^{\ast }(n)$ : la cohérence implique donc l’admissibilité. On obtient aussi

Les priorités ne peuvent pas diminuer le long d’un chemin. Le premier développement d’un état se fait donc sur un chemin de coût minimal, même si sa première génération était plus coûteuse.

Comprendre pourquoi l’admissibilité seule nécessite la réouverture

Considère les routes à double sens S–A 1, A–C 1, S–B 1, B–C 2 et C–G 3. Soient les estimations S 0, A 4, B 1, C 1 et G 0. Elles ne dépassent pas les coûts réels S 5, A 4, B 5, C 3 et G 0 ; elles sont donc admissibles. Mais A→C ne respecte pas la cohérence : $4>1+1$.

A* développe S, puis B avec une priorité de 2, puis C atteint pour un coût de 3 avec une priorité de 4. Il développe ensuite A avec une priorité de 5 et découvre un chemin moins coûteux vers C, de coût 2. Rejeter définitivement C parce qu’il est fermé laisse un but de coût 6. Rouvrir C propage l’amélioration et produit l’optimum, de coût 5.

Adapter l’heuristique au modèle de déplacement

La distance de Manhattan est admissible et cohérente pour des déplacements horizontaux et verticaux d’une case. Si les déplacements en diagonale coûtent aussi 1, aller de (0 ; 0) à (3 ; 3) ne prend que trois déplacements, tandis que la distance de Manhattan donne 6. Pour ce modèle de déplacement, $\max (\mathrm{\mid }\mathrm{\Delta }x\mathrm{\mid },\mathrm{\mid }\mathrm{\Delta }y\mathrm{\mid })$ donne la distance sans obstacle. La garantie d’une heuristique est liée à un modèle d’action particulier.

Pour concevoir une estimation fiable, résous une version plus facile du problème. Un problème relaxé supprime des restrictions sur les actions : toutes les solutions initiales restent donc disponibles. Son coût minimal ne peut pas dépasser celui du problème initial.

Supprimer les restrictions de façon réfléchie

Un coût exact de problème relaxé est une heuristique admissible. Il est aussi cohérent lorsque les actions initiales restent disponibles avec leurs coûts : effectuer une étape initiale puis suivre un itinéraire optimal dans le problème relaxé est un itinéraire possible dans ce problème ; l’optimum relaxé ne peut donc pas coûter plus cher.

Dans le taquin à 8 cases, une tuile ne peut se déplacer vers une case voisine que si cette case est vide. Supprime l’exigence de case vide et les tuiles peuvent traverser les cases occupées. Chaque tuile numérotée doit alors parcourir au moins la somme de ses distances horizontale et verticale jusqu’à sa cible. Leur somme donne la distance de Manhattan, $h_2$.

Supprime aussi l’exigence de voisinage et chaque tuile mal placée peut sauter directement vers sa cible en un déplacement. Le coût obtenu est le nombre de tuiles mal placées, $h_1$. Les deux sont faciles à calculer sans explorer le taquin initial.

Calculer les deux estimations

Pour le but « 1 2 3 / 4 5 6 / 7 8 case vide », considère « 5 1 3 / 4 case vide 2 / 7 8 6 ». Numérote les lignes et les colonnes à partir de 1.

Les autres tuiles numérotées sont déjà à la bonne place. Quatre sont mal placées, donc $h_1=4$. Leurs distances totalisent $2+1+2+1=6$, donc $h_2=6$. La solution optimale prend 12 déplacements ; les relaxations ignorent les interactions qui créent du travail supplémentaire.

Ne compte pas la case vide. À un déplacement du but, une tuile numérotée et la case vide sont toutes deux déplacées. Compter les deux donnerait 2 alors que le coût réel est de 1. La case vide permet les déplacements ; ce n’est pas une tuile supplémentaire à comptabiliser.

Stocker les sous-problèmes résolus

Une base de données de motifs enregistre les coûts exacts d’un sous-problème choisi, par exemple placer correctement les tuiles 1 à 4 en considérant les autres comme interchangeables. Construis la table une fois par une recherche à rebours depuis le but. Pendant une nouvelle recherche, consulte la table au lieu de résoudre à nouveau le sous-problème.

Le sous-problème ne demande pas plus de travail que le problème complet, ce qui fournit une borne inférieure. Cependant, additionner deux coûts de motifs ordinaires peut compter deux fois un même déplacement réel. L’addition est fiable pour des motifs disjoints lorsque chaque base ne compte que les déplacements de ses propres tuiles. Des noms de tuiles disjoints ne suffisent pas à établir cette règle de comptabilisation des coûts.

Combiner des estimations fiables

Le maximum d’estimations admissibles est admissible :

Chaque estimation candidate reste inférieure ou égale au coût restant réel, donc leur maximum aussi. Il est au moins aussi informatif que chacune des estimations prises séparément. Une simple somme n’offre pas cette garantie.

Une heuristique apprise à partir d’exemples résolus peut bien prédire le coût restant en moyenne. La précision moyenne n’établit pas une borne inférieure pour chaque état. Elle ne conserve la garantie de A* associée à une heuristique admissible que si l’on démontre que ses estimations ne surestiment jamais le coût.

Une estimation plus proche du coût réel peut réduire l’exploration, mais une estimation coûteuse peut malgré tout ralentir la recherche. Compare à la fois les informations fournies et le calcul total nécessaire.

Établir la dominance sur chaque état

Une heuristique admissible $h_2$ domine une heuristique admissible $h_1$ si $h_2(n)\ge h_1(n)$ partout. Une grille favorable ne suffit pas à démontrer cette relation.

La distance de Manhattan domine le nombre de tuiles mal placées dans le taquin à 8 cases. Chaque tuile mal placée doit parcourir au moins une case ; sa contribution à la distance de Manhattan est donc au moins égale à 1, la valeur comptée par l’heuristique moins forte. Une tuile correctement placée contribue pour zéro aux deux.

Avec des estimations cohérentes, A* doit développer les chemins tels que $g+h<C^{\ast }$. Augmenter une estimation admissible retire certains chemins de cette région où le développement est obligatoire. Une heuristique cohérente dominante ne développe pas plus de nœuds, hormis les différences dues aux ex æquo. Une estimation non admissible peut être encore plus grande, mais elle fait perdre la garantie d’optimalité et ne remplit pas les conditions de cette comparaison par dominance.

Résumer l’effort de recherche

Le facteur de branchement effectif, $b^{\ast }$, décrit la largeur d’un arbre uniforme équivalent. Compte $N$ nœuds générés sous la racine et note $d$ la profondeur de la solution. Résous

Le 1 supplémentaire correspond à la racine. Il faut compter de manière cohérente : si une mesure inclut déjà la racine, ne l’ajoute pas deux fois.

Pour 52 nœuds générés sous la racine et une solution de profondeur 5, le total est de 53 et $b^{\ast }\approx \mathrm{1,92}$. Pour 1 000 nœuds générés et une profondeur de 8, $b^{\ast }\approx \mathrm{2,20}$. Détermine ces valeurs numériquement en augmentant ou en diminuant une valeur d’essai jusqu’à ce que sa somme géométrique corresponde au nombre total de nœuds.

Une valeur proche de 1 indique une recherche étroite. Compare les résultats sur des instances représentatives, avec la même règle de décompte et des profondeurs de solution comparables. Le facteur de branchement effectif peut aider à estimer le passage à l’échelle, mais une instance exceptionnellement facile ne permet pas de prévoir de façon fiable le comportement sur toute une famille de problèmes.

Chronométrer l’ensemble du calcul

Supposons qu’un nœud prenne 10 microsecondes, dont 1 microseconde pour évaluer l’ancienne heuristique. Une heuristique de remplacement divise le nombre de nœuds par deux mais prend 100 microsecondes par évaluation. Le travail hors heuristique coûte toujours 9 microsecondes, donc le nouveau total par nœud est de 109. Le rapport des temps totaux est

La recherche est environ 5,5 fois plus lente malgré la visite d’un nombre inférieur de nœuds. Si la nouvelle évaluation ne prend que 2 microsecondes, le total par nœud passe à 11 et le rapport des temps est de $\mathrm{0,5}\times 11\mathrm{/}10=\mathrm{0,55}$. La recherche est alors environ 1,8 fois plus rapide.

Une base de données de motifs a aussi un coût de construction. De nombreuses recherches ayant le même but peuvent partager cet investissement ; une seule petite recherche peut ne pas le rentabiliser. Mesure séparément le prétraitement, le temps de consultation, le nombre de nœuds générés et la mémoire pour ne pas confondre une réduction des développements avec une amélioration automatique de la vitesse.

La recherche locale modifie à plusieurs reprises une réponse candidate complète. Elle convient aux tâches où la configuration finale compte et où la séquence utilisée pour la trouver peut être abandonnée.

Représenter un candidat complet

Pour les 8 dames, place une dame dans chaque colonne. Représente l’état par les huit numéros de ligne, en lisant les colonnes de gauche à droite. Chaque état comporte les huit dames, y compris les états avec des conflits. Un voisin déplace une dame vers une autre ligne de sa propre colonne.

Il existe $8^8=16777216$ états et $8\times 7=56$ voisins par état. Un nombre fixe d’états courants remplace la grande frontière et les enregistrements des parents de la recherche de chemin. Le stockage dépend toujours de la taille d’un état ; conserver un tuple de huit éléments prend moins de place que conserver un immense emploi du temps.

L’établissement d’emplois du temps, la disposition des composants d’une puce et le choix d’une tournée complète entre des villes suivent le même schéma général : chaque état est une proposition complète. Une tournée est elle-même une disposition candidate, même si son contenu décrit un trajet. La recherche locale n’a pas besoin de conserver la séquence de modifications utilisée pour améliorer cette tournée.

Définir ce que signifie « meilleur »

Une fonction objectif donne à chaque état un score à maximiser. On peut aussi définir un coût à minimiser. Pour les n dames, soit $h$ le nombre de paires de dames qui s’attaquent. Compte chaque paire une fois, y compris les attaques sur les lignes ou les diagonales même lorsqu’une autre dame se trouve entre elles. Une solution a $h=0$.

Pour quatre colonnes, le tuple (1 ; 2 ; 3 ; 4) place toutes les dames sur une diagonale. Ses $\left(\genfrac{}{}{0px}{}{4}{2}\right)=6$ paires s’attaquent toutes. Le tuple (2 ; 1 ; 3 ; 4) comporte deux paires qui s’attaquent, tandis que (2 ; 4 ; 1 ; 3) n’en comporte aucune. Ici, les valeurs plus faibles sont meilleures ; la lettre $h$ désigne un coût à minimiser, et non une estimation du coût de chemin restant utilisée par A*.

Lire le paysage

Imagine que la qualité d’un état soit représentée par une hauteur. Pour une maximisation :

• Un maximum global a la meilleure valeur de tout l’espace.
• Un maximum local est meilleur que ses voisins mais peut être moins bon qu’un état éloigné.
• Un plateau est une région plane connexe. Il peut s’agir d’un maximum local plat sans sortie ascendante ou d’un épaulement depuis lequel des déplacements latéraux permettent d’atteindre une sortie ascendante.
• Une crête peut monter dans une direction que les déplacements uniques disponibles ne peuvent pas suivre. Chaque choix immédiat peut sembler moins bon.

Pour minimiser un coût, inverse la hauteur : la recherche vise les minima et les vallées. Un minimum local ne prouve pas qu’il n’existe pas ailleurs un état de coût inférieur. Le voisinage détermine les états qui peuvent être comparés en une étape ; modifier la transformation autorisée peut donc changer les endroits où la recherche se bloque.

Vérifier que le chemin peut être ignoré

Un agent qui recherche un itinéraire doit renvoyer des actions autorisées depuis son départ réel. Une bonne destination ne suffit pas à elle seule. La recherche locale ne renvoie généralement que l’état candidat, sans chaîne de parents retraçant toutes les modifications précédentes.

Une méthode complète de recherche locale trouverait un but dès qu’il en existe un ; une méthode optimale trouverait le meilleur état global. Les méthodes locales de base ne donnent aucune de ces deux garanties générales. Leur intérêt est de pouvoir atteindre rapidement de bons candidats lorsque le stockage d’un arbre de recherche systématique est irréalisable.

La recherche par escalade effectue la meilleure amélioration immédiate qu’elle peut trouver. Pour un score à maximiser, l’escalade à plus forte pente choisit le voisin au score le plus élevé. Pour un coût à minimiser, elle choisit le voisin au coût le plus faible. Elle s’arrête lorsqu’aucune amélioration stricte n’existe.

Suivre une exécution pour quatre dames

Soit un état qui indique la ligne de la dame dans chaque colonne et soit $h$ le nombre de paires qui s’attaquent. Pars de (1 ; 2 ; 3 ; 4), dont le coût est de 6.

1. Évaluer les déplacements d’une dame. Un meilleur voisin est (2 ; 2 ; 3 ; 4), de coût 4.
2. De là, un meilleur voisin est (2 ; 1 ; 3 ; 4), de coût 2.
3. Aucun voisin obtenu en déplaçant une dame n’a un coût inférieur à 2. La recherche par escalade stricte s’arrête.

La disposition de coût nul (2 ; 4 ; 1 ; 3) existe, mais elle ne peut pas être atteinte depuis l’état d’arrêt par un déplacement qui améliore immédiatement le résultat. C’est une conséquence de la règle locale, et non la preuve que le programme a mal compté les conflits.

Autoriser des déplacements latéraux utiles

Un déplacement latéral conserve le même score. Il peut traverser un épaulement jusqu’à une sortie qui améliore le résultat, mais il peut aussi errer sur un optimum local plat. Limite les déplacements latéraux consécutifs pour éviter de tourner indéfiniment en rond.

Dans l’expérience sur les 8 dames rapportée par Russell et Norvig, l’escalade à plus forte pente à partir de départs aléatoires réussit environ 14 % du temps, en environ 4 étapes en cas de réussite et 3 lorsqu’elle se bloque. Autoriser jusqu’à 100 déplacements latéraux consécutifs porte le taux de réussite rapporté à environ 94 %, avec environ 21 étapes par réussite et 64 par échec. Ce sont les résultats de cette expérience, et non des taux de réussite universels pour la recherche par escalade.

Changer la façon de choisir un voisin

L’escalade stochastique sélectionne au hasard un voisin qui améliore le résultat, en favorisant éventuellement les améliorations les plus importantes. L’escalade au premier choix échantillonne les voisins un par un et prend la première amélioration. Elle évite d’évaluer un immense voisinage avant chaque déplacement. Les deux refusent toujours les déplacements vers des états moins bons.

La recherche par escalade avec redémarrages aléatoires commence une nouvelle exécution à partir d’un état nouvellement échantillonné après un échec. Pour des exécutions indépendantes de probabilité de réussite $p$, le nombre moyen d’exécutions jusqu’à la première réussite est de $1\mathrm{/}p$. Pour $p=\mathrm{0,14}$, cela représente environ 7 exécutions. Avec les nombres d’étapes rapportés, le nombre moyen total d’étapes est

Les exécutions échouées contribuent elles aussi au travail. Avec une probabilité de réussite strictement positive et des redémarrages indépendants, la probabilité de finir par réussir tend vers 1 lorsque le nombre d’exécutions augmente.

Faire partager les découvertes à plusieurs candidats

La recherche locale en faisceau conserve $k$ états, génère leurs voisins ensemble et retient les $k$ meilleurs de cet ensemble commun. Un parent prometteur peut fournir plusieurs états conservés alors qu’un autre n’en fournit aucun. Ce partage la distingue des redémarrages indépendants.

La mise en commun peut aussi regrouper tous les candidats dans une seule région. La recherche stochastique en faisceau échantillonne les états conservés avec une probabilité qui augmente avec leur qualité afin de préserver davantage de diversité. Le choix entre déplacements latéraux, redémarrages et diversité de la population dépend de la raison pour laquelle la progression échoue : un passage proche à valeur égale, une mauvaise région de départ ou trop de candidats explorant la même zone.

Dans certains paysages, une perte temporaire est nécessaire pour rendre accessible un meilleur état. Le recuit simulé autorise de tels déplacements avec une probabilité contrôlée. Les algorithmes génétiques explorent plutôt l’espace en sélectionnant et en combinant des candidats complets.

Accepter parfois un déplacement vers un état moins bon

Le recuit simulé échantillonne un voisin au hasard. Accepte un déplacement qui améliore le résultat. Pour une fonction objectif à maximiser, note sa variation $\mathrm{\Delta }E$. Si $\mathrm{\Delta }E<0$, accepte le déplacement vers un état moins bon avec la probabilité

Pour minimiser un coût, soit $\mathrm{\Delta }$ l’augmentation du coût. Un déplacement vers un état moins bon vérifie alors $\mathrm{\Delta }>0$ et sa probabilité d’acceptation est $e^{-\mathrm{\Delta }\mathrm{/}T}$. Les déplacements vers un état de même valeur ont une probabilité de 1 selon les deux formules. La température et les variations de la fonction objectif doivent utiliser des échelles numériques compatibles.

Une baisse de score de 2 est acceptée avec une probabilité d’environ 0,819 à une température de 10, de 0,135 à une température de 1 et de 0,018 à une température de 0,5. À une température de 10, une baisse plus importante de 5 a une probabilité d’environ 0,607. La température contrôle donc la tolérance, tandis que l’ampleur de la perte compte toujours à température égale.

Abaisser la température

Un schéma de refroidissement fixe la température au cours du temps. Le refroidissement géométrique utilise $T_{k+1}=\alpha T_k$ avec un facteur proche de 1, par exemple 0,95. À haute température, de nombreux déplacements vers des états moins bons sont acceptés et l’exploration ressemble à une marche aléatoire. Près de zéro, ces déplacements deviennent rares et le comportement ressemble à celui de la recherche par escalade.

Un refroidissement trop rapide peut piéger la recherche avant qu’elle ne s’échappe d’une mauvaise région. Un refroidissement très lent augmente le calcul nécessaire. Le résultat asymptotique sur l’optimum global exige un refroidissement suffisamment lent et la possibilité habituelle d’atteindre les états par le voisinage ; une exécution géométrique finie ordinaire ne garantit pas de trouver l’optimum global. Utilisée depuis les années 1980 pour la disposition des composants de puces et l’ordonnancement, la méthode tire son nom du chauffage puis du refroidissement lent du métal, qui lui permet d’adopter une structure de plus faible énergie.

Construire une nouvelle population

Un algorithme génétique représente les candidats par des chaînes. À chaque génération, il évalue leur adaptation, sélectionne les parents en privilégiant les mieux adaptés, crée des enfants par croisement et applique des mutations occasionnelles.

Pour les 8 dames, huit chiffres indiquant les lignes décrivent une dame par colonne. L’adaptation peut compter les paires qui ne s’attaquent pas, avec un maximum de 28. Coupe les chaînes des parents « 64751517 » et « 64278273 » après le quatrième chiffre. La combinaison des moitiés opposées donne « 64758273 » et « 64271517 ».

Les parents ont une adaptation de 23 et 24 ; les enfants ont une adaptation de 27 et 21. Un enfant est meilleur que les deux parents tandis que l’autre est moins bon. Le croisement offre de nouvelles combinaisons, sans garantir une amélioration. Il est utile lorsque de bons blocs tendent à conserver leur valeur lorsqu’ils sont combinés. La mutation modifie occasionnellement une position et contribue à introduire de la diversité au-delà de ces combinaisons.

La sélection, le croisement et la mutation jouent des rôles différents : la sélection favorise les candidats utiles, le croisement les recombine et la mutation modifie des positions individuelles. Comme la recherche stochastique en faisceau, la méthode conserve une population, mais les nouveaux candidats peuvent reprendre des éléments de deux parents. Ni un parent très adapté ni une température finale basse ne prouve à lui seul que l’optimum global a été trouvé.