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