Procura, jogos e manipulação simbólica

No grafo com arestas a→b, a→c, b→d, d→e, c→e e d→a, há dois caminhos simples de a até e. DFS segue o primeiro ramo até [a,b,d,e]; BFS encontra [a,c,e], com menos arestas.

Em a→b→d, os visitados do caminho já contêm a, por isso excluem o retorno d→a.

Evitar ciclos sem esconder respostas

Na procura em profundidade, começamos por um vizinho e continuamos nesse ramo antes de tentar o vizinho seguinte. Uma lista de visitados do caminho atual impede regressar a um estado do mesmo caminho, ou seja não é a mesma coisa que proibir esse estado em todos os caminhos: um caminho alternativo pode precisar dele.

A relação caminho(X,Z,V,C) da página anterior pressupõe X, Z e as ligações conhecidos. Cada passo escolhe um vizinho que não está em V e aumenta os visitados. Num grafo finito, esta condição limita cada caminho ao número de estados. Sem ela, um ciclo pode impedir o motor de chegar a uma solução num ramo posterior.

A fila BFS passo a passo

Com os caminhos guardados ao contrário, a fila evolui assim:

Depois destas três expansões, o caminho objetivo já está na fila mas ainda não foi retirado. Expandimos [d,b,a]: a aresta d→a é excluída pelos visitados e acrescentamos [e,d,b,a], deixando a fila [[e,c,a],[e,d,b,a]].

Só agora retiramos [e,c,a] e devolvemos [a,c,e]. Distingue descobrir um candidato de o aceitar quando chega à frente da fila.

Guardar a fronteira numa fila

BFS, procura em largura, guarda os caminhos por explorar numa fila. Retira o mais antigo, verifica se chegou ao objetivo e coloca os novos caminhos no fim. Assim, explora todos os caminhos de uma aresta antes dos de duas, e assim sucessivamente.

O programa guarda cada caminho ao contrário, [EstadoAtual,...,Inicio], para acrescentar um vizinho à cabeça em tempo constante e só usar reverse ao encontrar a resposta.

:- use_module(library(lists)).
ligado(a,b). ligado(a,c). ligado(b,d). ligado(d,e). ligado(c,e).
ligado(d,a).

caminho(X,X,_,[X]).
caminho(X,Z,V,[X|R]) :- ligado(X,Y), \+ member(Y,V), caminho(Y,Z,[Y|V],R).

bfs([[Z|R]|_],Z,C) :- reverse([Z|R],C).
bfs([[X|R]|Fila],Z,C) :-
    X \= Z,
    findall([Y,X|R],(ligado(X,Y), \+ member(Y,[X|R])),Novos),
    append(Fila,Novos,Seguinte),
    bfs(Seguinte,Z,C).

write_portatil(X) :- write(X), nl.

main :-
    once(caminho(a,e,[a],D)), write_portatil(D),
    bfs([[a]],e,B), write_portatil(B).

DFS imprime [a,b,d,e]; BFS imprime [a,c,e]. Há também uma ligação de d para a, que os visitados impedem de repetir no caminho.

BFS explora por número de arestas, desde que cada expansão termine. Com custos iguais, o primeiro objetivo tem também menor custo. Com arestas de custo 10, 1 e 1, um caminho de duas arestas pode custar 2 e ser melhor que uma ligação direta de custo 10. Para otimizar pesos, precisamos de uma estratégia que ordene pelo custo acumulado. A fila BFS pode guardar muitas alternativas em memória.

Minimax e poda alfa-beta

Em minimax, MAX escolhe o maior valor e MIN o menor. Uma folha tem um valor medido do ponto de vista de MAX. Para uma árvore finita, calculamos primeiro os filhos e depois aplicamos a escolha do jogador no nó.

O ramo esquerdo vale min(-1,4)=-1 e o direito min(2,3)=2, pelo que a raiz vale max(-1,2)=2. MAX escolhe o ramo direito porque MIN pode impor -1 no ramo esquerdo e não consegue garantir a folha 4.

