SMA*

A* com memória limitada simplificado (simplified memory- bounded A*).

Usa a memória disponível

• Contraste com IDA* e RBFS: estes foram desenhados para poupar memória, independentemente de ela existir de sobra ou não.

Quando a memória chega ao limite, esquece (remove) o nó n com maior custo f(n)=g(n)+h(n), actualizando em cada um dos nós ascendentes o “custo do melhor nó esquecido”

Só volta a gerar o nó n quando o custo do melhor nó esquecido registado no antecessor de n for inferior aos custos dos restantes nós.

Em cada iteração, é gerado apenas um nó sucessor.

• Existindo já um ou mais filhos de um nó, apenas se gera ainda outro se o custo do nó pai for menor do que qualquer dos custos dos filhos.

• Quando se gerou todos os filhos de um nó, o custo do nó pai é actualizado como no RBFS.

Exemplo – espaço de estados

Neste exemplo: memória = 3 nós.

• Melhores custos de nós esquecidos anotados entre parêntesis.