算法设计与分析.07.网络流 (4)

Posted on Edited on In Views:
最小代价匹配（概念及算法，应用）

网络流 (4)

  • Network Flow

最小代价匹配

  • 输入：带权的完全二部图 \(G=(X\cup Y,E)\)，\(\vert{X}\vert=\vert{Y}\vert\)
  • 输出：最小权重的完美匹配

实例问题

研讨会

  • \(m\) 个研讨会，\(n=12m\) 个学生，每个研讨会需要 12 个学生参加
  • 每个学生给出一个他最喜欢的研讨会列表（8 个）
  • 建模
    • \(X\)：研讨会（每个研讨会复制 12 份）
    • \(Y\)：学生
    • \(E\)：\(X\to Y\) 所有边，权重设置如下

定位

  • 通过两个传感器定位场景中 \(n\) 个物体的位置
    • 传感器返回一个方向
  • 建模
    • \(X_i\)：传感器 1 对物体 \(i\) 的定位方向
    • \(Y_i\)：传感器 2 对物体 \(i\) 的定位方向
    • \(E_{i,j}\)：传感器 1 和物体 \(i\) 的连线、传感器 2 和物体 \(j\) 的连线的距离
      • 由于测量误差，\(w(e_{i,j})>0\)

肾脏交换

  • 情况
    • \(x_i\) 的朋友 \(y_i\) 愿意捐献给 \(x_i\)，但是配型很差
    • \(x_j\) 的朋友 \(y_j\) 愿意捐献给 \(x_j\)，但是配型很差
    • \(x_i-y_j,x_j-y_i\) 配型好
  • 边权设置：配型越好越小，配型越差越大

二部图匹配

  • \(w(e)=1,\forall e\in E\)
  • 规约为最大流
  • 0-1 流

  • 残差图 \(G_M\) 如下

  • 增流路径
    • 起始边：\(s\to x\)，\(x\in X\) 是非匹配点
    • 中间边：匹配边和非匹配边的交错路径
    • 终止边：\(y\to t\)，\(y\in Y\) 是非匹配点

交错路径

  • 上面的增流路径的中间边
  • 匹配边和非匹配边的交错路径
  • 如果匹配 \(M\) 存在交错路径 \(P\)，则 \(M'=M\oplus P\) 也是一个匹配，而且 \(\vert{M'}\vert=\vert{M}\vert+1\)

  • 代价（cost）：\(P\) 上关于匹配 \(M\) 的非匹配边权重之和 - 匹配边权重之和
    • to match - to unmatch
  • 最短交错路径：cost 最小的交错路径

