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

Elfangor

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).

Een alternatief dat gebruik maakt van een bekend universeel zoekalgoritme

--Nick.dewaele (overleg) 16 jan 2018 19:49 (CET)

boog(a,b,1).
boog(a,c,1).
boog(b,d,1).
boog(c,d,1).
boog(d,z,2).

neighbor(X, Y) :- boog(X,Y,_); boog(Y, X, _).
vertices(V) :- findall(X, neighbor(X, _), Xs), sort(Xs, V).
edges(E) :- findall(e(X,Y,W), boog(X,Y,W), E).
weight(e(_,_,W), W).

% Dit predicaat vindt alle bogen tussen knopen uit V en knopen uit W
edgesbetween(V, W, Res) :-
    findall(e(X,Y,Weight), (
        (member(X, V),
        member(Y, W)
        ;
        member(Y,V),
        member(X, W)
        ),
        boog(X,Y,Weight)
    ), Res).

sumWeightEdges(V, W, Sum) :-
    edgesbetween(V, W, E),
    maplist(weight, E, Weights), % dit is de "map" van Haskell
    sum_list(Weights, Sum).

mincut(X,Y) :-
    vertices(Vert),
    findall(V, (member(V, Vert), \+member(V,[a,z])), InternalNodes),
    sumWeightEdges([a], [z], InitCost),
    dijkstra([InitCost-state([a], [z], InternalNodes)], X-Y).


dijkstra([Cost-state(Left,Right,[V|Unassigned]) | Q], Res) :-
    % voeg eerst toe aan de linkerkant
    sumWeightEdges([V], Right, SL),
    CostL is Cost + SL,
    LeftChild = CostL-state([V|Left], Right, Unassigned),
    % en dan rechts
    sumWeightEdges([V], Left, SR),
    CostR is Cost + SR,
    RightChild = CostR-state(Left, [V|Right], Unassigned),

    insertPQ([LeftChild, RightChild], Q, NewQ),
    dijkstra(NewQ, Res).

dijkstra([Cost-state(Left, Right, [])|Q], Cost-cut(L,R)) :-
    % De eerste op de wachtrij is nu optimaal. Als er andere doelen zijn met dezelfde kost,
    % dan staan die nu ook op de wachtrij. Dit is altijd het geval tenzij er bogen zijn met
    % gewicht 0. Ik veronderstel dat dit zich nooit voordoet.
    filterbest([Cost-state(Left, Right, [])|Q], OptStates),
    include(isGoal, OptStates, OptGoals), % dit is de "filter" van Haskell
    % geef 1 van de mogelijke resultaten terug.
    member(_-state(L,R,_), OptGoals).

insertPQ(Elems, Q, NewQ) :-
    append(Elems, Q, Q_),
    sort(1, @=<, Q_, NewQ).

isGoal(_-state(_,_,[])).

% haal de knopen uit de (gesorteerde) wachtrij die evenveel kosten als de eerste
filterbest([K-V | T], Res) :- filterbest([K-V|T], K, Res).
filterbest([K-V | T], K, [K-V|Res]) :- filterbest(T, K, Res).
filterbest([K-_ | _], X, []) :- K \= X.
filterbest([], _, []).
    
kleinste_mincut(X, Y) :-
    findall(NumEdges-Cost-cut(Left,Right), (
        mincut(Cost, cut(Left,Right)),
        edgesbetween(Left, Right, E),
        length(E, NumEdges)
    ), MinCuts),
    sort(1, @=<, MinCuts, Sorted),
    filterbest(Sorted, Best),
    % kies 1 oplossing
    member(_-X-Y, Best).