Avaliação da Pesquisa em Árvore
Last updated
Last updated
Seja:
N – número de nós da árvore de pesquisa no momento em que se encontra a solução.
X – Número de nós expandidos (não terminais).
d – comprimento do caminho na árvore correspondente à solução.
Ramificação média – número médio de filhos por nó expandido:
Nota: a ramificação média é um indicador da dificuldade do problema.
Factor de ramificação efectivo – número de filhos por nó, B, numa árvore com ramificação constante e com profundidade constante d.
Portanto: ou seja: (resolve-se por métodos numéricos).
O factor de ramificação efectiva é um indicador da eficiência da técnica de pesquisa utilizada.
Dados:
Coordenadas entre cidades.
Distâncias por estrada entre cidades vizinhas.
Calcular:
O melhor caminho entre duas cidades.
Usando:
Pesquisa em largura.
Pesquisa A*.
O problema consiste em determinar uma sequência de acções a desempenhar por um agente por forma a que, partindo de um dado estado inicial, se atinja um dado objectivo.
O conhecimento do domínio inclui uma descrição das condições de aplicabilidade e efeitos das acções possíveis.
STRIPS – planeador desenvolvido por volta de 1970, por Fikes, Hart e Nilsson.
A funcionalidade de um dado tipo de operação é definida, no formalismo STRIPS, através de uma estrutura chamada operador, que inclui a seguinte informação:
Pré-condições - um conjunto de fórmulas atómicas que representam as condições de aplicabilidade deste tipo de operação.
Efeitos negativos (delete list) – um conjunto de fórmulas atómicas que representam propriedades do mundo que deixam de ser verdade ao executar- se a operação.
Efeitos positivos (add list) – um conjunto de fórmulas atómicas que representam propriedades do mundo que passam a ser verdade ao executar-se a operação.
