Avaliação da Pesquisa em Árvore

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.

Aplicação: planear um passeio turístico

Dados:

• Coordenadas entre cidades.

• Distâncias por estrada entre cidades vizinhas.

Calcular:

• O melhor caminho entre duas cidades.

Usando:

• Pesquisa em largura.

• Pesquisa A*.

Aplicação: planeamento de sequências de acções

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.

Representação de acções em problemas de planeamento

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.

Exemplo: planeamento no mundo dos blocos