Estratégias de pesquisa
Árvore – algoritmo genérico
Percursos na árvore de pesquisa
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:
Tenta-se resolver o problema por pesquisa em profundidade com um dado limite N.
Se foi encontrada uma solução, retornar.
Incrementar N.
Voltar ao passo 1.
Pesquisa informada (“melhor primeiro”)
Last updated
