🎰需求排序算法设计
目录
背景
随着某些业务线日益膨胀的单个迭代需求数量，在一个统一的需求评审会上，通常会有许多人浪费大量的时间无效地参与对应的评审。比如：
假设每个需求的时间都是相等的单位长度：
- 我的等待时间是 5，而有效与会时间是 3，我的有效与会率是 $\frac{3}{8}$；
- 即使在 B 加入会议，G 离开会议，有效与会率也只有 $\frac{1}{2}$
- 与我相关的需求有三个且都不是连续的，频繁地加入离开会议并不是一个合适的设计；
有的业务线在意识到这个问题之后干脆把统一需求评审会取消了，按需求维度在指定时间内完成需求评审即可，但是我认为上述问题是可以通过一定的算法设计给出一个排序结果解决的。
优化目标
“背景”中抽象地描述了需求评审中遇到的各种问题，为了设计一个算法解决这个问题，我们需要把这个问题量化。 我用以下的公式表示本算法需要优化的目标：
- 与会时间和：$$T= \sum_{role \in R} (Leave(role) - Join(role))$$ PS: 其中 R 是所有需要参与会议的人员的集合，Leave/Join 分别表示某个人员离开和加入会议的时间。
我们假设：每个人都在它的第一个需求开始时加入会议，它的最后一个需求结束后离开会议。 那么对于：
- 有效与会时间：$$C = \sum_{role \in R} (\sum_{s \in Cocered(role)} time(s))$$
- 可以得到等待时间：$$W = T - C$$ 我们知道有效与会时间是一个确定的值，所以 T 最小等价于 W 最小；
举个例子🌰：
建模与预处理
建模
用无向图建模：
- 图的节点：每个需求视作图的一个节点；
- 节点的边：两个需求如果有共同参与的人员，则这两个节点之间存在一个边，边的权为共同参与的人员数量； 举个例子：
分治
上面这种方式建模会生成若干的连通图，可以证明：连通图之间的相互排序方式不影响最终的结果。因此我们只需要考虑连通图内部的排序方式即可。
比如在下面这个例子中：
最终排序结果 1->2->3->4 与 4->1->2->3 是完全等价的。
剪枝
注意到两类特别的人员：
- 有的人员需要参与所有的需求，考虑这类人员会减少连通图的数量，它们的等待时间总是为 0 的；
- 有的人员只需要参与一个需求，考虑这类人员会增加系统复杂度，它们的等待时间也总是为 0 的； 我们在构造连通图可以先去除这两类人员。
比如：
算法与实现
暴力算法
对于单个连通图的需求数量 n，需要考虑的人员数量为 m，朴素的暴力算法需要穷举所有情况，每次计算 T 需要 O(mn) 的时间，因此总的时间复杂度是 $$O(n! \times mn)$$
动态规划
设连通图中的 n 个需求构成一个集合 S。 状态：$dp(S_{ij})$
- 其中 $S_{ij}$ 是元素数量为 i 的 S 的子集，即 $$rank(S_{ij}) = i, S_{ij} \subseteq S$$；
- dp 本身表示进行状态转移 $S_{ij} \Rightarrow S$需要增加的最少等待时间（W）和。 状态转移方程：
- $$dp(S_{ij}) = min{dp(S_{ij} + {s}) + wait(S_{ij}, s) | s \in S - S_{ij}}$$
- 其中 wait 函数表示在已经选择了集合 ij 的情况下如果下一个需求是 s，增加的总等待时间数量。wait 函数的实现：
- 通过 $S_{ij}$我们可以计算出在进行决策时当前在会议中的所有与会人员 $M$，设 s 的所有关心人员为 $M_s$
- 那么 $$wait(S_{ij}, s) = time(s) * rank(M - M_s)$$ 那么原问题即求解：$dp(\emptyset)$
这个算法需要枚举 S 的所有子集，每次枚举过程中需要遍历剩余需求，所以它时间复杂度大约是 $$O(n \times 2^n)$$