Heuristic Function h(n)
"Mestre ne'ebé orienta busca atu la'o ho matenek"
Definisaun kompleta
Heuristic function (funcaun heuristika) mak funsaun ida ne'ebé uza iha área inteligénsia artifisál no siénsia komputasaun atu estima ka sura "distánsia" ka kustu husi estado atual ba estado objetivu. Nia funsiona hanesan "mestre" ida ne'ebé ajuda algoritmu buka-solução atu deside dalan ida ne'ebé mak promete atu la'o tuir, iha fatin atu buka dalan hotu ho maneira buta (uninformed). Ho nia, prosesu buka solusaun sai lalais no efisiente liu tanba heurístika fó orientasaun bazeia ba koñesimentu espesífiku husi problema ne'ebé sei rezolve.
Objetivu prinsipal husi heurístika mak atu hamenus tempu no rekursu komputasaun nian. Iha problema barak, buka solusaun ho forsa bruta (ezemplu, BFS ka DFS) bele lento tebes tanba espasu estadu boot liu. Heurístika ajuda atu evita ezpande node barak ne'ebé la relevante no foka ba dalan ne'ebé lori ba solusaun ho lalais. Maibé, importante atu hatene katak uza heurístika involve kompromisu entre "velosidade" no "akurácia". Heurístika fó estimativa de'it, la'ós garantia, tanba ne'e dala ruma bele lori ba solusaun sub-ótima se la kuidadu.
Métodu Atu Dezenvolve Heurístika (ho exemplo)
1. Analiza Problema Prinsipal
Iha Informed Search, heuristika mak funsaun estimasaun ne'ebé ajuda algoritmo hili dalan ne'ebé promissor liu ba meta. Pergunta importante mak: Oinsá ita bele dezenvolve heuristika ne'ebé di'ak, akuradu no efisiente? Dezenvolve heuristika la'ós inventa valor arbiru. Nia presiza baze iha analize struktura problema.
2. Simplifikasaun Problema (Problem Relaxation)
Ideia: Ita halo versãun problema ne’ebé simples liu husi problema orijinal. Signifika: ignora regra balu, reduz restrisaun, halo movimentu sai livre liu. Lojika: Se problema simples bele resolve ho fasil, kustu husi versãun simples ne’e bele sai estimasaun ba problema real. Razaun: Problema ne’ebé relaxadu sei la iha kustu boot liu problema real, tanba restrisaun menus. Nune’e, heuristika ne’e normalmenti admissible.
3. Uza Koñesimentu Domíniu (Domain Knowledge)
Heuristika di’ak uza informasaun espesífiku kona-ba natureza problema. Iha mapa: uza distánsia linha reta. Iha puzzle: uza número peça ne’ebé la iha pozisaun loos. Analiza: Sem heuristika, busca la iha orientasaun. Koñesimentu domíniu ajuda aproxima realidade. Maibé se koñesimentu la presizu → estimasaun bele sala.
Exemplo puzzle: Manhattan distance — soma movimentu vertikal/horizontal ba kada bloku.
4. Abstrasaun (Abstraction)
Halo representasaun problema ne’ebé menus detallu. Problema real normalmenti kompleks. Ita bele halo modelu abstratu ne’ebé ignora elementu sekundáriu. Benefísiu: kalkulasaun sai simples, busca sai lalais. Risku: abstrasaun boot liu → estimasaun la presizu.
5. Dezenvolve husi Solusaun Subproblema
Divide problema boot ba parte ki’ik. Se subproblema ida bele resolve, nia kustu bele uza hanesan heuristika. Iha puzzle, ita calcula distánsia kada peça mesak. Total estimasaun: h(n) = Σ hᵢ(n). Ne’e mak soma kustu subproblema.
6. Kombinasaun Heuristika
Dala ruma ita iha heuristika barak: h₁(n), h₂(n). Ita bele uza: h(n) = max(h₁(n), h₂(n)). Razaun: Valor boot liu normalmenti aproxima kustu real liu. Se heuristika hotu admissible, max sei kontinua admissible.
h(n) = max(h₁, h₂) fornese heuristika ne’ebé forte liu (informativu), maibé nafatin admissible.
Komparasaun heuristika ba 8-puzzle (estadu exemplo)
Supozu estadu atual ho konfigurasaun:
2 8 3 1 6 4 7 0 5 (0 = espasu vaziu)
| Heurístika | Valor | Kategoria |
|---|---|---|
| Misplaced tiles (h₁) | 5 peça sala fatin | admissible |
| Manhattan distance (h₂) | 8 total movimentu | admissible (forte liu) |
| Max(h₁, h₂) | max(5,8)=8 | admissible & informativu |
Kombinasaun max hetan informasaun di'ak liu.
Ilustrasaun heurístika iha mapa
Iha mapa, heurístika linha reta (Euclidiana) entre A no B serve hanesan estimativa ba distáncia dalan real. Linha putus-putus iha imajen hatudu estimativa heurístika (nunka liu dalan real se uza linha reta).
Exemplo ida ne’e ilustra "domain knowledge" (koñesimentu domíniu).
Propriedade Importante: Admissible no Konsistente
Heurístika admissível (nunka superestima) garante otimalidade iha A*.
Heurístika konsistente (monotónika) garante efisiéncia liu tan. Ezemplu: manhattan distance, misplaced tiles, linha reta.
↳ Iha 8-puzzle, heurístika Manhattan no misplaced tiles hotu admissível.
Iha Informed Search, heuristika mak funsaun estimasaun ne’ebé ajuda algoritmo hili dalan ne’ebé promissor liu ba meta... (konteúdu kompletu hetan tratamentu iha leten).