Uso de não determinismo
Exemplo
Problema dos casamentos estáveis
• Existe um conjunto de N homens e um conjunto de N
mulheres que querem casar.
• Cada homem tem associada uma lista com todas as
mulheres por ordem decrescente das suas preferências
para casamento.
– Idem para cada mulher (que tem uma lista de todos os
homens por ordem decrescente das suas preferências).
• O problema é encontrar um conjunto de casamentos
que sejam todos estáveis.
• Os casamentos são instáveis se existe um homem e
uma mulher que se preferem mais entre eles que aos
seus esposos.
Instabilidade
•
•
Existe um conjunto de N homens e um conjunto de N mulheres que
querem casar.
Cada homem tem associada uma lista com todas as mulheres por ordem
decrescente das suas preferências para casamento.
– Idem para cada mulher (que tem uma lista de todos os homens por ordem
decrescente das suas preferências).
•
•
O problema é encontrar um conjunto de casamentos que sejam todos
estáveis.
Os casamentos são instáveis se existe um homem e uma mulher que se
preferem mais entre eles que aos seus esposos.
• Exemplo de par de casamentos instáveis:
Manuel : Paula (Manuel preferia a Maria)
Pedro : Maria (Maria preferia o Manuel)
N=3
Homens
Preferências
Mulheres
Preferências
Zé
Ana, Rita, Inês
Ana
Rui, Zé, Ivo
Rui
Inês, Ana, Rita
Rita
Zé, Rui, Ivo
Ivo
Ana, Inês, Rita
Inês
Zé, Ivo, Rui
Conjuntos estáveis ?
Zé : Ana
Rui : Inês
Ivo : Rita
Zé : Ana
Ivo : Inês
Rui : Rita
Rui : Ana
Ivo : Inês
Zé : Rita
X
X