O modelo pressupõe dois jogadores com interesses opostos, informação completa e as jogadas da árvore disponíveis.

Numa árvore de fator de ramificação b e profundidade d, explorar todos os nós exige ordem b^d visitas. Limitar a profundidade pede uma função de avaliação para os estados não terminais. Esses valores são estimativas, não provas de vitória.

Na poda alfa-beta, alpha é um limite inferior já garantido a MAX e beta é um limite superior já garantido a MIN. Se alpha >= beta, explorar mais aquele ramo não melhora a decisão de um antepassado, e pode ser dispensado. A ordem das jogadas muda a quantidade de poda, mas não o valor minimax numa árvore finita com as mesmas folhas e regras.

Na árvore acima, depois de visitar o filho MIN esquerdo a raiz MAX tem alpha=-1; no filho MIN direito, ler 2 estabelece beta=2 e, como -1 < 2, ainda não podemos podar. Lemos também 3, o MIN fica em 2 e a raiz escolhe 2.

Se visitarmos o ramo direito primeiro, MAX já tem alpha=2. No ramo esquerdo, a primeira folha -1 estabelece beta=-1; agora alpha >= beta e a folha 4 pode ser dispensada. A decisão final continua a ser 2, com menos uma folha examinada.

Termos que representam expressões

Um termo como produto(var(x),var(x)) representa a expressão x*x. Não é uma multiplicação a executar com is; os functors guardam a estrutura para uma transformação simbólica. Uma regra pode desmontar o construtor e construir o resultado:

derivar(soma(A,B), X, soma(DA,DB)) :-
    derivar(A,X,DA), derivar(B,X,DB).

A regra da soma deriva os dois componentes. A regra do produto constrói DA*B + A*DB, conservando também as expressões originais. A derivada de uma variável relativamente a si própria é um; a de outra variável é zero. O programa pressupõe que os nomes das variáveis estão instanciados e que a expressão é uma árvore finita dos construtores apresentados.

:- use_module(library(lists)).
derivar(num(_), _, num(0)).
derivar(var(X), X, num(1)).
derivar(var(X), Y, num(0)) :- X \= Y.
derivar(soma(A,B), X, soma(DA,DB)) :- derivar(A,X,DA), derivar(B,X,DB).
derivar(produto(A,B), X, soma(produto(DA,B),produto(A,DB))) :-
    derivar(A,X,DA), derivar(B,X,DB).

valor(folha(N),N).
max_num([X|Xs], M) :- max_num(Xs, X, M).
max_num([], M, M).
max_num([X|Xs], A, M) :- (X > A -> B = X ; B = A), max_num(Xs, B, M).
valor(no(max,Filhos),V) :-
    Filhos = [_|_], findall(N,(member(F,Filhos),valor(F,N)),Ns), max_num(Ns,V).
min_num([X|Xs], M) :- min_num(Xs, X, M).
min_num([], M, M).
min_num([X|Xs], A, M) :- (X < A -> B = X ; B = A), min_num(Xs, B, M).
valor(no(min,Filhos),V) :-
    Filhos = [_|_], findall(N,(member(F,Filhos),valor(F,N)),Ns), min_num(Ns,V).

main :-
    derivar(produto(var(x),var(x)),x,D), write(D), nl,
    valor(no(max,[no(min,[folha(-1),folha(4)]),no(min,[folha(2),folha(3)])]),V),
    write(V), nl.

O primeiro resultado é soma(produto(num(1),var(x)),produto(var(x),num(1))). Ainda não está simplificado: uma fase posterior poderia retirar multiplicações por um e obter soma(var(x),var(x)). O segundo resultado é 2, o valor do jogo desenhado acima.

Uma transformação simbólica termina quando cada chamada recursiva recebe uma subexpressão menor. Se acrescentares regras de reescrita nas duas direções, como transformar uma soma numa forma e imediatamente regressar à original, podes criar um ciclo. Escolhe uma direção de simplificação e uma medida de progresso.