条件迁移算法

Question

问题的文字描述:

给定若干所学校，每所学校根据其需要拥有一定数量的教师。在学年结束时，一些教师要求根据有序列表更改他们的职位(他们目前正在任教的学校)(即:将我更改为 school1，如果不可能，则为 school2，如果不可能，则为 school3，等等。 .) 请记住，每所学校都必须拥有其所需的确切教师人数(不多也不少)。

每个老师都有一个唯一的重要性编号，因此如果两个或更多老师同时申请同一所学校，则重要性编号较高的老师将获得所需的学校。

如果我们无法按照他的名单迁移一名或多名教师，那么我们会让他留在他最初的学校回答:“对不起，你今年的需求是负担得起的”

我们如何负担得起这种“迁移”？

(p.s:我所说的“负担得起”是指将每个老师的职位更改为最好的(根据他的名单最好的)期望的学校。

---

I/问题的代数建模

给定E={e1..en}，n>=0，一组正整数(e代表实体)

给定L={l1..lm}，m>=0，一组正整数(l代表位置)

给定 P:E --> L ，一个函数。 (P代表职位)

给定 C:L --> IN*，一个函数。 (C为容量)

给定 U:L --> IN，一个函数。 (U 表示已用)定义为:U(l)=card({e/P(e)=l})

给定 A:L --> IN，一个函数。 (A 表示可用)定义为:对于 L 中的任何 l，C(l)=A(l)+U(l)。

让 D:E --> L^k，其中 0 < k <= m，D(e)=(l1,l2,..li) 一个函数(D 代表目的地)

(也就是说，每个实体都有一个有序的非空位置列表(目的地)愿意移动到)。

令 I:E --> IR+，双射(I 代表重要性)。 (即每个实体都有一个唯一的重要性编号I(e))

II/迁移规则:

要求的任务是找出提供以下内容的新 P' 函数(定位):

1- P'(e) 属于 {l1,l2,..,li} 其中 (l1,l2,..,li)=D(e)

2- 如果我们 P'(e)=ls 和 P'(e)=lt 是两个可能的解决方案，其中 D(e) = (l1,...,ls,...,lt,.. .,li)，那么我们必须保留与目的地顺序匹配的解决方案(即本例中的 ls)并排除另一个)

3-如果 A(l) = 1 和 P'(e1)=l 和 P'(e2)=l 是两个可能的解决方案，其中 I(e1)>I(e2) 那么我们必须保持解决方案匹配重要性的顺序(即在本例中为 P'(e1)=l)并排除另一个。

4- 如果没有一个可能的目的地，则 P'(e)=P(e)

Answer 1

这可以表述为二分匹配(或者，为了效率，整数最大流以避免重复相同的位置)。制作一个图表，每个老师都有一个节点，每个位置都有一个节点。在教师和他们当前的任务之间，以及所有高于他们当前任务的事情之间划上界限。找到最大匹配；如果它不完美，那么如果不让老师反对他们的偏好列表，这个问题就无法解决。

否则，对于每位教师，按重要性从高到低的顺序，确定可行的最佳分配并致力于此。有一种线性时间算法，给定一个具有完美匹配的二分图，确定是否存在另一个包含特定边的匹配(定位匹配边，以另一种方式定位非匹配边，并寻找增广路径) .