LISP

Procura em Espaço de
Estados
Inteligência Artificial

Joaquim Filipe (c) 2001

1

Resolução de problemas
A inteligência artificial destina-se a construir máquinas para ajudar a resolver problemas em que de momento as pessoas são melhores.
Daí que um dos tópicos proeminentes seja o estudo e implementação de métodos automáticos de resolução problemas.

Joaquim Filipe (c) 2001

2

Espaço de estados
Uma forma simples de resolver problemas que não se podem resolver com fórmulas ou algoritmos, consiste em explorar o espaço de possibilidades tentando vários caminhos possíveis até encontrar a solução.
Neste caso um problema terá de ser equacionado em termos de:
– Estados
– Operadores (de transição de estados)

Terá ainda de ser definido
– O estado final (poderá ser com uma função de teste)

Joaquim Filipe (c) 2001

3

Exemplo (puzzle de 15)

(Nils Nilsson, Problem Solving Methods in AI, p.5)
Nilsson,

Joaquim Filipe (c) 2001

4

Representação
Grafo:
– O Espaço de Estados pode ser representado por um grafo dirigido acíclico.

Nó:
– cada nó do grafo representa um estado do problema, com alguma informação adicional (pointer para o nó que o gerou; etc.)

Arco:
– Cada arco do grafo representa uma transição de estado ao longo do processo de resolução do problema. Joaquim Filipe (c) 2001

5

Exemplo
Caixeiro Viajante.
– Problema clássico: um caixeiro viajante tem de planear uma viagem em que visita n cidades apenas 1 vez e regressa à cidade de origem, minimizando um custo (normalmente a distância percorrida). Representação gráfica:

Joaquim Filipe (c) 2001

6

Grafo do problema

(Nils Nilsson, Problem Solving Methods in AI, p.5)
Nilsson,
Joaquim Filipe (c) 2001

7

Representação de um Estado
Um estado no problema do caixeiro viajante pode ser representado como um conjunto de 2 elementos: {C, V}
C = Conjunto de cidades a visitar.
V = Conjunto das cidades já visitadas.

O estado