Eine heuristische Funktion ist ...
- Konsistent, wenn die geschätzten Kosten vom Knoten zum Ziel nicht größer sind als die Schrittkosten für seinen Nachfolger zuzüglich der geschätzten Kosten vom Nachfolger zum Ziel.
- Zulässig, wenn niemals die wahren Kosten für den Zielzustand überschätzt.
Das Lehrbuch für meinen Kurs über künstliche Intelligenz besagt, dass Konsistenz stärker ist als Zulässigkeit, dies jedoch nicht beweist, und ich habe Probleme, eine mathematische Erklärung zu finden.
algorithms
shortest-path
heuristics
user58348
quelle
quelle
Antworten:
Um die Aussage in Ihrer Frage zu beweisen, lassen Sie uns beweisen, dass Konsistenz Zulässigkeit impliziert während das Gegenteil nicht unbedingt zutrifft. Dies würde die Konsistenz zu einer stärkeren Bedingung machen als letztere.
Konsistenz impliziert Zulässigkeit:
Lassen Sie mich betonen , dass beginnen , wenn die heuristische Funktion h ist zulässig (wobei t ein Ziel ist) , da Kantenkosten angenommen werden nicht-negativ und damit zu sein, ist die optimale Kosten von einem Knoten zu sich selbst notwendigerweise 0 Dies gilt sicherlich für den Fall, dass die heuristische Funktion zulässig ist, aber wir möchten nachweisen, dass Konsistenz notwendigerweise Zulässigkeit impliziert . Nehmen wir dazu weiter an, dass h ( t ) = 0 für ein beliebiges Ziel ist - und diese Tatsache wird im folgenden Basisfall verwendet.h(t)=0 h t h(t)=0
Der Beweis erfolgt durch Induktion:
Basisfall : Nehmen Sie einen beliebigen Vorgänger des Zielknotens . Es sei n , so dass t ein Nachfolger von n ist . Wenn die heuristische Funktion konsistent ist , ist h ( n ) ≤ c ( n , t ) + h ( t ) = c ( n , t ) + 0 = c ( n , t ) und damit ht n t n h(n)≤c(n,t)+h(t)=c(n,t)+0=c(n,t) h verhält sich in diesem Fall zulässig.
Beachten Sie, dass der Basisfall nicht davon ausgehen , dass die Kante notwendigerweise die optimale Lösung von n bis t und in der Tat könnte es ein anderer Weg sein n⟨n,t⟩ n t n bis mit geringer Kosten. Die Wichtigkeit des Basisfalls ist, dass h ( n ) ≤ c ( n , t ) für alle Vorfahren des Knotens t istt h(n)≤c(n,t) t ! Dieses Ergebnis wird im Induktionsschritt wiederverwendet.
Induktionsschritt : Betrachte einen Knoten . Die optimal Kosten , das Ziel zu erreichen t von n , h * ( n ) wird berechnet als: min m ∈ S C S ( n ) { c ( n , m ) + n ) ≤ c ( n , n ' ) + h ( n ' ) . Weiterhin gilt als h ( n ′ )n t n h∗(n) , wobei S C S ( n ) ist die Menge der Nachfolger des Knotens n . AlsKonsistenzminm∈SCS(n){c(n,m)+h∗(m)} SCS(n) n wird hypothetisch angenommen, dann ist )h(n)≤c(n,n′)+h(n′) durch den Induktionsschritt angenommen wird, gilt h ( n ) ≤ c ( n , n ' ) + h ∗ ( n ' und dies gilt für alle Nachfolger n ' von Knoten nh(n′)≤h∗(n′) h(n)≤c(n,n′)+h∗(n′) n′ n . Mit anderen Worten: , so daß h ( n ) ≤ h * ( n ) .h(n)≤minm∈SCS(n){c(n,m)+h∗(m)}=h∗(n) h(n)≤h∗(n)
Zulässigkeit bedeutet nicht notwendigerweise Konsistenz:
Hierzu genügt ein einfaches Beispiel. Betrachten wir eine graphische Darstellung , die mit 10 Knoten eines einzigen Pfad besteht: , wo das Ziel ist , n 9 . Nehmen wir wlog an, dass alle Kantenkosten gleich 1 sind. Offensichtlich ist h ∗ ( n 0 ) = 9 1 ≤⟨n0,n1,n2,...,n9⟩ n9 h∗(n0)=9 , und machen wir , h ( n i ) =h(n0)=8 und h ( n 9 ) = 0 . Die heuristische Funktion isteindeutig zulässig:h(ni)=1,1≤i<9 h(n9)=0
Jedoch ist nicht konsistent und h ( n 0 ) = 8 > c ( n 0 , n 1 ) + h ( n 1 ) = 1 + 1 = 2 .h(n) h(n0)=8>c(n0,n1)+h(n1)=1+1=2
Hoffe das hilft,
quelle