Busca com heurística e sua completude
Por Cassiano Carvalho Rocha e José Maria Silveira Neto para a disciplina de Inteligência Artificial, ministrada pelos professores Marcelino Pequeno e Carlos Brito. Curso de Computação, Universidade Federal do Ceará, 2007.2.
Busca com heurística é um método de solução de problemas onde a busca no espaço de estados é orientada por uma função. Essa função vai receber um estado e retornar um valor. Idealmente esse valor reflete a distancia do atual estado ao estado objetivo, a solução.
Uma função para busca com heurística pode ser derivada do senso comum ou obtida empiricamente através de experiências com modelos teóricos ou práticos. Espera-se de uma boa heurística que ela retorne valores baixos para estados que estejam mais próximos da solução e retorne valores altos quando estiverem mais distantes. Por outro lado, uma heurística ruim poderá não refletir essa informação, ou pior, traze-la de maneira invertida.
Na figura abaixo, o ponto preto representa o estado inicial. O ponto vermelho representa a solução. A região de fronteira do algoritmo de busca em largura é representado pela região cinza.
Note que uma heurística que resulta sempre os mesmos valores, irá nos conduzir à mesma fronteira de uma busca em largura.
Se nos usarmos uma boa heurística a fronteira vai se aproximar da solução mais rapidamente.
Uma heurística ruim ira expandir a fronteira numa direção errada.
Num caso ainda pior, a heurística irá sempre apontar numa direção errada, dizendo que aquele nó sempre está mais perto da solução do que todos os outros.
O que nos leva a uma situação onde temos uma busca não completa.
Na figura acima temos o caso onde h(x) (a função da heurística) sempre diz que os descendentes de x sempre estarão mais próximos da solução do que o ponto y.
Uma forma disso acontecer é se a função h(x) sempre retornar zero. Podemos evitar esse caso restringindo h com um certo E qualquer.
- ∀x, h(x) > E > 0
Para contornar essa situação iremos usar não somente a heurística na hora de avaliar qual nó iremos expandir. Vamos utilizar o custo do caminho até o nó candidato à expansão, somando esse valor à heurística:
- h(x) + g(x)
onde h(x) é a função da heurística e g(x) é o custo até o nó x.
Dessa maneira iremos avaliar os pontos x e y novamente. Agora as heurísticas podem até apontar na direção errada, como no exemplo anterior, mas elas serão retardadas pela acréscimo da função g.
Colocando a restrição:
- ∀a, g(a) > E > 0
Haverá um momento em que h(x)+g(x) > h(y)+g(y), já que cada vez que descemos na árvore o custo do caminho se torna cada vez mais alto. Nesse momento escolhemos y para ser expandido.
Porém há um problema. Caso a heurística possa retornar infinito para um ponto y, não haverá nenhum valor de h(x)+g(x) maior do que h(y)+g(y). Logo, o algoritmo de busca nunca escolherá y para ser expandido. O que torna, novamente, nossa busca incompleta.
Adicionamos mais uma restrição à h nunca retornará infinito.
A⋆
Nosso algoritmo que, a cada passo, seleciona na fronteira um nó x com menor valor para f(x)=g(x)+h(x), é completo.
Prova:
Vamos supor uma heurística bem ruim. Para caminhos que não levem a solução, ela estima os nós com peso E. E para caminhos que levem a solução, a heurística retorna um valor α, maior que E. Se nosso algoritmo não leva-se em conta os custos dos caminhos até os nós, é fácil ver que ele não encontraria a solução.
Porém f(x) cresce de maneira monotônica. Em algum momento f(x) passará a ser maior que f(y), onde f(y) será um nó em algum outro caminho. Em particular em algum momento esse outro caminho será o caminho que levará à solução.