successive shortest path algorithm

  • 解决最小代价匹配问题
  • 算法：从空匹配开始，反复寻找最短交错路径，直到找不到
  • 如何找到最短交错路径？
    • \(s\to t\) 的最短路
  • 找最短路时，边的方向如下（和 \(G_M\) 的定义一致）
    • 匹配边：\(X\to Y\)
    • 非匹配边：\(Y\to X\)
  • 最短路是交错路径
    • \(s\) 的下一个点一定是 \(X\) 中未匹配的点
    • 路径中的点 \(y\in Y\) 的下一个点 \(y'\) 一定是 \(X\) 中的匹配点或者 \(t\)
      • 否则 \(G_M\) 中不存在边 \(y'\to y\)，同样转换图中也不存在
    • 路径中的点 \(x\in X\) 的下一个点 \(x\) 一定是 \(Y\) 中的匹配点
      • 转换图中匹配边权值为 0（后面证明）
  • Dijkstra 算法
    • 负权边如何处理？
    • 如果没有负权环，使用 Bellman-Ford 算法
    • 进行转换，把负权边转化为非负权边

等价转换

  • 对于 \(\forall x\in X\)，将它的所有出边都加上/减去 \(p(x)\) 最小代价匹配对应的边不变
  • 对于 \(\forall y\in Y\)，将它的所有入边都加上/减去 \(p(y)\) 最小代价匹配对应的边不变
  • 证明：对于完美匹配 \(M\) 和任意 \(x\in X,y\in Y\)，肯定会使用到 \(x\) 中一条出边，\(y\) 的一条入边

转换后的代价函数

  • reduced cost：\(c^{p}(x,y)\)
    • 从 \(X\) 到 \(Y\)

\[ c^{p}(x,y)=p(x)+c(x,y)-p(y) \]

  • Compatible prices：相容赋值
    • \(p(x),p(y)\) 满足如下条件

\[ \begin{array}{cc} c^p(x,y)\ge 0,&\text{for all }(x,y)\notin M\\ c^p(x,y)= 0,&\text{for all }(x,y)\in M\\ \end{array} \]

  • 如果代价函数是相容赋值，而且 \(M\) 是完美匹配，那么 \(M\) 是最小代价匹配
    • 证明：\(cost(M)=0\)

算法

引理1

  • \(p\) 是相容赋值，\(d\) 是 \(G_M\) 关于 \(c^p\) 的最短路，那么 \(d\) 上的边都满足 \(c^{p+d}(x,y)=0\)
  • 证明
  • 对于 \((x,y)\in d\) 都有 \(d(x)+c^{p}(x,y)-d(y)=0\)
  • \((x,y)\in M\)
    • 于是有 \((y,x)\in d\)
    • 于是有 \(d(x)=d(y)-c^{p}(x,y)\)
  • \((x,y)\notin M\)
    • 于是有 \((x,y)\in d\)
    • 于是有 \(d(y)=d(x)+c^{p}(x,y)\)
  • 根据定义

\[ c^{p}(x,y)=p(x)+c(x,y)-p(y) \]

  • 于是有

\[ \begin{aligned} c^{p+d}(x,y) &=\Big(p(x)+d(x)\Big)+c(x,y)-\Big(p(y)+d(y)\Big)\\ &=p(x)+c(x,y)-p(y)-c^{p}(x,y)\\ &=0\\ \end{aligned} \]

  • 证毕
  • 这里匹配边赋值为 0，保证了在下一步找最短路时，可以将匹配边定义为反向
    • \(G_M\) 的合理性（即这里说明了为什么定义 \(c^{p}(x,y)\) 的时候说 \(X\to Y\)，但是在找最短路的时候匹配边是 \(Y\to X\) 的）

引理2

  • \(p\) 是相容赋值，\(d\) 是 \(G_M\) 关于 \(c^p\) 的最短路，那么 \(p'=p+d\) 也是相容赋值
  • 证明：分类
  • \((x,y)\in M\)
    • \((y,x)\) 是图 \(G_M\) 中唯一的一条 \(x\) 的入边
      • 对于未匹配边，流量为 0，在残差图中没有反向边
    • 因此 \((x,y)\in M\)
    • 根据引理 1，\(c^{p+d}(x,y)=0\)
  • \((x,y)\notin M\)
    • 对于未匹配边，流量为 0，在残差图中有正向边（而且是 \(X\to Y\) 的边）
    • 距离三角不等式：\(d(y)\le d(x)+c^{p}(x,y)\)

\[ \begin{aligned} c^{p+d}(x,y) &=\Big(p(x)+d(x)\Big)+c(x,y)-\Big(p(y)+d(y)\Big)\\ &=\Big(p(x)+c(x,y)-p(y)\Big)+\Big(d(x)+d(y)\Big)\\ &=c^{p}(x,y)+\Big(d(x)-d(y)\Big)\\ &\ge0\\ \end{aligned} \]

引理3

  • \(p\) 是 \(M\) 的相容赋值，\(M'\) 是 \(M\) 按照最短路 \(d\) 增流之后的匹配，则 \(p'=p+d\) 是 \(M'\) 的相容赋值
  • 证明
  • 引理2 \(\Rightarrow\) \(p'\) 是 \(M\) 的相容赋值
  • 相较于 \(M\) 而言，\(M'\) 只是把 \(d\) 上的边进行反向了
  • 由引理1，\(d\) 上的边满足 \(c^{p+d}(x,y)=0\)
    • \(c^{p+d}(x,y)\) 和方向性无关，都是从 \(X\to Y\)
  • 证毕

算法正确性

  • 初始 \(p\) 相容，根据引理 2、3，算法一直都是相容的，在找到完美匹配的时候，\(w(M)=0\)，是最小权值匹配

算法复杂度

  • \(O(n^3)\)
  • \(n\) 次迭代（找最短路）
  • Dijkstra 算法：\(O(n^2)\)
    • \(m=n^2/4\)

发展

Input-queued switching

  • 数据包要从 \(x_i\to y_j\)
  • 一个时间片内，一个 \(x_i\) 只能发送一个包，一个 \(y_i\) 只能接收一个包
  • 如果两个数据包，起点终点都不冲突，可以一起发送

FIFO

  • 问题：Head-of-line blocking (HOL)
    • 这个时刻本来可以发送：\((x_1\to y_1,x_2\to y_2,x_3\to y_3)\)
    • 但是由于 FIFO，最多只能发送两个包

  • uniform i.i.d.：58% throughput

VOQ

  • Virtual output queueing

  • 每一个输入维护关于每一个输出的队列
  • 找最大匹配
  • uniform i.i.d.：100% throughput
  • 问题：starve input-queues when arrivals are nonuniform

最小带权匹配

  • LQF：\(c(x_i,y_j)\) 表示 \(x_i\) 传到 \(y_j\) 的包数量
  • OCF：\(c(x_i,y_j)\) 表示 VOQ 算法中距离上一次传送 \(x_i\) 到 \(y_j\) 包的时间
  • independent (even if not uniform)：100% throughput
  • 问题
    • 硬件难以实现
    • 匹配过慢
  • 意义
    • 提供了理论框架