Por estratégia entendemos um método determinístico de construir árvores de prova, com o intuito de obter as respostas calculadas. Do que vimos, uma estratégia pode ser definida fixando:
Designamos por escolha standard do tipo f, a escolha da folha mais à esquerda na árvore de prova parcial. Foi a escolha adoptada no exemplo em 2.4. Estando fixa a escolha do tipo f, podemos representar todas as tentativas de escolha do tipo c, por uma árvore de procura. A árvore de procura standard, é aquela que corresponde à escolha standard do tipo f. O princípio é o seguinte: partimos de uma questão
?- A.
Cada nó da árvore de procura contém um alvo, isto é, uma sucessão finita de átomos. O alvo da raíz é o átomo A. Em cada nó da árvore de procura, um dos átomos do alvo é designado por átomo escolhido. Na árvore de procura standard, o átomo escolhido é sempre o primeiro átomo do alvo. Um nó da árvore de procura tem tantos filhos quantas as cláusulas do programa (renomeadas) cuja cabeça possa ser unificada com o átomo escolhido desse nó. O alvo de um filho é obtido a partir do alvo do pai, unificando o átomo escolhido com uma cabeça de cláusula (renomeada); instanciando por esse unificador o alvo do pai e a cláusula; e substituindo o átomo escolhido pelo corpo da cláusula. A árvore de procura leva também indicações suplementares. Um exemplo são as substituições utilizadas. Vejamos um exemplo que mostra o método de construção. Retomemos a questão
?- avo(rosa,N).
Árvore de procura:
Para facilitar a construção da árvore de procura, acrescentámos a cada arco pai-filho
a cabeça da cláusula (renomeada) correspondente, bem como o número desta cláusula no
programa. Por outro lado, cada nó leva a substituição que define o unificador minimal
entre o átomo escolhido do nó pai e a cabeça da cláusula indicada sobre o arco
pai-filho (podemos considerar que o nó raíz leva a substituição identidade ). É por
conseguinte fácil, inscrevendo sistematicamente estas indicações, construir a árvore
de procura descendo da raíz e substituindo o átomo escolhido (que sublinhamos) pelo
corpo da cláusula, depois de instanciada. Na prática, para estarmos seguros de que
tentamos todas as cláusulas possíveis de serem unificadas, tentamos todas as cláusulas
com o mesmo símbolo de predicado do átomo escolhido, colocando a pontilhado as que não
são unificáveis. Graças às cláusulas cujo corpo é vazio, factos, podemos acabar em
nós nos quais o alvo é vazio. Esses nós são os nós terminais (folhas) da árvore de
procura, e neles colocamos a menção sucesso. Mas existem outros nós terminais:
aqueles para os quais nenhuma cláusula (renomeada) tem uma cabeça que pode ser unificada
com o átomo escolhido e portanto não possuem filhos. Juntamos a esses nós a menção falha.
É importante notar que os filhos de um nó são ordenados (esquerda-direita) pela ordem
das cláusulas no programa. Uma árvore de procura pode ser infinita, quer dizer, poderá
ter ramos infinitos que não são, portanto, terminados por uma folha falha ou sucesso.
Veremos exemplos à frente. A árvore de procura do exemplo anterior é a árvore de
procura standard (oriunda do átomo avo(rosa,N)), já que o átomo escolhido
em cada nó (o átomo sublinhado) é sempre o primeiro. Vemos facilmente que cada ramo da
árvore de procura, retrata a história das tentativas de construção de uma árvore de
prova. Por exemplo, o ramo que acaba na folha sucesso com , retrata exactamente
a construção da árvore de prova do capítulo anterior: 6 etapas de construção que
correspondem a 6 nós no ramo. Os ramos que acabam em folhas falha correspondem
às tentativas infrutíferas (situações de impasse); os ramos que acabam em folhas sucesso
correspondem às tentativas de êxito na construção de uma árvore de prova total. Cada
nó da árvore de procura corresponde a uma etapa na construção de uma árvore de prova.
Nessa etapa já construimos uma árvore de prova parcial e o alvo contido no nó não é
mais do que a sucessão de folhas dessa árvore de prova parcial. A escolha do átomo num
nó da árvore de procura, corresponde à escolha da folha na árvore de prova parcial. A
cada ramo sucesso da árvore de procura, corresponde uma resposta calculada à
questão de onde é oriunda a árvore de procura: é a resposta calculada que decorre da
construção da árvore de prova associada a esse ramo sucesso e que pode ser
obtida pela composição das substituições indicadas em cada nó do ramo. Quando a
resposta calculada não é evidente, mencionamo-la também ao lado da menção sucesso.
É o que fazemos no exemplo seguinte. Mas antes vamos introduzir o conceito (recursivo) de
lista.