Y a-t-il des graphiques pour lesquels un * ne peut pas être admissible?

Question

Wikipedia stipule que "sur des graphiques infinis avec un facteur de ramification fini et Coûts de bord qui sont délimités à partir de zéro $ (x, y)> \ varpsilon> 0 $ pour certains $ \ varpsilon $ ), A * est garanti de se terminer uniquement s'il existe une solution. "

Cela signifie-t-il que, si j'ai un tel graphe, il n'y a pas d'admissible A * qui existe pour ce graphique? Quand on dit qu'un * n'est pas admissible, cela signifie que son heuristique n'est pas admissible, non?

En outre, est-il correct de dire qu'une heuristique est seulement admissible par rapport à un graphique - pas généralement admissible?

Par exemple, si j'ai un graphique infini qui a un facteur de ramification fini, et le coût de chaque bord est La moitié du coût du bord précédant (quelque chose comme ceci: $ but \ raquetarrow _ {_ {c= 2}} start \ rightarrow _ {_ {c= 1}} q1 \ researrow_ {_ {c= 1/2}} q_2 \ rightarrow ... $ ), la heuristique et donc l'A * est nécessairement irrecevable car il n'existe pas de classique $ \ epsilon> 0 $ moins que le coût de tout bord?

Generaliser, la $ EPSILON $ La contrainte est de vous assurer qu'il n'y a pas de chemin infini qui converge le coût total converge, assurant ainsi la terminaison?

Une clarification est appréciée. Merci!

Answer 1

la fonction heuristique $ h: v \ longrightarrow \ mathbb {r} _ {\ geq 0} $ est * une entrée à la $ A ^ * $ algorithme. Si la fonction est admissible alors $ a ^ * $ algorithme vous donne la solution; Cependant, comme vous l'avez noté pour les graphiques infinis, les poids des bords doivent avoir une limite inférieure positive.

Le point de la fonction heuristique consiste à trouver le chemin le plus court dans le moins de temps , i.e. abaissez la complexité de calcul; Parce que vous prenez des décisions éclairées basées sur une heuristique (d'où le nom).

rappeler la fonction heuristique est admissible si $ h (v) $ est toujours inférieur à (ou égal à) le vrai chemin coûteux pour le nœud d'objectif.

Il y a toujours un admissible $ h $ nommément $ h (v)= 0 $ pour tous $ v $ . Dans ce cas extrême, il devient Algorithme de Dijkstra .

retourner à l'exemple que vous avez donné si vous branchez l'entrée $ a ^ * (g, h) $ où $ G $ est une description de $ g $ et $ h= 0 $ alors < SPAN CLASS="MATH-CONTENEUR"> $ A ^ * $ n'arrête pas (série géométrique $ R= 2 \ implique \ sum_i r ^ i=frac { 1-R ^ {n + 1}} {1-R} \ Leq 2 $ Pour toutes les sommes partielles finies). Mais voyons si nous pouvons contourner cela; permet d'essayer: \ begin {équation} h (v)=begin {cas} 3 & \ texte {if} v= q_1 \\ 0 & \ text {ele} \ fin { Cas} \ end {équation} Comme vous pouvez le voir $ h $ est admissible (car $ d (q_1 , \ texte {but})= 3 $ sur le nez) et $ a ^ * $ choisira "but" comme son premier noeud (parce que son Deux choix sont $ f (q_1)= 4 $ ou $ f (\ text {butin})= 2 $ ).