问题定义
输入：
- 人的集合P = {P1,P2,...,Pn}，其中，P1<P2<...<Pn。
- 工作的集合J = {J1,J2,...,Jn}，J是偏序集合，也就是说，J中某些元素之间存在序关系。
- 矩阵[Cij]，Cij表示工作Jj分配给Pi的代价。
输出：
- 每个人都被分配到某一工作，不同人分配到不同工作，且满足以下条件：如果F(Pi) ≤ F(Pj)，那么Pi<Pj。其中，F:P→J,表示p被分配给工作j。
- 矩阵[Xij]，Xij = 1表示Jj分配给Pi，使得ΣXijCij最小。
分析以及生成解空间
定义1：J的拓扑序列<JK1,JK2,...JKn>。满足，如果 Ji≤Jj，那么Ji 排在Jj。
命题1：如果P1→Jk1,P2→Jk2,..,Pn→Jkn是一个可能 解, 当且仅当Jk1,Jk2,...,Jkn必是一个J的拓朴排序的序列。
证明1：显然，依据问题的定义可以直接证明得到。
拓扑排序树问题
输入：偏序集合J
输出：J的拓扑序列树，即用树表示所有的拓扑排序序列<JK1,JK2,...JKn>。满足，如果 Ji≤Jj，那么Ji 排在Jj。
输入: 偏序集合S, 树根root.
输出: 由S的所有拓朴排序序列构成的树.
生成树根root;
选择偏序集中没有前序元素的所有元素, 作为root的子节点;
For root的每个字节点v Do
S=S-{v};
把v作为根, 递归地处理S
拓扑序列树的例子
分支界限搜索方法
该问题变为对拓扑序列树的最大权值序列的搜索问题。
命题2，把代价矩阵某行(列)的各元素减去同一个 数, 不影响优化解的求解，同时，所有被减去元素的和 + 某一序列对于当前权值矩阵计算的和 = 该序列对于原权值矩阵计算的和，且将所有被减去元素的和定义为解的代价下界。
证明2，该序列仅仅在权值矩阵的每一行(列)选取一个元素，也必会选取一个元素，那么，把代价矩阵某行(列)的各元素减去同一个数，并不会影响对于该行(列)元素的选取。
技巧1，代价矩阵的每行(列)减去同一个数(该行或列的最小数), 使得每行和每列至少有一个零, 其余各元素非负。
技巧1的意义，可以降低权值的分布范围以及提高了序列权值的下界，便于搜索算法里权值计算以及剪支。
搜索算法可以定义为：
- 建立根节点，其权值为解代价下界：技巧1中所有被减去元素的和。
- 使用爬山法,，贪心求解出当前算法的某个代价较小的可行解，计算代价方法为：每产生一个节点,，其权值为加工后的代价矩阵对应元素 + 其父节点权值。
- 当发现某个可行解时，遍历所有的解，在这一过程中，不断较低界限以及根据界限删去不可能是优化解的部分(剪支)。
