Tip:
Highlight text to annotate it
X
Ovde ćemo vam dati činjenicu zašto
optimistična heuristička funkcija, h, nalazi najjeftiniji put.
Kada se A-star završi, vraća se put, p, sa procenjenom cenom, c.
Ispostavlja se da je c takođe i stvarna cena,
zato što je u cilju komponenta h 0,
i tako je cena puta ukupna cena procenjena funkcijom.
Sada, svi putevi na granici
imaju procenjene cene koje su veće od c,
a to znamo, zato što je granica istražena po redosledu najjeftinija-prva.
Ako je h optimistična, onda je procenjena cena
manja od stvarne cene,
tako da put p mora imati cenu manju od stvarne cene
bilo kojog puta na granici.
Bilo koji put koji ide iza granice
mora imati cenu koja je veća od toga
zato što smo se dogovorili da je cena koraka uvek 0 ili više.
Dakle, to znači da ovaj put, p, mora biti put minimalne cene.
Sada, ovaj argument, trebalo bih da kažem, jedino prolazi
za pretragu stabla.
Za pretragu grafa argument je malo komplikovaniji,
ali opšte činjenice su iste.