Optimality & Completeness (h(n) & A* property)
Heuristic function (h(n)) mak fungsi estimativa ne’ebé nunka boot liu husi kustu real husi node agora too goal node (se h(n) admissível). Iha A*, h(n) uza atu balu algoritmu determina node ne’ebé prioridade iha ekspansaun. Heurístika = perkiraan biaya, la biaya nyata. Singkat: h(n) fó-hatene se node ida “dí’ak” liu ka besik liu ba objetivu.
Optimality signifika katak algoritmu A* sempre hetan solusaun ho kustu mínimu (mura) se h(n) admissível (nunka superestima). Completeness signifika katak A* sempre hetan solusaun (se iha solusaun) tanba nia explora node sira ho orden f(n) no la hetan loop infinitu.
Optimality
A* garantia dalan ho kustu minimu se h(n) admissível (ex: heurístika konsistente).
Completeness
A* sempre hetan solusaun (se iha) tanba nia explora gradually no kobre.
Exemplo: optimality ho heurístika admissível
Konsidera problema ho inísiu S no objetivu G. Heurístika h(n) nunka boot liu kustu real ba G.
| Node | g(n) (kustu real) | h(n) (estima) | f(n) = g+h |
|---|---|---|---|
| S | 0 | 5 | 5 |
| A | 4 (exemplu) | 7 | 11 |
| B | 3 (exemplu) | 8 | 11 |
| G (via A) | 10 | 0 | 10 |
| G (via B) | 12 | 0 | 12 |
Optimality: A* sei explora dalan ho f=5 (S), depois f=11 (A no B). Tanba h admissível, A* sei hetan dalan S→A→G ho f=10 molok S→B→G ho f=12. Nune’e nia garante dalan ótimu (kustu 10).
Completeness: Se iha dalan ba G (ho kustu finitu), A* sempre sei hetan, tanba nia la tama loop infinitu.
Papel h(n) iha Optimality no Completeness
• Se h(n) admissível (≤ kustu real), A* garante optimality.
• Se h(n) konsistente (monotóniku), A* optimal liu tan no eficiente.
• Completeness depende: A* kompletu se kustu pasu pozitivu no branching faktur finitu. Heurístika ajuda atu hetan liu lalais maibé la afeta completeness.
Visualizasaun Optimality
Imajen: Árvore busca ho dalan S → A → G (kustu 10) no S → B → G (kustu 12). Heurístika h(n) admissível garante katak A* sei explora dalan ho f(n) ki’ik liu, to’o hetan dalan ótimu. Númeru iha nódus reprezenta f(n). Iha imajen, f(S)=5, f(A)=11, f(B)=11, f(G) liuhusi A=10, liuhusi B=12.
Fonte: ilustrasaun ba konseitu optimality no completeness iha A*.
Optimality: dalan ho kustu mínimu
Kondisaun ba Optimality no Completeness (A*)
✅ Optimality se h(n) admissível (nunka superestima).
✅ Completeness se kustu pasu pozitivu no branching faktur finitu (A* sempre explora).
🤝 Heurístika admissível garante katak A* hetan solusaun ótima (mura liu).