Procura, jogos e manipulação simbólica

DFS, BFS e ciclos

• DFS explora um ramo em profundidade antes das alternativas. A ordem das cláusulas afeta o primeiro caminho; um ramo infinito pode impedir respostas posteriores.
• Visitados do caminho atual impedem ciclos nesse caminho. Um estado pode continuar a pertencer a outro caminho válido.
• Num grafo finito com geração finita de vizinhos, acrescentar só estados ainda não visitados limita cada caminho.
• BFS retira o caminho mais antigo da fila e acrescenta as extensões no fim. Explora por número de arestas; o primeiro objetivo tem menor custo quando as arestas custam o mesmo.

DFS encontra [a,b,d,e]; BFS encontra [a,c,e]. A fila guarda caminhos invertidos e o objetivo só é aceite ao chegar à frente: depois de expandir a, b e c, a fila é [[d,b,a],[e,c,a]] e ainda falta expandir d. Com pesos diferentes, menos arestas não garante menor custo; a fila BFS pode ocupar muita memória.

Minimax e alfa-beta

Calcula de baixo para cima: min(-1,4)=-1, min(2,3)=2 e max(-1,2)=2. MAX não pode escolher a folha 4, porque MIN controla essa escolha. O modelo exige dois jogadores opostos, informação completa e uma árvore finita de jogadas.

• Com ramificação $b$ e profundidade $d$, visitar tudo custa $O(b^d)$ para $b>1$. Um limite de profundidade usa estimativas nos estados não terminais, não provas de vitória.
• alpha é um limite inferior garantido a MAX; beta é um limite superior garantido a MIN. Quando alpha >= beta, o resto do ramo não melhora a decisão do antepassado.
• A ordem das jogadas altera a poda, mas conserva o valor minimax nas mesmas condições. Na figura, visitar o ramo direito primeiro dá alpha=2; ler -1 no esquerdo dá beta=-1 e dispensa a folha 4.

Derivação simbólica

Um termo produto(var(x),var(x)) guarda uma expressão; não pede a multiplicação com is. Derivar desmonta os construtores e constrói outro termo.

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

• A regra do produto constrói DA*B + A*DB, conservando as expressões originais. Uma variável deriva para um relativamente a si própria e para zero relativamente a outra.
• Derivar x*x pode produzir 1*x+x*1: derivação e simplificação são fases distintas.
• Exige nomes de variáveis instanciados e árvores finitas dos construtores suportados. A recursão termina ao passar para subexpressões menores; reescritas nas duas direções podem criar ciclos.

Procura, poda e símbolos.