redes

Inteligência Artificial
Funções Heurísticas

1

Funções heurísticas


Tentaremos mostrar a natureza das heurísticas em geral



Como é a heurística no quebra-cabeça de 8 peças? Lembrando o Objetivo:


Deslizar os blocos no sentido horizontal ou vertical para o espaço vazio até chegar na configuração objetivo.



.
2

1

Funções heurísticas


Para um quebra-cabeça de 8 peças




Custo de solução média 22 passos
Fator de ramificação ‘b’ ~ 3
=>Busca exaustiva para a profundidade 22 examinaria 



Controlando estados repetidos seria :




170 000 vezes

Para um quebra-cabeça de 15 peças




322 estados (ou ~ 3,1 x 1010 estados)

1013 estados !

Precisamos de uma boa função heurística!
3

Funções heurísticas


Candidatas a h(.)



h1= Nro de blocos em posições erradas. h2= Soma das distancias dos blocos de suas posições objetivo.


Distancia de Manhattan

4

2

Funções heurísticas


Efeito da Exatidão da h(.)


Qualidade de uma h(.) é caracterizado pelo:






Fator de ramificação efetiva (b*)
Nós gerados por A* ~ N
(para um problema)
Profundidade ~ d

Então:b* é o fator de ramificação que uma árvore uniforme de profundidade d precisaria ter para conter N + 1 nós. Desse modo: 5

Funções heurísticas


Exatidão da h()


Calculando o Fator de ramificação:

6

3

Funções heurísticas


Exatidão da h()


Calculando o Fator de ramificação:


Medidas experimentais de b* podem fornecer uma boa orientação sobre:




A utilidade GERAL da heurística

Uma heurística bem projetada teria um valor de b* ~ 1

7

Funções heurísticas – experimento (1200 prob.aleat)



BAI=Busca por aprofundamento iterativo
A*

8

4

Criação de Funções heurísticas admissíveis





Como alguém poderia criar h2() [distancia de Manhattan]
Um computador pode criar tal heurística mecanicamente? Observar:
