Universidade Federal de São Carlos
Departamento de Computação
Programação Lógica
Prof. Dr. Antonio Francisco do Prado
e-mail: [email protected]
Outros Exemplos
Problema dos Missionários e Canibais
Na margem esquerda de um rio há 5 missionários e 5
canibais, que querem atravessá-lo para a outra margem .
Há um bote que pode transportar no máximo 3 pessoas ao
mesmo tempo. Os missionários não podem ficar em menor
número que os canibais em qualquer margem, caso
contrário serão devorados. Como fazer para que todos
cheguem a salvo na outra margem do rio?
Resolução:
Consideraremos a seguinte descrição para o conjunto de
estados possíveis utilizados para representar o problema
(Me, Ce, Bte)
onde,
Me = número de missionários na margem esquerda
Ce = número de canibais na margem esquerda
Bte = 1 se o bote está na margem esquerda, 0 na direita
Logo, o estado inicial é (5, 5, 1) e o final (0, 0, 0)
Representação do Espaço de Estados do Problema
(5,5,1)
(5,4,0)
(5,3,0)
(5,2,0)
(5,4,1)
(4,4,0)
(5,3,1)
(3,3,0)
(5,1,0)
(5,0,0)
(4,4,1)
(5,2,1)
(5,1,1)
(2,2,0)
(3,3,1)
(0,3,0)
(0,4,1)
(0,1,0)
(1,1,1)
(0,5,1)
(0,2,0)
(0,3,1)
(0,0,0)
(0,4,0)
(2,2,1)
(0,2,1)
O programa prolog que encontra a solução para este
problema usando busca em largura é mostrado abaixo.
largura([ ],_,_):- write('Solução não encontrada!'),nl.
largura([G|T],_,G):- write('Solução encontrada!'),nl.
largura([S|T],C,G):write('Listas a Percorrer: '),write([S|T]),nl,
write('Listas Percorridas: '), write(C),nl,
bagof(X,movelargura( S, T, C, X ),Lista),
append(T,Lista,O ),!,
largura(O, [S|C],G ).
largura([S|T],C,G):- largura(T,[S|C],G).
movelargura(S,T,C,X):- move(S,X),
X \== S,
not member(X,T),
not member(X,C).
% representação do espaço de estados
move([5,5,1],[5,2,0]).
move([5,5,1],[5,4,0]).
move([5,5,1],[4,4,0]).
move([5,5,1],[5,3,0]).
move([5,2,0],[5,3,1]).
move([5,2,0],[5,4,1]).
move([4,4,0],[5,4,1]).
move([0,1,0],[0,2,1]).
move([5,3,0],[5,4,1]).
move([5,3,1],[3,3,0]).
move([5,3,1],[5,0,0]).
move([5,3,1],[5,1,0]).
move([5,4,1],[3,3,0]).
move([5,4,1],[5,1,0]).
move([5,0,0],[5,1,1]).
move([5,1,0],[5,2,1]).
move([2,2,0],[3,3,1]).
move([0,3,0],[0,4,1]).
move([0,4,1],[0,2,0]).
move([0,5,1],[0,2,0]).
move([0,2,0],[2,2,1]).
move([0,1,0],[0,3,1]).
move([0,1,0],[1,1,1]).
move([0,3,1],[0,0,0]).
move([1,1,1],[0,0,0]).
move([0,2,1],[0,0,0]).
move([5,0,0],[5,2,1]).
move([3,3,0],[4,4,1]).
move([5,2,1],[2,2,0]).
move([3,3,1],[0,3,0]).
move([0,3,0],[0,5,1]).
move([0,4,1],[0,1,0]).
move([0,5,1],[0,4,0]).
move([0,2,0],[0,3,1]).
?- largura([[5,5,1]],[ ],[0,0,0]).
Neste caso partiu-se com o Estado Inicial, a Lista
dos Percorridos e o Estado Final.
Organização de uma Lista
Bubblesort
bubblesort(List,Sorted):-swap(List,List1),!,
bubblesort(List1,Sorted).
bubblesort(Sorted,Sorted).
swap([X,Y|Rest],[Y,X|Rest]):-gt(X,Y).
swap([Z|Rest],[Z|Rest1]):-swap(Rest,Rest1).
gt(X,Y):-X>Y.
Questão:
?- bubblesort([9,5,3,8],L).
L = [3,5,8,9]
Quicksort
quicksort([],[]).
quicksort([X|Tail],Sorted):-split(X,Tail,Small,Big),
quicksort(Small,Sortedsmall),quicksort(Big,Sortedbig),
conc(Sortedsmall,[X|Sortedbig],Sorted).
split(X,[],[],[]).
split(X,[Y|Tail],[Y|Small],Big):-gt(X,Y),!,
split(X,Tail,Small,Big).
split(X,[Y|Tail],Small,[Y|Big]):-split(X,Tail,Small,Big).
conc([],L,L).
conc([X|L1],L2,[X|L3]):-conc(L1,L2,L3).
gt(X,Y):-X>Y.
Questão:
?- quicksort([5,8,0,2,7],L).
L = [0,2,5,7,8] ;
no
Permutation Sort
psort(Xs,Ys) :- permutation(Xs,Ys), ordenado(Ys).
permutation(Xs,[Z|Zs]) :- select(Z,Xs,Ys),
permutation(Ys,Zs).
permutation([],[]).
ordenado([]).
ordenado([X]).
ordenado([X,Y|Ys]) :- X <= Y, ordenado([Y|Ys]).
Questão:
?- psort([3,4,2,1],Y).
Y = [1,2,3,4]
Insertion Sort
isort([X|Xs],Ys) :- isort(Xs,Zs), insert(X,Zs,Ys).
isort([],[]).
insert(X,[],[X]).
insert(X,[Y|Ys],[Y|Zs]) :- X > Y, insert(X,Ys,Zs).
insert(X,[Y|Ys],[X,Y|Ys]) :- X <= Y.
Questão:
?- isort([3,2,1],A).
A = [1,2,3]
Investigando um Crime
 Definição de uma base de dados:
possivel_suspeito(fred).
possivel_suspeito(mary).
possivel_suspeito(jane).
possivel_suspeito(george).
crime(roubo,john,terca,parque).
crime(roubo,robin,quinta,bar).
crime(assalto,jim,quarta,bar).
estava(fred,terca,parque).
inveja(fred,john).
principal_suspeito(Pessoa,Crime):crime(Crime,Vitima,Dia,Lugar),
possivel_suspeito(Pessoa),
estava(Pessoa,Dia,Lugar),
tem_motivo_contra(Pessoa,Vitima).
principal_suspeito(desconhecido,Crime).
tem_motivo_contra(Pessoa,Vitima):inveja(Pessoa,Vitima).
Questões:
?- principal_suspeito(Quem,roubo).
Quem = fred ;
Quem = desconhecido
?- crime(Crime,Vitima,Dia,bar).
Crime = roubo ,
Vitima = robin ,
Dia = quinta ;
Crime = assalto ,
Vitima = jim ,
Dia = quarta ;
Calculando o M.D.C. de uma Lista de Números
Uma das formas de calcularmos o m.d.c de dois números
é fatorarmos os dois e selecionarmos os fatores primos com
os menores expoentes em cada um deles, por exemplo:
18 = 2^1 * 3^2
12 = 2^2 * 3^1
mdc(12, 18) = 2^1 * 3^1 = 6
Outra forma de calcularmos o m.d.c. de dois números é
seguindo a seguinte regra:
1) Se a divisão do maior número pelo menor for exata então
o mdc é igual ao menor número.
2) Senão o processo é repetido usando o menor número e o
resto da divisão do maior pelo menor.
Ex:
mdc(18, 12)
18 | 12
01
--06
mdc(12, 06)

12 | 06
12 02
--00

