Declaratieve Talen/Oplossing Minimale Snede

Oplossing niet volledig maar het moeilijkste stuk is er:

boog(a,b,1).
boog(a,c,1).
boog(b,c,1).
boog(c,z,3).
boog(b,z,1).


min_cut(Snede,Kost) :-
	findall((Snede,Kost),min_snede(Snede,Kost),R),
	min(R,Snede,Kost).
	
min([(Snede,Kost)],KortsteSnede,LaagsteKost) :-
	KortsteSnede = Snede,
	LaagsteKost = Kost.
	
min([(Snede,Kost)|Rest],KortsteSnede,LaagsteKost) :-
	KortsteSnede = Snede,
	LaagsteKost = Kost.


min_rnd_snede(Snede, Kost) :-
	knopen(Knopen),
	permu(Knopen, [K|PKnopen]),
	min_snede_perm([K],PKnopen,Snede,Kost).

	

%gegeven een zeker permutatie/volgorde van de knopen: ga alle snedes af 
min_snede_perm(X,[Y],KortsteSnede,Lengte) :-
	kost(snede(X,[Y]),Lengte),
	KortsteSnede = snede(X,[Y]).
min_snede_perm([X1|X1rest],[X2|X2rest], KortsteSnede, LengteKortsteSnede) :-
	min_snede_perm([X2,X1|X1rest],X2rest,KortsteSubSnede,LengteKortsteSubSnede),
	kost(snede([X1|X1rest],[X2|X2rest]),Kost),
	(Kost < LengteKortsteSubSnede ->
	LengteKortsteSnede = Kost,
	KortsteSnede = snede([X1|X1rest],[X2|X2rest]);
	KortsteSnede = KortsteSubSnede,
	LengteKortsteSnede = LengteKortsteSubSnede	
	).

%bereken de kost van een snede
kost(snede([],_),Y) :- Y = 0.
kost(snede([X|Xs],Y),Result) :-
	findall(Kost, ((boog(X,Z,Kost);boog(Z,X,Kost)),elementvan(Z,Y)),Kosten),
	sum(Kosten,TotaleKostX),
	kost(snede(Xs,Y),RecurResult),
	Result is RecurResult + TotaleKostX.

%element van
elementvan(X,[L|Lijst]) :-
	X == L;
	elementvan(X,Lijst).

%bereken de som van een rij
sum([],R) :- R = 0.
sum([X],R) :- R = X.
sum([L|List], R) :-
	sum(List, Recur),
	R is Recur + L.

%alle knopen van de graaf
knopen(Result) :-
	findall(X,(boog(_,X,_);boog(X,_,_)),Knopen),
	list_to_set(Knopen,Result).

%permutates the list
permu([],[]).
permu(X,[Y|Ys]) :- 
	del(Y,X,Rs),
	permu(Rs,Ys).
	
%deletes X from the list
del(X,[X|Xs],Xs).
del(X,[Y|Ys],[Y|Zs]) :- 
	del(X,Ys,Zs).  

Een alternatief

boog(a,b,1).
boog(a,c,1).
boog(b,c,1).
boog(c,z,3).
boog(b,z,1).

mincut(X,Y) :-
	findall((Opl,L),oplossingen([a],Opl,L),Rij),
	sort(Rij,Sorted),
	last(Sorted,Last),
	neem_minimum(Sorted,Last,(L,Y)),
	alle_knopen(All),
	vind_rechterdeel(All,L,[],R),
	X = (L,R).

neem_minimum([],Res,Res).
neem_minimum([(Links,Som)|Xs],(LL,SS),(Lres,Sres)) :-
	( Som < SS ->
		neem_minimum(Xs,(Links,Som),(Lres,Sres))
	;
	 neem_minimum(Xs,(LL,SS),(Lres,Sres))).



is_bereikbaar(X,Rij,Return) :-
	findall(B,(boog(X,B),\+ member(B,Rij)),R),
	delete(R,z,Return).

alle_knopen(Result) :-
	findall(X,boog(X,_,_),Rij1),
	findall(Y,boog(_,Y,_),Rij2),
	append(Rij1,Rij2,Rij),
	sort(Rij,Result).

% Alle knopen, Linkerdeel, res en res
vind_rechterdeel([],_,Res,Res).
vind_rechterdeel([X|Rest],Rij,Res,Result) :-
	( member(X,Rij) ->
		vind_rechterdeel(Rest,Rij,Res,Result)
	;
	  vind_rechterdeel(Rest,Rij,[X|Res],Result)).

som_rij([],Res,Res).
som_rij([X|Xs],SubRes,Res) :-
	NSubRes is SubRes + X,
	som_rij(Xs,NSubRes,Res).

% Linkerdeel, rechterdeel, result
bereken_som(Links,Rechts,Som) :-
	findall(L,(boog(X,Y,L),member(X,Links),member(Y,Rechts)),Rij),
	som_rij(Rij,0,Som).

% Je zit in, linkerdeel, result
oplossingen(Res,Res,Som) :- 
	alle_knopen(Knopen),
	vind_rechterdeel(Knopen,Res,[],Rechts),
	bereken_som(Res,Rechts,Som).
oplossingen(Rij,Result,L) :-
	member(M,Rij),
	boog(M,B,_),
	B \== z,
	\+ member(B,Rij),
	append(Rij,[B],Verder),
	oplossingen(Verder,Result,L).

--Beau 15 jun 2006 11:51 (CEST)

Een ander alternatief

buur(X,Y,N) :-
       (boog(X,Y,N) ; boog(Y,X,N)).
            
find(X,Y,snede([X|Z],[Y|W])) :-
       findall(A,buur(A,_,_),L),
       list_to_set(L,La),
       permutation(La,R),
       append([[X,Y],Z,W],R).
        
       
mincut(X,Y) :-
       findall(C-B,(find(a,b,B), capaciteit(B,C)),L),
       keysort(L,[Xs-_|R]),
       partition(gelijk(Xs),R,Gelijken,_),
       pairs_values(Gelijken,Values),
       findall(C-B,(member(B,Values), gesneden_bogen(B,C)),A),
       keysort(A,[X-Y|_]).
       
       
gelijk(Xs,Xs-_).  
         
capaciteit(snede(Xs,Ys), C) :-
       findall(N, (member(X,Xs), member(Y,Ys), buur(X,Y,N)),L),
       sumlist(L,C).
         
gesneden_bogen(snede(Xs,Ys), C) :-
       findall(N, (member(X,Xs), member(Y,Ys), buur(X,Y,N)),L),
       length(L,C).