Notas de Aula

1. Defina uma heurística admissível e consistente (h1).
2. Defina uma segunda heurística admissível e consistente (h2) que domine h1.

A heurística do algoritmo A* utiliza a distancia entre dois pontos para efetuar seus cálculos.

A Função Heurística (h(n)) escolhida é também a técnica de busca mais utilizada. Esta função heurística estima o custo do caminho mais barato do estado atual até o estado final mais próximo, ou seja, encontrar a rota mais curta entre dois estados:

h(n) = valor estimado da distância em linha reta direta entre o nó n e o nó final.

A estratégia escolhida para esta heurística combina o custo do caminho g(n) com o valor da heurística h(n) através do algoritmo A* (f(n) = g(n) + h(n)).

• g(n) = custo do caminho do nó inicial até o nó n.
• h(n) = valor da heurística do nó n até um nó objetivo (distância em linha reta no caso de distâncias espaciais).

Usando essa heurística foram então definidos valores estimados (h1) para os custos dos estados de uma peça bruta em linha reta até o estado final (H) como mostra a Tabela 1.

Tabela 1 – Heurística h1.

Estado	h1
A	40
B	20
C	20
D	10
E	5
F	3
G	8
H	0

É sempre melhor usar uma função heurística com valores mais altos e mais próximos do valor real do custo do caminho, contanto que ela seja admissível. É definida uma segunda heurística admissível e consistente (h2) que domine h1, como mostra a Tabela 2.

Tabela 2 – Heurística h2.

Estado	h2
A	42
B	22
C	24
D	12
E	7
F	5
G	11
H	0

Nesse caso h2 é melhor que h1 por causa:

• ∀n, h2(n) ≥ h1(n).
• A* com h2 expande menos nós do que com h1.

Além disso, hi domina hk se hi(n) ≥ hk(n), ∀n no espaço de estados.

1. Um desenho das árvores de busca geradas pelo uso de h1 e pelo uso de h2 do estado A até o objetivo H permitindo comparar:

1. Número de nós criados;
2. Valor de f(n) para cada nó criado na árvore;
3. Se f(n) é não decrescente;

Para h1 foram expandidos 19 nós, como mostra a Figura 1. Já para o h2 foram expandidos 14 nós (Figura 2). Analisando ambos os grafos é possível afirmar que h2(n) ≥ h1(n) e o algoritmo A* com h2 expande menos nós do que com h1, portanto h2 domina h1.

[pic 1]

Figura 1 - Árvore de busca gerada pelo uso de h1.

[pic 2]

Figura 2 - Árvore de busca gerada pelo uso de h2.