mdc(18, 12) = 6
Nosso programa PROLOG utiliza o segundo método com
a diferença que o estendemos para uma lista de números e
não apenas para dois números:
mdc([A|[]], A) :- !.
mdc([A|Calda], N) :- mdc(Calda, B), mdc2(A, B, N), !.
mdc2(A, B, B) :- X is A mod B, X is 0, !.
mdc2(A, B, N) :- X is A mod B, mdc2(B, X, N).
O predicado mdc possui duas clausulas, a primeira existe
para determinarmos qual o mdc de uma lista com apenas
um elemento, e a segunda clausula determina o mdc de uma
lista com dois ou mais elementos, calculando recursivamente
o mdc da calda desta lista e em seguida o mdc da cabeca da
lista com o mdc da calda da lista já calculado.
As clausulas do predicado mdc2 aplicam os passos 1 e 2 do
segundo método mostrado acima.
Abaixo mostramos alguns exemplos de execução do
programa:
?- mdc([18,30,12,60], R).
R=6
?- mdc([18,30,10,60], R).
R=2
?- mdc([15,6,12,9], R).
R=3
?- mdc([15,30,20,12], R).
R=1
?- mdc([16,8,32,64], R).
R=8
O Problema das Damas no Tabuleiro de Xadrez
O enunciado do problema é o seguinte: “Em um tabuleiro
de xadrez, ou de um modo mais geral um tabuleiro de N*N
casas, queremos posicionar N damas de modo que nenhuma
das damas ataca qualquer outra”.
A resolução do problema está diretamente relacionada à
movimentação exercida pela dama; No jogo de xadrez a
dama caminha nas verticais, horizontais e diagonais, deste
modo já eliminamos a possibilidade de haver duas ou mais
damas numa mesma coluna ou numa mesma linha, restando
apenas verificar se todas elas não se atacam nas diagonais.
Podemos mapear o problema da seguinte maneira: Para
um tabuleiro de N linhas por N colunas colocamos uma dama
em cada coluna, cada uma em uma linha diferente da outra e
então começamos a permutar cada dama de uma certa
coluna com cada outra dama de outra coluna, desta forma
realizaremos N! permutações, entre estas permutações
eventualmente encontraremos situações onde nenhuma dama
ataca nenhuma outra, esta situação representa uma solução.
A figura abaixo representa uma das 82 soluções encontrada
pelo programa PROLOG para um tabuleiro de 8*8 com 8
damas:
?- damas(8,R).
R = [1,5,8,6,3,7,2,4]
Na figura contamos as linhas de baixo para cima, por
exemplo o número 5 da resposta corresponde a dama da
segunda coluna colocada na quinta linha. A baixo mostramos
o código em PROLOG.
damas(NumDamas,Solucao) :- intervalo(1,NumDamas,Lista),
permuta(Lista,Solucao), seguro(Solucao).
intervalo(A,A,[A]).
intervalo(A,B,[A|Calda]) :- A < B, Proximo is A+1,
intervalo(Proximo,B,Calda).
permuta([],[]).
permuta(Lista,[Elemento|Calda]) :retira(Elemento,Lista,NovaLista),
permuta(NovaLista,Calda).
retira(X,[X|Calda],Calda).
retira(X,[Y|Calda],[Y|NovaCalda]) :- retira(X,Calda,NovaCalda).
seguro([]).
seguro([Cabeca|Calda]) :- seguro(Calda),
not ataca(Cabeca,Calda).
ataca(Cabeca,Calda) :- ataca(Cabeca,1,Calda).
ataca(X,Distancia,[Y|Calda]) :- X is Y+Distancia; X is Y-Distancia.
ataca(X,Distancia,[Y|Calda]) :- N1 is Distancia+1,
ataca(X,N1,Calda).
O predicado damas é composto de dois argumentos
NumDamas (número de damas) e Solucao (lista que contém
a solução), e dos predicados intervalo (que cria uma lista do
tipo [1, 2 ,3 , 4 ,5 ,6 ,7 ,8]), permuta (que realiza todas as
permutações na lista que criamos) e seguro (que testa se uma
dada situação gerada a partir de uma permutação é uma
situação aceitável, ou seja nenhuma dama ataca nenhuma
outra).
Calculando Números Primos
Os números primos são aqueles divisíveis por si e pelo
número um, desta forma poderíamos determinar se um
número é primo dividindo-o por todos os números anteriores
a ele e contando quantos números conseguiram dividi-lo sem
deixar resto. Este processo seria muito demorado,
principalmente se desejássemos calcular uma lista de
números primos. Podemos resolver este problema de uma
maneira diferente:
1) Criamos uma lista de números consecutivos que começa
em 2 e vai até o maior número do intervalo no qual
queremos encontrar os números primos.
2) Pegamos o primeiro número da lista e cortamos todos os
seus múltiplos.
3) Repetimos o processo para cada novo elemento na lista.
No final do processo a lista restante contém apenas
elementos que não possuem divisores diferente do número 1,
ou seja, apenas números primos. A figura seguir ilustra o
processo para os números de 2 a 100.
O código PROLOG é mostrado a seguir:
primos(Limite, Primos) :- geraLista(2, Limite, Lista),
geraPrimos(Lista, Primos).
geraLista(Menor, Maior, [Menor|Lista]) :- Menor =< Maior, N is
Menor+1, geraLista(N, Maior, Lista), !.
geraLista(_, _, []).
geraPrimos([], []) :- !.
geraPrimos([Primo|Lista], [Primo|MaisPrimos]) :removeMultiplos(Primo, Lista, NovaLista),
geraPrimos(NovaLista, MaisPrimos).
removeMultiplos(Num, [], []) :- !.
removeMultiplos(Num, [Cabeca|Lista], [Cabeca|NovaLista]) :not(0 is Cabeca mod Num),
removeMultiplos(Num, Lista, NovaLista), !.
removeMultiplos(Num, [Cabeca|Lista], NovaLista) :0 is Cabeca mod Num,
removeMultiplos(Num, Lista, NovaLista).
O predicado removeMultiplos gera uma lista que possui
apenas números que não são múltiplos de um certo número
dado. O predicado geraLista constrói uma lista com todos os
números entre um número menor e um maior. O predicado
geraPrimos pega o primeiro número de uma lista e arranca
todos os múltiplos deste elemento, então pega a esta nova lista
e repete o processo. O predicado primos gera uma lista
inicialmente com todos os números num intervalo dado e
após isto chama o predicado geraPrimos. A seguir mostramos
uma execução:
?- primo(100,L).
L = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,
79,83,89,97]
Encontrando o Menor Caminho Entre Duas Cidades
Quando desejamos encontrar o menor caminho entre duas
cidades devemos primeiramente conhecer todos os caminhos
que nos levam da cidade origem até a cidade destino, para isso
devemos montar um grafo onde os nós são as cidades e os
arcos são as distâncias entre uma cidade e outra. O grafo
abaixo representa um exemplo:
Nosso programa PROLOG deve encontrar todos os caminhos
possíveis entre a cidade origem e a cidade destino e escolher
aquele cuja a soma das distâncias correspondesnte às viagens
de uma cidade para outra é a menor. O programa é o seguinte:
distancia(a, d, 200). distancia(a, e, 500).
distancia(b, e, 100). distancia(b, f, 100).
distancia(d, e, 100). distancia(e, g, 300).
distancia(f, i, 100). distancia(g, h, 300).
vizinho(X, Y, Dist) :- distancia(X, Y, Dist).
vizinho(X, Y, Dist) :- distancia(Y, X, Dist).
pertence(X, [X|_]).
pertence(X, [_|L]) :- pertence(X,L).
distancia(b, c, 100).
distancia(c, f, 100).
distancia(e, i, 400).
distancia(h, i, 200).
caminho(Origem, Origem, _, [], 0).
caminho(Origem, Destino, CidadesVisitadas,
[Intermediario|Caminho], Distancia) :vizinho(Origem, Intermediario, Dist1),
not(pertence(Intermediario, CidadesVisitadas)),
caminho(Intermediario, Destino,
[Intermediario|CidadesVisitadas], Caminho, Dist2),
Distancia is Dist1 + Dist2.
primeiro([[Caminho,Distancia]|Lista], Caminho, Distancia).
resolve(Origem, Destino, [Origem|Caminho], Distancia) :bagof([Camin,Dist], caminho(Origem, Destino, [Origem],
Camin, Dist), Lista),
sort(Lista,ListaOrdenada,[2]),
primeiro(ListaOrdenada, Caminho, Distancia).
O predicado distancia determina as distâncias entre as
cidades, o predicado vizinho determina que se uma cidade dista
x de outra então esta segunda dista x da primeira, o predicado
pertence determina se uma elemento já pertence a uma lista ou
não (no nosso caso se uma cidade já pertence a uma lista de
cidades), o predicado caminho encontra o caminho de uma
cidade até outra bem como a distância total do percurso, o
predicado primeiro pega o primeiro elemento de uma lista e o
predicado resolve é o responsável por pegar todos os caminhos
encontrados e escolher o de menor distância. A seguir
mostramos um exemplo para o grafo anterior:
?- resolve(a, h, Caminho, Distancia).
Caminho = [a,d,e,b,f,i,h] ,
Distancia = 800
Busca em Largura em Árvore Binária
Freqüentemente necessitamos realizar buscas em árvores
para solucionar problemas, como por exemplo quando
queremos verificar todos os estados de um jogo de dama
para chegar a uma posição vitoriosa. O backtracking de
PROLOG nos permite realizar buscas em profundidade com
certa facilidade, no entanto, para alguns problemas
necessitamos realizar buscas em largura, o que não é uma
tarefa tão simples. A busca é feita da seguinte forma:
1) Coloca-se o nó raiz em uma lista
2) Expande-se (gera-se todos os seus filhos) o primeiro
elemento da lista e coloca-se o resultado no final da lista
3) Repete-se o processo para o segundo da lista, terceiro da
lista, etc..., até que não haja mais elementos para expandir.
No final teremos uma lista de nós cuja ordem é a ordem
da busca em largura. A figura abaixo mostra uma árvore
exemplo e os passos do processo descrito acima.
O código PROLOG é mostrado a seguir:
buscaLargura([], []).
buscaLargura([tree(No, Esq, Dir)|Calda], [No|Resultado]) :bagof(X, filho(tree(No, Esq, Dir), X), Lista),
append(Calda, Lista, NovaLista),
buscaLargura(NovaLista, Resultado), !.
buscaLargura([tree(No, Esq, Dir)|Calda], [No|Resultado]) :buscaLargura(Calda, Resultado), !.
filho(tree(No, Esq, Dir), Esq) :- Esq \== null.
filho(tree(No, Esq, Dir), Dir) :- Dir \== null.
O predicado buscaLargura realiza o processo de expandir o
primeiro nó da lista, criar uma nova lista que contém também
os nós expandidos e repetir o processo para cada nó sucessivo
da lista. O predicado filho é usado para retornar cada filho de
um certo nó. A seguir mostramos a execução:
?- buscaLargura( [tree(3, tree(1, null, tree(2, null, null)), tree(7,
tree(5, tree(4, null, null), tree(6, null, null)), tree(8, null, null)))],R).
R = [3,1,7,2,5,8,4,6]
Verificação de Árvores AVL
Neste exemplo mostraremos como verificar se uma dada
árvore é uma árvore AVL. Árvores AVL são árvores binárias
de busca que possuem altura mínima, ou seja, em uma árvore
de N nós a distância máxima da raiz a qualquer folha é no
máximo log(N). Árvores de altura mínima são chamadas
árvores balanceadas.
Portanto devemos verificar duas condições:
1)A árvore binária deve ser uma árvore de busca.
2)A árvore binária deve estar balanceada.
Dizemos que uma árvore binária é de busca se todos os
elementos da subárvore esquerda de qualquer nó são
menores que este nó e todos os elementos da subárvore direita
de qualquer nó são maiores que este nó.
Dizemos que uma árvore é balanceada se a diferença de
altura da subárvore esquerda para a subárvore direita não
exceder em módulo a unidade.
Desta forma o teste de árvores AVL fica como mostrado a
seguir:
ehAVL(Arvore) :- arvoreBusca(Arvore), balanceada(Arvore).
arvoreBusca(null).
arvoreBusca(tree(Raiz, ArvoreEsq, ArvoreDir)) :- maior(Raiz,
ArvoreEsq), menor(Raiz, ArvoreDir).
maior(_, null).
maior(Maior, tree(Raiz, ArvoreEsq, ArvoreDir)) :- Maior > Raiz,
maior(Raiz, ArvoreEsq), menor(Raiz, ArvoreDir),
maior(Maior, ArvoreDir).
menor(_, null).
menor(Maior, tree(Raiz, ArvoreEsq, ArvoreDir)) :Maior < Raiz, maior(Raiz, ArvoreEsq),
menor(Raiz, ArvoreDir), menor(Maior, ArvoreEsq).
balanceada(null).
balanceada(tree(_, ArvoreEsq, ArvoreDir)) :balanceada(ArvoreEsq), balanceada(ArvoreDir),
altura(ArvoreEsq, HE), altura(ArvoreDir, HD),
DIF is HE - HD, abs(DIF) =< 1.
altura(null, 0).
altura(tree(_, ArvoreEsq, ArvoreDir), Altura) :altura(ArvoreEsq, HE), altura(ArvoreDir, HD),
Altura is max(HE, HD) + 1.
Na chamada ao predicado ehAVL devemos passar uma
estrutura de árvore como a mostrada nos exemplos a seguir:
?- ehAVL(tree(3, tree(1, null, tree(2, null, null)), tree(7, tree(5,
tree(4, null, null), tree(6, null, null)), tree(8, null, null)))).
yes
?- ehAVL(tree(3, tree(1, null, tree(2, null, null)), tree(7, tree(5,
tree(0, null, null), tree(6, null, null)), tree(8, null, null)))).
no
?- ehAVL(tree(3, tree(1, null, tree(2, null, null)), tree(7, tree(5,
tree(4, null, null), tree(6, null, null)), null))).
no
Reconhecendo Cadeias de Símbolos Através de MEFs
Máquinas de Estados Finita (MEF) podem ser
representadas de modo simplificado por um conjunto de
estados e um conjunto de transições de estados, além dos
estados finais e do estado inicial. Freqüentemente desejamos
verificar se uma certa cadeia de símbolos pertence a
linguagem determinada por uma MEF, para isso devemos
aplicar uma seqüência de transições correspondentes aos
símbolos dessa seqüência que nos levarão de um estado inicial
a um estado final. Caso o estado final pertença ao conjunto de
estados finais dizemos que a seqüência de entrada pertence a
linguagem determinada pela MEF.
Existem ainda MEFs que possuem transições de um
determinado estado para mais de um estado, estas MEFs são
chamadas MEF indeterminísticas (MEF_ind), diferentemente
da primeira conhecida como MEF determinística (MEF_det).
Quando trabalhamos com MEFs_ind devemos ser capazes de
determinar qual o conjunto de estados resultante da
aplicação de uma transição sobre vários estados da MEF e
não apenas um único estado resultante da aplicação de uma
única transição sobre um único estado. O programa que
implementamos em PROLOG aceita MEFs_ind embora o
exemplo escolhido represente uma MEF_det.
terminal(q8).
transicao(q0, a, q3).
transicao(q1, b, q2).
transicao(q3, b, q4).
transicao(q5, a, q8).
transicao(q7, a, q4).
transicao(q0, b, q1).
transicao(q2, a, q5).
transicao(q4, a, q7).
transicao(q6, a, q3).
transicao(q7, b, q8).
transicao(q1, a, q4).
transicao(q3, a, q6).
transicao(q4, b, q5).
transicao(q6, b, q7).
transicao(q8, a, q5).
verifica(Estados, Entradas, []) :- aplicaTransicoes(Estados,
Entradas, []), write('Nao ha transicao prevista, a MEF para: '), !.
verifica(Estados, Entradas, Resposta) :aplicaTransicoes(Estados, Entradas, Resposta),
temTerminal(Resposta), write('Sequencia valida: '), !.
verifica(Estados, Entradas, Resposta) :aplicaTransicoes(Estados, Entradas, Resposta),
write('Sequencia invalida: '), !.
aplicaTransicoes([], Entradas, []) :- !.
aplicaTransicoes([Estado|[]], [], [Estado]) :- !.
aplicaTransicoes([Estado|[]], [Entrada|Sequencia],
EstadosFinais) :- transicoes(Estado, Entrada, ListaEstados),
aplicaTransicoes(ListaEstados, Sequencia, EstadosFinais), !.
aplicaTransicoes([Estado|MaisEstados], Entradas,
EstadosFinais) :- aplicaTransicoes([Estado], Entradas, ListaA),
aplicaTransicoes(MaisEstados, Entradas, ListaB),
uniao(ListaA, ListaB, EstadosFinais).
temTerminal([Estado|_]) :- terminal(Estado), !.
temTerminal([_|Estados]) :- temTerminal(Estados).
transicoes(Estado, Entrada, ListaEstados) :bagof(NovoEstado, transicao(Estado, Entrada,
NovoEstado), ListaEstados), !.
transicoes(Estado, Entrada, []).
uniao([], [], []) :- !.
uniao([], Lista, NovaLista) :- tiraRepetidos(Lista, NovaLista), !.
uniao(Lista, [], NovaLista) :- tiraRepetidos(Lista, NovaLista), !.
uniao([Elem|ListaA], ListaB, NovaLista) :- pertence(Elem, ListaB),
uniao(ListaA, ListaB, NovaLista), !.
uniao([Elem|ListaA], ListaB, NovaLista) :- pertence(Elem, ListaA),
uniao(ListaA, ListaB, NovaLista), !.
uniao([Elem|ListaA], ListaB, [Elem|NovaLista]) :- uniao(ListaA,
ListaB, NovaLista).
tiraRepetidos([], []) :- !.
tiraRepetidos([Elem|[]], [Elem]) :- !.
tiraRepetidos([Elem|Calda], Saida) :- pertence(Elem, Calda),
tiraRepetidos(Calda, Saida), !.
tiraRepetidos([Elem|Calda], [Elem|Saida]) :tiraRepetidos(Calda, Saida).
pertence(Elem, [Elem|_]) :- !.
pertence(Elem, [_|Lista]) :- pertence(Elem, Lista).
Os fatos terminal e transicao determinam a estrutura da
MEF (estados, transições e estado final). O predicado verifica
possui três argumentos: uma lista de estados, uma lista
representando a seqüência de símbolos de entrada e uma lista
de estados finais da MEF correspondente às transições
realizadas após a verificação. No processo de verificação
devemos aplicar transições correspondentes aos símbolos de
entrada, esta tarefa é realizada pelo predicado
aplicaTransicoes, neste predicado encontramos um conjunto
de estados resultantes das transições correspondentes a uma
determinada entrada e repetimos este processo até que se
esgotem os símbolos de entrada. No final do processo de
aplicação de transições teremos duas listas com estados finais
da MEF (uma gerada a partir do primeiro estado da lista de
estados e outra gerada a partir dos estados restantes).
Devemos agora unir estas duas listas em uma (tarefa realizada
pelo predicado uniao) retirando as possíveis repetições de
estados através do predicado tiraRepetidos. Por fim
determinamos se o conjunto de estados finais possui ao menos
um elemento terminal, esta tarefa é realizada pelo predicado
temTerminal. A estrutura da MEF é mostrada na figura
abaixo e aceita as cadeias de ‘a’s e ‘b’s que possuem número
par de ‘a’s (2, 4, ..) e exatamente 2 ‘b’s em qualquer ordem.
Representação gráfica da MEF
Algumas possíveis execuções seriam:
?- verifica([q0], [a,b,a,a,b,a,a,a], R).
Sequencia valida: R = [q8]
?- verifica([q0], [b,a,a,b,b,a,a], R).
Nao ha transicao prevista, a MEF para: R = []
?- verifica([q0], [a,b,a,a], R).
Sequencia invalida: R = [q4]
Poderiamos ainda iniciar a MEF a partir de mais de um
estado como por exemplo q0 e q4, isso acarretaria no
reconhecimento de seqüências com um único ‘b’ e um número
impar de ‘a’s (1, 3, ...) além das seqüências reconhecidas
anteriormente a partir de q0.
?- verifica([q0,q4], [a,b,a,a], R).
Sequencia valida: R = [q4,q8]
?- verifica([q0,q4], [a,b,b,a,a], R).
Sequencia invalida: R = [q5]
?- verifica([q0,q4], [a,a,b,b,a,a], R).
Sequencia valida: R = [q8]
O Problema das Jarras D’água
O problema das jarras d’água tradicional consiste de duas
jarras de capacidades 3 e 5 litros (inicialmente vazias) e uma
fonte d’água para encher as jarras. O objetivo do problema é
deixar 4 litros na jarra de capacidade 5 litros, para isso
podemos realizar as seguintes ações: encher uma jarra,
esvaziar uma jarra ou despejar o conteúdo de uma jarra na
outra. Poderíamos representar a seqüência de transições que
nos conduzem à resposta representando os estados das jarras
(através de pares) entre cada ação tomada. A solução seria a
seguinte: (0,0), (0,5), (3,2), (0,2), (2,0), (2,5), (3,4).
Outra maneira de representarmos a solução seria
reportando a seqüência de passos a serem tomados: encher a
2o. jarra, virar a 2o. jarra na 1o., esvaziar a 1o. jarra, virar a
2o. jarra na 1o., encher a 2o. jarra, virar a 2o. jarra na
primeira.
Esquema das transições que levam o estado inicial a um estado final
O problema que mostramos a seguir estende o problema
tradicional das jarras d’água para qualquer número de
jarras, com qualquer configuração inicial, qualquer
capacidade e qualquer configuração final da jarras. Além
disso impomos um limite de transições para alcançarmos o
estado final, isto significa que eventualmente podemos não
encontrar uma solução, não porque esta solução não existe,
mas sim porque ela necessita de mais transições do que o
limite que colocamos.
move(JarraA, CapacA, JarraB, CapacB, NovoA, NovoB) :NovoA is CapacA, NovoB is JarraB, JarraA\=CapacA.
move(JarraA, CapacA, JarraB, CapacB, NovoA, NovoB) :NovoA is 0, NovoB is JarraB, JarraA\=0.
move(JarraA, CapacA, JarraB, CapacB, NovoA, NovoB) :NovoA is 0, NovoB is JarraA+JarraB,
NovoB<CapacB, JarraA\=0.
move(JarraA, CapacA, JarraB, CapacB, NovoA, NovoB) :NovoA is JarraA-(CapacB-JarraB), NovoB is CapacB,
CapacB-JarraB=<JarraA, JarraB\=CapacB.
altera([Cabeca|Calda], 0, Valor, [Valor|Calda]).
altera([Cabeca|Calda], Posicao, Valor, [Cabeca|NovaCalda]) :NovaPosicao is Posicao-1,
altera(Calda, NovaPosicao, Valor, NovaCalda).
pegaItem([Cabeca|Calda], Cabeca, 0).
pegaItem([_|Calda], Elemento, NovoContador) :pegaItem(Calda, Elemento, Contador),
NovoContador is Contador+1.
pegaJarra(Configuracao, Jarra, Posicao) :pegaItem(Configuracao, Jarra, Posicao).
pegaCapacidade(Capacidades, Capac, Posicao) :pegaItem(Capacidades, Capac, Posicao).
pertence(X, [X|_]) :- !.
pertence(X, [_|Z]) :- pertence(X, Z).
transicao(ConfFinal, ConfFinal, Capacidades, Lista, Contador)
:- reverse(Lista, NovaLista), write(NovaLista), !.
transicao(ConfInicial, ConfFinal, Capacidades, Lista,
Contador) :- Contador>0, NovoContador is Contador-1,
pegaJarra(ConfInicial, JarraA, PosicaoA),
pegaCapacidade(Capacidades, CapacA, PosicaoA),
pegaJarra(ConfInicial, JarraB, PosicaoB),
pegaCapacidade(Capacidades, CapacB, PosicaoB),
PosicaoA\=PosicaoB,
move(JarraA, CapacA, JarraB, CapacB, NovoA, NovoB),
altera(ConfInicial, PosicaoA, NovoA, ConfTemp),
altera(ConfTemp, PosicaoB, NovoB, NovaConf),
not(pertence(NovaConf, Lista)),
transicao(NovaConf, ConfFinal, Capacidades,
[NovaConf|Lista], NovoContador), !.
resolve(Inicial, Final, Capacidade, Contador) :caminho(Inicial, Final, Capacidade, [Inicial], Contador).
Os predicados move representam as transições que
podemos realizar entre duas jarras: encher, esvaziar e virar
uma em outra (virando até encher ou virando todo o
conteúdo). O predicado altera recebe uma lista, uma posição
e um valor e retorna uma nova lista igual, exceto na posição
recebida, onde o valor será alterado para o valor recebido. O
predicado pegaItem recebe uma lista e devolve um valor e sua
posição correspondente na lista, caso a posição já esteja
definida pegaItem retorna apenas o valor associado à
posição. Os predicados pegaJarra e pegaCapacidade apesar de
possuírem nomes diferentes realizam a mesma tarefa,
selecionam um valor e uma posição em uma lista dada.
O predicado transicao é o coração do algoritmo, no
primeiro predicado representamos um estado solução, ou seja,
a configuração atual do problema é igual a configuração final
do problema. Neste caso mostramos na tela a seqüência de
estados que representam a solução. No segundo predicado,
primeiramente testamos e decrementamos um contador para
que possamos garantir que não iremos procurar soluções que
possuam mais que um determinado número de transições,
após isso selecionamos duas jarras (na verdade todas as
combinações de duas jarras) e suas respectivas capacidades,
então conferimos se não pegamos duas vezes a mesma jarra.
Caso não tenhamos pego, criamos uma nova lista parecida
com a lista que possui a configuração atual, mas com os
conteúdos das duas jarras alterados, após isso verificamos se a
nova configuração que construímos não é um estado que já
faz parte de nossa lista de transições. Caso afirmativo,
continuamos o processo procurando agora chegar à
configuração final à partir do novo estado que geramos (com
a possibilidade de realizarmos uma transição a menos e com
um estado a mais na lista de estados que constituem o
caminho solução). O predicado resolve recebe uma lista que
representa a configuração inicial das jarras, uma lista que
representa o estado final, uma lista que representa a
capacidade das jarras e o número máximo de transições que
desejamos realizar. A seguir mostramos algumas execuções.
?- resolve( [0,1,2], [2,2,4], [2,3,5], 4 ).
[ [0,1,2], [1,0,2], [1,2,0], [1,2,5], [2,2,4] ] yes
?- resolve( [3,4], [1,0], [5,7], 4 ).
no
Note que no último exemplo não conseguimos encontrar
uma solução com 4 transições ou menos. No entanto, se
estipularmos 5 transições o problema já passa a ser solúvel.
?- resolve( [3,4], [1,0], [5,7], 5 ).
[ [3,4], [3,0], [0,3], [5,3], [1,7], [1,0] ] yes
Outro aspecto importante do problema é que podemos
omitir partes do estado solução quando não estamos
interessados em alguma jarra em específico:
?- resolve( [0,1], [3,2], [6,4], 10 ).
no
?- resolve( [0,1], [3,_], [6,4], 5 ).
[ [0,1], [6,1], [3,4] ] yes
Também podemos estabelecer relações de igualdade entre
os conteúdos finais das jarras:
?- resolve( [1,1,3,2], [X,2,X,1], [2,4,5,3], 3 ).
[ [1,1,3,2], [0,2,3,2], [0,2,2,3], [2,2,2,1] ] X = 2
O Problema da Coloração de Mapas
Quando estamos colorindo um mapa queremos que cada
país, ou estado, possua uma cor diferente de qualquer um de
seus vizinhos para que possa ser bem delimitado.
Matematicamente está provado que em um plano não
podemos interconectar totalmente mais que 4 elementos, ou
seja, teremos no máximo 4 países que fazem fronteira um com
o outro sem possibilidade de repetirmos cores. Se inserirmos
um quinto país, onde quer que seja, haverá sempre uma cor
que já usamos e assim poderemos repeti-la. Desta forma nosso
programa de coloração de mapas necessita apenas 4 cores.
Uma das diversas resoluções é a que se segue:
1) Definimos os países e as fronteiras entre eles.
2) Escolhemos um país e damos uma cor a ele
temporariamente.
3) Preenchemos os seus vizinhos com as cores restantes,
também temporariamente.
4) Pegamos outro país e repetimos o processo.
5) Caso não seja possível distribuir as cores para o país e
seus vizinhos, voltamos no Backtracking de PROLOG e
escolhemos outras combinações de cores.
OBS: Como sempre pintamos um país com uma cor e os
vizinhos com as restantes, sempre que conseguirmos pintar o
último país teremos certeza que ele não tem a mesma cor que
nenhum de seus vizinhos, e portanto todos ou outros países já
estão pintados corretamente. O código PROLOG é o seguinte:
cores([vermelho, amarelo, azul, verde]).
mapa([ fronteira(paisA, A, [B, C, D, F]),
fronteira(paisB, B, [A, C, D, E, F]),
fronteira(paisC, C, [A, B, D]),
fronteira(paisD, D, [A, B, C, E, F]),
fronteira(paisE, E, [B, D, F]),
fronteira(paisF, F, [A, B, D, E]) ] ).
pintaMapa(Solucao) :- mapa(Solucao), coloreMapa(Solucao).
coloreMapa([Pais|PaisesRestantes]) :- coloreRegiao(Pais),
coloreMapa(PaisesRestantes).
coloreMapa([]).
coloreRegiao(fronteira(Pais, Cor, Vizinhos)) :- cores(Cores),
seleciona(Cor, Cores, CoresRestantes),
preenche(Vizinhos, CoresRestantes).
seleciona(Elem, [Elem|Calda], Calda).
seleciona(Elem, [ElemDifer|Calda], [ElemDifer|NovaLista]) :seleciona(Elem, Calda, NovaLista).
preenche([Elem|Calda], Lista) :- member(Elem, Lista),
preenche(Calda, Lista).
preenche([], Lista).
O predicado mapa possui informações sobre os nomes dos
países, suas cores e as cores de seus vizinhos, servindo com
uma base de dados de países. Note que a cor de cada país bem
como a cor de seus vizinhos são representadas por variáveis
(letras maiúsculas), isto é, não estão instanciadas e portanto
poderão assumir diversos valores durante a execução do
programa. O predicado pintaMapa lê este mapa que definimos
e o colore. O predicado coloreMapa pega o primeiro país e
atribui uma cor a ele e aos seus vizinhos, após isso repete o
processo aos países restantes. O predicado coloreRegiao
seleciona uma cor para um país e utiliza as cores restantes
para preencher os países restantes.
O predicado seleciona pega uma cor entre as 4 cores e
retorna uma lista com as cores restantes, e o predicado
preenche atribui cores aos países não permitindo que um país
possua uma cor diferente das cores passadas no segundo
argumento deste predicado. A saída do programa contém os
nomes dos países, suas respectivas cores e a listas de cores
correspondentes aos países vizinhos. Note que para cada saída
do programa a cor do país nunca pertence a sua lista de cores
de países vizinhos.
A seguir mostramos 3 dos 24 modos diferentes de colorir o
mapa do nosso exemplo, e um mapa ilustrativo para cada caso.
?- pintaMapa(R).
R = [ regiao(paisA, vermelho, [amarelo, azul, verde, azul]),
regiao(paisB, amarelo, [vermelho, azul, verde, vermelho, azul]),
regiao(paisC, azul, [vermelho, amarelo, verde]),
regiao(paisD, verde, [vermelho, amarelo, azul, vermelho, azul]),
regiao(paisE, vermelho, [amarelo, verde, azul]),
regiao(paisF, azul, [vermelho, amarelo, verde, vermelho]) ] ;
R = [ regiao(paisA, amarelo, [azul, verde, vermelho, verde]),
regiao(paisB, azul, [amarelo, verde, vermelho, amarelo, verde]),
regiao(paisC, verde, [amarelo, azul, vermelho]),
regiao(paisD, vermelho, [amarelo, azul, verde, amarelo, verde]),
regiao(paisE, amarelo, [azul, vermelho, verde]),
regiao(paisF, verde, [amarelo, azul, vermelho, amarelo]) ] ;
R = [ regiao(paisA, verde ,[amarelo, vermelho, azul, vermelho]),
regiao(paisB, amarelo ,[verde, vermelho, azul, verde, vermelho]),
regiao(paisC, vermelho, [verde, amarelo, azul]),
regiao(paisD, azul, [verde, amarelo, vermelho, verde, vermelho]),
regiao(paisE, verde, [amarelo, azul, vermelho]),
regiao(paisF, vermelho, [verde, amarelo, azul, verde]) ] ;
Sistema Especialista no Planejamento Empresarial
Os sistemas especialistas são aplicações computacionais
capazes de simular o comportamento de um especialista
humano, em um determinado assunto, a fim de descobrir ou
resolver um determinado problema. Os sistemas especialistas
estão presentes em vários ramos da computação como:
OCRs, reconhecimento de voz, diagnóstico médico, jogo de
xadrez, sistema de computação de bordo de carros, sistema de
controle de robôs, etc. Nosso exemplo de sistema especialista
identifica alguns dos vários problemas que uma empresa tem
que resolver do ponto de vista estratégico. No exemplo
colhemos do usuário informações sobre o estado da empresa
bem como as condições gerais do mercado e, através destas
informações, inferimos outras coisas (assim como um
especialista humano faria). As informações que colhemos
devem estar relacionadas, ou encadeadas, de forma a
podermos construir grafos de causa-conseqüência. O grafo
abaixo representa três possíveis problemas que devemos
verificar e seus relacionamentos de causa-conseqüência.
Podemos dizer por exemplo que se: Funcionarios fazem
hora-extra frequentemente for verdadeiro e Projetos estao
atrasados for verdadeiro então concluímos (inferimos) que
Servico esta sobrecarregado é verdadeiro.
Nosso programa deve verificar cada um dos três problemas
que representamos fazendo perguntas quando necessário
(texto em preto), tirando conclusões (texto em azul) e
identificando o problema (texto em vermelho). O código
PROLOG é o seguinte:
conclusao(‘Ha necessidade de contratar pessoal’, [[‘Servico
esta sobrecarregado’, 1], [‘As vendas aumentaram’, 1],
[‘Nivel de informatizacao e bom’, 1]]).
conclusao(‘Ha necessidade de informatizar o setor’, [[‘Servico
esta sobrecarregado’, 1], [‘As vendas aumentaram’, 1],
[‘Nivel de informatizacao e bom’, 0]]).
conclusao(‘Ha necessidade de terceirizar o servico’, [[‘Ha
viabilidade em terceirizar o servico’, 1],
[‘Determinado servico esta custando caro para a empresa’, 1],
[‘Investir em tecnologia ao inves de terceirizar o servico nao e
viavel’, 1]]).
regra(‘Servico esta sobrecarregado’, [[‘Funcionarios fazem horaextra frequentemente’, 1], [‘Projetos estao atrasados’, 1]]).
regra(‘Nivel de informatizacao e bom’, [[‘Hardware e software estao
atualizados’, 1], [‘Numero de computadores e satisfatorio’, 1]]).
regra(‘Ha viabilidade em terceirizar o servico’, [[‘Existe uma
empresa especializada no servico a ser terceirizado’, 1],
[‘Transporte e comunicacao com a empresa de
terceirizacao e caro’, 0],
[‘O servico da empresa de terceirizacao e caro’, 0]]).
regra(‘Investir em tecnologia ao inves de terceirizar o servico nao e
viavel’, [[‘Novas tecnologias para o setor a ser terceirizado sao
caras’, 1], [‘Pesquisa com os funcionarios aponta rejeicao
com a tecnologia da empresa de terceirizacao’, 1]]).
pergunta(Frase, Resposta) :- write(Frase), display(' ? (s ou n)
: '), read(SimOuNao),
trata_resposta(Frase, SimOuNao, Resposta).
trata_resposta(Frase, s, 1) :- assert(fato(Frase, 1)), !.
trata_resposta(Frase, _, 0) :- assert(fato(Frase, 0)).
conhecido(Frase) :- fato(Frase, _).
nao_perguntavel(Frase) :- conclusao(Frase, _).
nao_perguntavel(Frase) :- regra(Frase, _).
calcula_regra([], 1) :- !.
calcula_regra([[Frase, Esperado]|Calda], Resultado) :fato(Frase, Esperado), calcula_regra(Calda, Resultado), !.
calcula_regra([[Frase, Esperado]|Calda], Resultado) :regra(Frase, Condicoes), calcula_regra(Condicoes,
PreResultado), Esperado==PreResultado,
calcula_regra(Calda, Resultado), !.
calcula_regra([[Frase, Esperado]|Calda], Resultado) :not(conhecido(Frase)), not(nao_perguntavel(Frase)),
pergunta(Frase, PreResultado), Esperado==PreResultado,
calcula_regra(Calda, Resultado), !.
calcula_regra(_, 0).
resolve(Problema) :- retractall(fato(_, _)), conclusao(Problema,
Condicoes), calcula_regra(Condicoes, 1), !.
resolve('Não consegui chegar a nenhuma conclusão') :- !.
O predicado conclusao relaciona as informações que
podemos inferir para chegar a uma conclusão final do
problema bem como os fatores que determinam esta
inferência. O predicado regra relaciona todos as informações
que podemos inferir, exceto as inferências que nos levam a
uma conclusão. O predicado pergunta é utilizado quando
precisamos de uma informação mas não a temos, neste caso,
o predicado pergunta lê a resposta do usuário e trata esta
resposta.
O predicado trata_resposta utiliza a predicado assert de
PROLOG para inserir uma nova clausula chamada fato em
tempo de execução, esta clausula fato relaciona uma pergunta
e uma resposta dada pelo usuário. O predicado conhecido
verifica se já existe um fato (uma resposta do usuário)
relacionado a uma determinada pergunta. O predicado
nao_perguntavel verifica se uma certa pergunta não é do tipo
que o usuário pode responder, ou seja, se ela não é uma
pergunta e sim o resultado de uma inferência. O predicado
calcula_regra retorna o valor de uma certa inferência feita
através de um fato existente, do processamento de outras
regras ou de uma pergunta ao usuário. O predicado resolve
busca cada um dos problemas possíveis e verifica se algum está
ocorrendo. A seguir algumas execuções do programa:
?- resolve(Problema).
Funcionarios fazem hora-extra frequentemente ? (s ou n) : ? s.
Projetos estao atrasados ? (s ou n) : ? s.
As vendas aumentaram ? (s ou n) : ? s.
Hardware e software estao atualizados ? (s ou n) : ? s.
Numero de computadores e satisfatorio ? (s ou n) : ? n.
Problema = 'Ha necessidade de informatizar o setor’
Podemos verificar também se um determinado problema
está ocorrendo, a resposta será então do tipo yes ou no.
?- resolve('Ha necessidade de terceirizar o servico').
Existe uma empresa especializada no servico a ser terceirizado
? (s ou n) : ? s.
Transporte e comunicacao com a empresa de terceirizacao e
caro ? (s ou n) : ? n.
O servico da empresa de terceirizacao e caro ? (s ou n) : ? s.
no