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
Profa.: Sandra Maria Aluísio
e-mail: sandra@icmsc.sc.usp.br
Aluno: Pastor W. Gonzales Taco
e-mail: pastor@sc.usp.br
Primeiro Projeto: Crypto-arithmetic Puzzles
1. Enunciado do Problema
2. Estrutura do Programa em Prolog
3. Características Necessárias para Resolução
4. Teste do Programa
5. Conclusões
1. Enunciado do Problema
Crypto-arithmetic Puzzles. Implemente um resolvedor genérico de puzzles aritméticos como o clássico:
** SEND
** +MORE
** -------
** MONEY
O objetivo deste jogo é atribuir um digito a cada letra em SEND e MORE e então adicionar aqueles valores como um problema matemático normal e obter MONEY como resposta. Faça um programa genérico, com a restrição de que 2 números para ser adicionados tenham o mesmo número de digitos e a solução um digito a mais (veja que send e more tem 4 digitos e money 5). Outra entrada:
[C,R,O,S,S] + [R,O,A,D,S] = [D,A,N,G,E,R].
2. Estrutura do Programa em Prolog
main:-
write($Puzzle? $),
read(Puzzle),
solve(Puzzle),
write(Puzzle),nl,
fail.
main:- write($no more$),nl.solve([A|At] + [B|Bt] = [C0,C|Ct]) :-
permutation([A,B,C0,C], [0,1,2,3,4,5,6,7,8,9],L),
A \= 0, B \= 0, C0 \= 0,
(X = 0; X = 1),
A + B + X =:= 10 * C0 + C,
solve2(At+Bt=Ct,X,L).solve2([A] + [B] = [C], X, L) :-
permutation([A,B,C],L,_),
(X = 0, A + B =:= C; X = 1, A + B =:= 10 + C).
solve2([A|At] + [B|Bt] = [C|Ct], X, L) :-
permutation([A,B,C],L,L1),
(X1 = 0; X1 = 1),
(X = 0, A + B + X1 =:= C; X = 1, A + B + X1 =:= 10 + C),
solve2(At + Bt = Ct, X1,L1).permutation([],L,L).
permutation([A|X],Y,L) :- atomic(A), permutation(X,Y,L).
permutation([A|X],Y,L) :- remove(A,Y,Y1), permutation(X,Y1,L).remove(A,[A|X],X).
remove(A,[B|X],[B|Y]) :- remove(A,X,Y).
3. Características Necessárias para Resolução
Em uma variedade de problemas de inteligência artificial, determinados valores podem ser asinados a um número de variaveis sujeitas a certas restrições. Uma abordagem comum para resolver esses problemas é atravez da geração e teste de valores. Este proceso consiste em escolhendo algums valores para cada variável, e testando-os para determinar se a combinação de tais valores satisfaz as restrições. De ser assim o problema é resolvido, se não, escolhe-se um novo conjunto de valores os quais são asignados as variáveis, para provar outra vez. Em outras abordagems procura-se a geração, teste e permutação de valores. Antes de passar a ver como funciona o programa, primeiro veremos a seguir alguns aspectos relacionados com os predicados e termos usados do Prolog no programa.
Entrada e Saida:
read(X) Este predicado destina-se à leitura de termos do teclado.Todo o termo escrito deve terminar com um ponto ( . ). Este termo podeser uma palavra isolada, uma lista de letras ou ainda um string de caracteres. No caso do programa perante o predicado write($Puzzle? $) ao escrever a sintaxe do Puzzle, o sistema encarará o Puzzle como um argumento associado à variável X.
write(X) Imprime termos associados a X. São válidas as mesmasobservações feitas para read.
nl Provoca a quebra da linha, sendo que o próximo comando deimpressão iniciará numa nova linha.
No programa podemos ver estes predicados de entrada e saida
write($Puzzle? $),
read(Puzzle),
solve(Puzzle),
write(Puzzle),nl,
Variáveis: As variáveis são utilizadas de acordo com o comando, e deve começar com letra maiúscula. A variável é o elemento mais útil para a formulação de questões. Em cima das questões com variáveis é que serão construídos os sistemas mais complexos de estruturação da representação de conhecimentos.
Regras: É o comando na forma:
remove(A,[B|X],[B|Y]) :- remove(A,X,Y).
Onde o símbolo :- indica a uma condição (se) ou, no caso de compararmos com lógica de predicados, a uma implicação material. A regra é o instrumento básico de organizaçãodo banco de conhecimentos e permite a construção de questõescomplexas (formas mais sofisticadas de consulta ao banco de dados). É ela que indica a validade de um conjunto de fatos, questões ou conjunções. Percebemos, então, que há a possibilidade de construçãode produções complexas em cada regra, permitindo conceitoscada vez maiores e consultas com um maior nível de definição e de variáveis.
Relacionais: Operadores numéricos relacionais são aqueles usadospara realizar testes quantitativos entre dois números. Alguns dos utilizados (existindo outros) no programa são: = (igual), \= (diferente).
Aritméticos: Operadores aritméticos são os utilizados na aritmética básica e os utilizados aqui são: + (soma), * (multiplicação).
A \= 0, B \= 0, C0 \= 0,
(X = 0; X = 1),
A + B + X =:= 10 * C0 + C,
Deste modo, percebemos que há a possibilidade de construçãode diversas funções matemáticas mais complexas a partirde regras e operadores relacionais e aritméticos. De fato existem funções matemáticas mais complexas já implementadas em Prolog.
Estruturas de Dados: As estruturas servem para aninhaar dados de forma organizada, estruturada. Elas permitem a distinção de atributos para um argumento. A estrutura de dados já é criada em qualquer tipo de comando Prolog, de forma que devemos ter em mente sempre esta estruturação para mais facilmente compreendermos a funçãodo comando que estamos analisando ou trabalhando. Obviamente as estruturas em Prolog não resumem-se à forma de seus comandos. Podemos construir estruturas de dados mais complexaspara auxiliar na implementação de aplicações.
Listas: A forma mais adequada para estruturação de dados emProlog são as listas. Como o nome diz, são estruturas dinâmicasde armazenamento de dados. Elas são utilizadas na construçãode vetores e matrizes dinâmicos de caracteres, números, equaisquer outros dados utilizados. Alem disso há um conceito importante para a utilização das listas é o cabeça-corpo ( | ). Ele é usado para isolarmembros de uma lista. Como podemos observar, o operador | permite a separaçãoda cabeça da lista de seu corpo. Isso permite o isolamento dos membrosda lista, facilitando sua análise. No programa apresentam-se na forma:
solve([A|At] + [B|Bt] = [C0,C|Ct]) :-
permutation([A,B,C0,C], [0,1,2,3,4,5,6,7,8,9],L),
As listas são o principal tipo de estrutura de dados em Prolog, com as quais é possível a construção de vetores e matrizes, com a vantagem de ser uma estrutura de memória dinâmica.
Um resolvedor genérico de
Puzzles Aritméticos, como o clássico: SEND + MORE = MONEY, tem
como objetivo atribuir um digito a cada letra em SEND e MORE e
então somar esses valores como um problema de matemática normal
obtendo MONEY como resposta. Expressando o problema na forma de
três listas de letras de variáveis ligadas por operadores,
pode-se enfrentar a solução do problema, com aplicação de
algumas restrições. O puzzle a resolver é um simples termo em
Prolog de variáveis com uma mesma letra em comum, tal como o Es
em SEND MORE MONEY,
a qual será restringida para ter o mesmo valor. Os
valores que assuman as variáveis serão positivas, e no conjunto
de {0,1,2,3,4,5,6,7,8, 9}. A relação definida para as
variáveis será preservada por
unificação com as listas que compõem as palavras, definidas no
programa, sendo que atravesarão varios níveis recursivos para
resolver até resolver (solve)o problema.
solve([A|At] + [B|Bt] = [C0,C|Ct])
O backtracking para o predicado da
permutação (permutation) produz números
diferentes para serem asignados às variáveis, isso na procura
de soluções para o programa. Porém o programa resolverá o
problema permutando os valores das letras e aplicando as
restrições, se as restrições falham, o programa voltará a
permutar até a resposta ser achada.
permutation([A,B,C0,C], [0,1,2,3,4,5,6,7,8,9],L),
As permutações no programa alocam
diferentes valores para as variáveis na primeira lista desde os
valores na segunda. A terceira lista é a lista de valores sem
serem alocados. Esta trabalha apagando elementos da lista que
usa. Assim, apaga o próximo elemento e fixa simplesmente seus
valores para a variável, provendo assim um modo simples para
nomear e permutar valores para uma lista de variáveis. Ao
voltar, as variáveis são apagadas para o próximo elemento da
lista, gerando assim eventualmente todas as permutações de uma
lista.
permutation([],L,L).
permutation([A|X],Y,L) :- atomic(A), permutation(X,Y,L).
permutation([A|X],Y,L) :- remove(A,Y,Y1), permutation(X,Y1,L).remove(A,[A|X],X).
remove(A,[B|X],[B|Y]) :- remove(A,X,Y).
O processso de ressolução torna-se recursivo até chegar à solução, ou soluções do Puzzle.
4. Teste do Programa
O programa assim elaborado para ser testado e rodado fazendo uso do software Amzi! 3.3 Prolog. Assim o arquivo puzzle_1.pro contendo o programa, foi compilado e linkado junto ao Amzi! Compiler e Amzi! Linker, respectivamente, como é mostrado a seguir:
O programa apresentado (puzzle_1.pro), poderá resolver problemas, com a restrição que os dois números a serem somados tenham o mesmo número de dígitos, e a solução tem um dígito a mais. Nenhum dos primeiros dígitos pode ser zero, podendo o programa ser modificado para ser mais geral.
A seguir no Amzi! prosseguisse a rodar o programa. Para isso na barra de ferramentas seleccione o comando Listener e logo Star, aparecerá inmediatamente uma janela de consulta. Ir de novo na barra de ferramentas e em Listener seleccionar Consult..., na janela ativa será chamado o arquivo contendo o programa (puzzle_1.pro). Prossiga escrevendo main. e logo o puzzle da forma mostrada na figura a seguir:
Após esse processo deve-se obter os seguinte resultado: [9,5,6,7] + [1,0,8,5] = [1,0,6,5,2]
Pode acontecer problemas na resolução do programa, devido a pouca capacidade na memoria do seu computador. Nesses casos você terá que utilizar Amzi! no "Prompt do MS-DOS", e rodar o programa puzzle_1.pro como pode ser visto a seguir:
- Crie um diretorio onde estejam localizados o arquivo puzzle_1.pro e o arquivo executable do Amzi! arun.exe
- Digite arun na linha de entrada, e de enter.
- O Prolog pedirá digitar o nome do programa para rodar, então digite puzzle_1.pro e de enter
- O progama solicitará o Puzzle? para testar. Digite: [S, E, N, D] + [M, O, R, E] = [M, O, N, E, Y]
- Após digitar o Puzzle aparecerá o(s) resultado(s). Para nosso primeiro teste temos somente um resultado, como pode ser observado na figura a seguir: [9,5,6,7] + [1,0,8,5] = [1,0,6,5,2]
- Pode-se testar outros Puzzles, como o proposto no inicio: [C, R, O, S, S] + [R, O, A, D, S] = [D, A, N, G, E, R] obtendo a solução unica: [9,5,6,7] + [1,0,8,5] = [1,0,6,5,2]
- Um outro Puzzle para teste que nos permite obter 35 alternativas de solução é o seguinte:
- Já para o Puzzle [ L, U, A, N, A] + [A, N, D, R, E] = [J, A, V, I, E, R] criado especificamente para testar um número menor de soluções, obtem-se 8 alternativas de solução, como pode ser observado na figura a seguir:
5. Conclusões
O uso de um número limitado de listas, principal tipo de estrutura de dados em Prolog, oferece uma grande vantagem ao permitir uma estrutura de memória dinâmica.
A asignação de diferentes números para as variáveis é possibilitado pelo processo de backtracking do predicado da permutação (permutation). Esse recurso possibilita a escolha de uma gama diverssa de soluções para o puzzle.
O processo de permutação é resolvido permutando os valores das letras e aplicando as restrições, se as restrições falham, o programa voltará a permutar até a resposta ser achada. A definição adecuada das restrições poderá facilitar na resolução do puzzle.
Observa-se que dependendo do tipo de puzzle o número de soluções variará. Assim o processo de recursão nas permutações pode tornar-se insoluvel, ou com várias soluções.
Bibliografia: