dimanche 29 mars 2015

Algorithm for conditioned migration

I/ Algebraic modeling of the problem


Given E={e1..en}, n>=0, a set of positive integers (e for entity)


Given L={l1..lm}, m>=0, a set of positive integers (l for location)


Given P:E --> L , a function. (P for position)


Given C:L --> IN*, a function. (C for capacity)


Given U:L --> IN, a function. (U for used) defined by: U(l)=card({e/P(e)=l})


Given A:L --> IN, a function. (A for available) defined by: C(l)=A(l)+U(l) for any l in L.


Let D:E --> L^k, where 0 < k <= m, D(e)=(l1,l2,..li) a function (D for destinations)


(That is, each entity has an ordered non-empty list of locations (destinations) willing to move to).


Let I:E --> IR+, a bijection (I for Importance). (That is, each entity has a unique importance number I(e))


II/Rules of Migration:


The asked task, is to find out the new P' function (Positioning) that affords the following:


1- P'(e) belongs to {l'1,l'2,..,l'i} where (l'1,l'2,..,l'i)=D(e)


2- If we P'(e)=l's and P'(e)=l't are two possible solutions, where D(e) = (l'1,...,l's,...,l't,...,l'i), then we must keep the solution that matches the destinations' order (i.e l's in this case) and exclude the other one)


3-If A(l) = 1 and P(e1)=l and P(e2)=l are two possible solutions, where I(e1)>I(e2) then we must keep the solution that matches the importance's order (i.e in this case P(e1)=l) and exclude the other one.


4- If none of the desired destinations is possible, then P'(e)=P(e)


Which algorithmic problem would matches the one I've exposed?


Aucun commentaire:

Enregistrer un commentaire