Prolog
• O predicado deverá receber uma lista de homens com as
suas preferências e uma lista de mulheres com as suas
preferências e devolver uma lista de pares
homem/mulher com os casamentos.
• Um exemplo duma chamada deste predicado poderá ser:
?- casamentos(
[h(pedro,[maria,paula]), h(manuel,[paula,maria])],
[m(maria,[pedro,manuel]), m(paula,[pedro,manuel])],
C).
C = [c(pedro,maria), c(manuel,paula)] ;
no
Aproveitar o não determinismo
• Ir (não deterministicamente) gerando casais
– Testando estabilidade com os já gerados
• Gerar casais:
– Para cada homem, escolher uma mulher solteira
casamentos(Homens,Mulheres, Casais) :acasala(Homens,Mulheres, [], Casais).
acasala([],[],_,[]).
acasala([h(Homem,PrefsH)|HRest],Ms, Casados,[c(Homem,Mulher)|Cs]) :% escolher Mulher
% testar estabilidade
acasala(HRest,MRest, [c(Homem:PrefsH,Mulher:PrefsM)|Casados],Cs).
Escolher uma mulher…
• member/2 ?
– É preciso memorizar as que ainda ficam solteiras
• Solução: select/3
my_select(X, [X|R], R).
my_select(X, [H|T], [H|R]):- my_select(X, T, R).
• Ficaria: my_select(m(Mulher,_), Ms, MRest)
• Com heurística (tentar 1º as mais preferidas):
member(Mulher, PrefsH),
my_select(m(Mulher,PrefsM), Ms, MRest)
Acasalar…
acasala([],[],_,[]).
acasala([h(Homem,PrefsH)|HRest],Ms, Casados,[c(Homem,Mulher)|Cs]) :member(Mulher,PrefsH),
%Heurística: tenta 1º as + preferidas
my_select(m(Mulher,PrefsM), Ms, MRest),
% testar estabilidade
acasala(HRest,MRest, [c(Homem:PrefsH,Mulher:PrefsM)|Casados],Cs).
• Teste de estabilidade
\+ instavel(c(Homem:PrefsH,Mulher:PrefsM), Casados)
Instabilidade
𝑖𝑛𝑠𝑡á𝑣𝑒𝑖𝑠 𝐶𝑠, 𝑃𝑟𝑒𝑓𝑠 ↔
∃<ℎ1,𝑚1>,<ℎ2,𝑚2>∈𝐶𝑠 (𝑝𝑟𝑒𝑓𝑇𝑟𝑜𝑐𝑎𝑟(ℎ1, 𝑚2, 𝑃𝑟𝑒𝑓𝑠) ∨ 𝑝𝑟𝑒𝑓𝑇𝑟𝑜𝑐𝑎𝑟(ℎ2, 𝑚1, 𝑃𝑟𝑒𝑓𝑠))
𝑝𝑟𝑒𝑓𝑇𝑟𝑜𝑐𝑎𝑟 ℎ, 𝑚, 𝑃𝑟𝑒𝑓𝑠 ↔
(𝑝𝑟𝑒𝑓𝑒𝑟𝑒(ℎ, 𝑚, 𝑐𝑜𝑛𝑗𝑢𝑔𝑒 ℎ , 𝑃𝑟𝑒𝑓𝑠) ∧ 𝑝𝑟𝑒𝑓𝑒𝑟𝑒(𝑚, ℎ, 𝑐𝑜𝑛𝑗𝑢𝑔𝑒(𝑚), 𝑃𝑟𝑒𝑓𝑠))
instavel(c(H1:PrefsH1,M1:PrefsM1), [c(H2:PrefsH2,M2:PrefsM2)|_]):preferem_trocar(H1,M1, H2,M2, PrefsH1,PrefsM2)
;
preferem_trocar(H2,M2, H1,M1, PrefsH2,PrefsM1).
instavel(Casal, [_|Cs]):- instavel(Casal, Cs).
Preferir trocar
𝑝𝑟𝑒𝑓𝑇𝑟𝑜𝑐𝑎𝑟 ℎ, 𝑚, 𝑃𝑟𝑒𝑓𝑠 ↔
(𝑝𝑟𝑒𝑓𝑒𝑟𝑒(ℎ, 𝑚, 𝑐𝑜𝑛𝑗𝑢𝑔𝑒 ℎ , 𝑃𝑟𝑒𝑓𝑠) ∧ 𝑝𝑟𝑒𝑓𝑒𝑟𝑒(𝑚, ℎ, 𝑐𝑜𝑛𝑗𝑢𝑔𝑒(𝑚), 𝑃𝑟𝑒𝑓𝑠))
%H1 (casado com M1) e M2 (casada com H2)
%preferem trocar entre eles
preferem_trocar(H1,M1, H2,M2, PrefsH1,PrefsM2):antes(PrefsH1, M2,M1),
antes(PrefsM2, H1,H2).
%antes(Prefs, X,Y) :- X está antes de Y em Prefs.
antes([X|_], X,_):- !.
antes([Y|_], _,Y):- !, fail.
antes([_|L], X,Y):- antes(L, X,Y).
casamentos(Homens,Mulheres, Casais) :- acasala(Homens,Mulheres, [], Casais).
acasala([],[],_,[]).
acasala([h(Homem,PrefsH)|HRest],Ms, Casados,[c(Homem,Mulher)|Cs]) :member(Mulher,PrefsH),
%Heurística: tenta 1º as + preferidas
my_select(m(Mulher,PrefsM), Ms, MRest),
\+ instavel(c(Homem:PrefsH,Mulher:PrefsM), Casados),
acasala(HRest,MRest, [c(Homem:PrefsH,Mulher:PrefsM)|Casados],Cs).
instavel(c(H1:PrefsH1,M1:PrefsM1), [c(H2:PrefsH2,M2:PrefsM2)|_]):preferem_trocar(H1,M1, H2,M2, PrefsH1,PrefsM2)
;
preferem_trocar(H2,M2, H1,M1, PrefsH2,PrefsM1).
instavel(Casal, [_|Cs]):- instavel(Casal, Cs).
%H1 (casado com M1) e M2 (casada com H2) preferem trocar entre eles
preferem_trocar(H1,M1, H2,M2, PrefsH1,PrefsM2):antes(PrefsH1, M2,M1),
antes(PrefsM2, H1,H2).
%antes(Prefs, X,Y) :- X está antes de Y em Prefs.
antes([X|_], X,_):- !.
antes([Y|_], _,Y):- !, fail.
antes([_|L], X,Y):- antes(L, X,Y).
my_select(X, [X|R], R).
my_select(X, [H|T], [H|R]):- my_select(X, T, R).