Estratégias de pesquisa

Árvore – algoritmo genérico

Percursos na árvore de pesquisa

Pesquisa em largura

Pesquisa em profundidade

Implementação baseada numa fila

Pesquisa em largura

Pesquisa em profundidade

Python

Vamos criar um conjunto de classes para suporte à resolução de problemas por pesquisa em árvore.

• Classe SearchDomain() – classe abstracta que formata a estrutura de um domínio de aplicação.

• Classe SearchProblem(domain,initial,goal) – classe para especificação de problemas concretos a resolver.

• Classe SearchNode(state,parent) – classe dos nós da árvore de pesquisa.

• Classe SearchTree(problem) – classe das árvores de pesquisa, contendo métodos para a geração de uma árvore para um dado problema.

Pesquisa em profundidade - variantes

Pesquisa em profundidade sem repetição de estados – para evitar ciclos infinitos, convém garantir que estados já visitados no caminho que liga o nó actual à raiz da árvore de pesquisa não são novamente gerados.

Pesquisa em profundidade com limite – não são considerados para expansão os nós da árvore de pesquisa cuja profundidade é igual a um dado limite.

Pesquisa em profundidade com limite crescente – consiste no seguinte procedimento:

1. Tenta-se resolver o problema por pesquisa em profundidade com um dado limite N.

2. Se foi encontrada uma solução, retornar.

3. Incrementar N.

4. Voltar ao passo 1.

Pesquisa informada (“melhor primeiro”)