Universidade de São Paulo
Instituto de Ciências Matemáticas e de Computação
Departamento de Ciências da Computação e Estatística
Primeiro Semestre de 1999
SCE 5774 - Introdução à Inteligência Artificial
Primeiro Projeto - Representação do Mundo dos Blocos
Humberto Costa de Sousa
Problema:
Considere o domínio do mundo dos blocos em que existe uma mesa que suporta 3 blocos nos quais podem ser empilhados outros blocos, e que a pilha possa ter qualquer altura. Estados neste domínio podem ser representados por uma lista de 3 listas. Por exemplo:
Ex: [[a,b,c],[d],[e,f]] = |
a |
||
|
b |
|
e |
c |
d |
f |
|
|
----- |
Escreva um programa imprime(estado) que imprime um dado Estado na forma visual acima.
Solução proposta:
A solução proposta para o problema foi considerar a lista de listas uma matriz.
Ex: [[a,b,c],[d],[e,f]] = |
a |
b |
c |
|
d |
|
|
|
e |
f |
A solução do problema foi então imaginada como a transposição da matriz acima, onde:
a |
b |
c |
|
a |
d |
e |
d |
|
|
= t => |
b |
|
f |
e |
f |
|
|
c |
|
Nota-se que a diferença entre a transposta da matriz e a representação desejada é a disposição dos elementos vazios da matriz. Esta disposição pode ser alterada invertendo os elementos das linhas da matriz, de maneira que:
a |
b |
c |
|
c |
b |
a |
d |
|
|
= i1 => |
d |
|
|
e |
f |
|
|
f |
e |
Uma vez invertida a ordem dos elementos da matriz, como ilustrado acima, a transposta da matriz com os elementos invertidos gerará:
c |
b |
a |
|
c |
d |
f |
d |
|
|
= t => |
b |
|
e |
f |
e |
|
|
a |
|
A matriz transposta difere da representação desejada apenas na ordem das linhas da matriz. Como a matriz é representada através de uma lista de listas, basta então inverter a ordem das listas desta lista, de maneira que:
c |
d |
f |
|
a |
||
b |
|
e |
= i2 => |
b |
|
f |
a |
|
|
c |
d |
e |
Assim, alcançamos o objetivo do trabalho.
Mecanismos necessários para a solução do problema:
O problema foi resolvido através da manipulação de listas. Três operações foram utilizadas:
A inversão de elementos de uma lista foi facilmente resolvido através de:
inverte([X|Y],Tmp,Saida) :-
inverte(Y,[X|Tmp],Saida).
inverte([],X,X).
Onde elementos da lista de entrada são retirados um a um e colocados em uma lista temporária. Quando a lista de entrada torna-se vazia, a lista temporária é copiada para a lista de saída.
A transposição da matriz foi resolvida em três passos:
transpoe(MatrizA, MatrizB) :-
transpoe2(MatrizA, MatrizB, Tmp).
transpoe2(MatrizA, [LinhaB|RestoB], MatrizC) :-
transp_aux(MatrizA, LinhaB, MatrizC),
transpoe2(MatrizC, RestoB, _).
A quebra da recursão de transpoe2 é feita através da verificação da existência de apenas listas vazias em MatrizA o que indica que não é necessário transpor novos elementos:
transpoe2(Matriz,[],[]) :-
vazio(Matriz).
transp_aux([ [Elem|RestoLinhaA] | Resto], [Elem|RestoB], [RestoLinhaA|XX]) :-
transp_aux(Resto, RestoB, XX ).
Para transformar as posições vagas da matriz em espaços em branco, é chamada:
transp_aux([[]|Resto], [' '|RestoB], [[]|XX]) :-
transp_aux(Resto, RestoB, XX).
E para quebrar a recursão, retornando uma lista de elementos a serem transpostos vazia, é chamada:
transp_aux([],[],[]).
A verificação se a lista é composta de listas vazias é feita através de simples comparações:
vazio([]).
vazio([A|Resto]) :-
A == [],
vazio(Resto).
Uma descrição mais detalhada pode ser observada no arquivo block.pl que implementa a solução descrita acima.
Obs.: A solução proposta não limita que o número de blocos seja 3, permitindo que qualquer número de blocos seja representado.
Testes:
Aqui estão listados os resultados de alguns testes utilizando a implementação da solução proposta.
?- imprime([[a,b,c],[d],[e,f]]).
a |
||
b |
e |
|
c |
d |
f |
--------------
yes
?- imprime([[a,b],[d,e,f,g],[h,i]]).
d |
||
e |
||
a |
f |
h |
b |
g |
I |
--------------
yes
?- imprime([[a,b],[d,e,f,g],[h,i],[j,k,l],[m],[n,o]]).
d |
|||||
e |
j |
||||
a |
f |
h |
k |
n |
|
b |
g |
i |
l |
m |
o |
--------------
yes
?- imprime([[a],[b,c]]).
b |
|
a |
c |
--------------
yes
?- imprime([[],[b,c],[d,e,f]]).
d |
||
b |
e |
|
c |
f |
--------------
yes
?- imprime([[],[],[e,f,g]]).
e |
||
f |
||
g |
--------------
yes
?- imprime([[],[],[]]).
--------------
yes