Geek Answers Handbook

Logical programming: how to distribute resources among consumers?

I have a task in which I must distribute unique resources among consumers. Rules:

  • each consumer has a set of types of resources that they can use,
  • each resource is unique
  • each consumer should receive n> 0 resources,
  • all resources must be distributed.

E. G. we have this list of consumers and their preferences:

  • A: {X, W}
  • B: {X, Y, V}
  • C: {X, Z}
  • D: {Z}

We have a list of resources: [X, W, Y, V, Z].

If we assign resources naively, iterating through the list of consumers and providing them with the first available resource from our set, we fail in D because only Z is already assigned C. The best solution is the following: A (W), B (Y, V) , C (X), D (Z).

! Prolog, , , , , .

, google, ?

+4
1

, . , . Prolog , :

distribution([], [], []).
distribution([C-Ps|CPs], Rs0, [C-As|CAs]) :-
        allocation(Ps, As, Rs0, Rs1),
        As = [_|_],
        distribution(CPs, Rs1, CAs).

allocation(_, [], Rs, Rs).
allocation(Ps0, [A|As], Rs0, Rs) :-
        select(A, Ps0, Ps1),
        select(A, Rs0, Rs1),
        allocation(Ps1, As, Rs1, Rs).

distribution/3 Consumer-Preferences, - . Consumer-Allocated resources. SWI-Prolog :

?- distribution([a-[x,w],b-[x,y,v],c-[x,z],d-[z]], [x,w,y,v,z], Ds).
Ds = [a-[w], b-[y, v], c-[x], d-[z]] ;
Ds = [a-[w], b-[v, y], c-[x], d-[z]] ;
false.

. : ( , , , allocation/4, - - , As ), , , () , false.

+4

More articles:


All Articles