Universidade Federal de Santa Catarina
Departamento de Automação e Sistemas
Programa de Pós-Graduação em Engenharia de Automação e Sistemas
Inteligência Artificial
Professor: Jomi F. Hübner
|
Universidade Federal de Santa Catarina
|
|
Para realizar os experimentos com é necessário o GNU Prolog.
% Resolução de CSP com GNU Prolog
%
% Exemplo básico:
% variáveis:
% X1, X2, X3
% domínios:
% X1: {1, 2}
% X2: {2}
% X3: {1, 2}
% restrições (\= significa diferente):
% X1 \= X3
% X2 \= X3
%
% Para executar, digite em uma shell de comandos:
% gprolog --query-goal "consult('explo-basico'), resolve, halt"
resolve :-
% cria uma lista com todas as variáveis
Todas = [X1, X2, X3],
% cria as variáveis e os domínios
fd_domain(X1, [1,2]),
fd_domain(X2, [2]),
fd_domain(X3, [1,2]),
% restrições
X1 #\= X3,
X2 #\= X3,
% resolve o CSP
fd_labeling( Todas ),
% imprime resultado
write('X1 = '), write(X1), nl,
write('X2 = '), write(X2), nl,
write('X3 = '), write(X3), nl.
% variáveis: supondo uma rainha por linha,
% as variáveis representam as colunas das
% rainhas: R1, R2, R3, R4
% domínios:
% Ri: {1..4}
% restrições (|....| significa módulo):
% Ri \= Rj
% | i-j | \= |Ri - Rj|
%
% Para executar, digite em uma shell de comandos:
% gprolog --query-goal "consult('4-rainhas'), resolve, halt"
resolve :-
% cria uma lista com todas as variáveis
Todas = [R1, R2, R3, R4],
% cria as variáveis e os domínios (valores de 1 a 4)
fd_domain(Todas, 1, 4),
% restrições
fd_all_different(Todas), % todas devem ter valores diferentes
% diagonais (dist retorna a diferença entre as variáveis)
1 #\= dist(R1, R2),
2 #\= dist(R1, R3),
3 #\= dist(R1, R4),
1 #\= dist(R2, R3),
2 #\= dist(R2, R4),
1 #\= dist(R3, R4),
% resolve o CSP
fd_labeling( Todas ),
% imprime resultado
write('R1 = '), write(R1), nl,
write('R2 = '), write(R2), nl,
write('R3 = '), write(R3), nl,
write('R4 = '), write(R4), nl.
Três macacos sábios têm os seguintes nomes: Zé, Chico e Tonho. Seu sobrenomes são Galho, Banana e Pulo, não necessariamente nesse ordem. Um deles não vê, outro não fala e outro não ouve, também não necessariamente nesse ordem. Zé lamenta que seu amigo Galho não possa ouvir. Chico e Pulo adoram ver as macaquices mútuas. Aquele que não ouve vive assistindo às provocações entre Tonho e Banana. Qual o nome completo e a característica de cada um?
% run with
% gprolog --query-goal "consult(macacos), resolve, halt"
resolve :-
Todas = [Ze, Ch, Tn, Ga, Bn, Pl, Cg, Md, Sr],
fd_domain(Todas,1,3),
fd_all_different([Ze, Ch, Tn]),
fd_all_different([Ga, Bn, Pl]),
fd_all_different([Cg, Md, Sr]),
Ze #\= Ga,
Ga #= Sr,
Ze #\= Sr,
Tn #\= Bn,
Sr #\= Tn,
Sr #\= Bn,
Ch #\= Pl,
Ch #\= Cg,
Pl #\= Cg,
fd_labeling(Todas),
write('nomes [Ze, Ch, Tn] = '), write([Ze, Ch, Tn]), nl,
write('sobre nomes [Ga, Bn, Pl] = '), write([Ga, Bn, Pl]), nl,
write('deficiencias [Cg, Md, Sr] = '), write([Cg, Md, Sr]), nl,
nl.
Suponha que você precisa comprar adubo para melhorar a qualidade do solo de uma determinada propriedade. São necessários 500 Kg de adubo com a seguinte composição mínima:
Existem 3 tipos de adubos para comprar, cada um com uma determinada composição e preço, conforme a tabela abaixo:
| Adubo 1 | Adubo 2 | Adubo 3 | |
| Nitrato | 8% | 4% | 3% |
| Fósforo | 15% | 17% | 14% |
| Potássio | 10% | 10% | 7% |
| Custo Kg | $ 1,50 | $ 1,00 | $ 0,70 |
Pergunta-se: quantos Kg devem ser comprados de cada tipo de adubo para atender os requisitos e ter o menor valor final a pagar?
% Resolucao de CSP com GNU Prolog
%
% Exemplo Orimizacao na Compra de Adubo
%
% Para executar, digite em uma shell de comandos:
% gprolog --query-goal "consult('adubo.pl'), resolve, halt"
%
% by Jomi
resolve :-
% cria uma lista com todas as variaveis
Todas = [A1, A2, A3],
Qtd = 500, % Qtd de adubo a ser comprada
% cria as variaveis e os dominios (valores de 1 a Qtd)
fd_domain(Todas, 0, Qtd),
% restricoes
% qtd de nitrato
((A1*8) + (A2*4) + (A3*3)) #>= (4*Qtd),
% qtd de fosforo
((A1*15) + (A2*17) + (A3*14)) #>= (14*Qtd),
% qtd de potassio
((A1*10) + (A2*10) + (A3*7)) #>= (8*Qtd),
A1 + A2 + A3 #= Qtd,
% custo
C #= A1 * 15 + A2 * 10 + A3 * 7,
% otimiza o CSP
fd_minimize(fd_labeling(Todas), C),
% imprime resultado
write('A1 = '), write(A1), nl,
write('A2 = '), write(A2), nl,
write('A3 = '), write(A3), nl,
write('Custo='), write(C), nl.
Fazer os exemplos de coloração de mapas, quadrado mágico e do escalonamento de tarefas (enunciados vistos em sala).
Avalie o desempenho de diferentes heurísticas. Veja na seção 8.9 do manual do GProlog (``Labeling constraints'') como determinar as heurísticas utilizadas.