2011-11-11 06:38:43Morris
[結論] 最少路徑覆蓋問題
問題描述 :
用盡量少的不相交簡單路徑覆蓋有向無環圖G的所有節點。
額外補充 :
有向無環圖(Directed acyclic graph)簡稱 DAG
解決 :
解決此類問題可以建立一個二分圖模型。
把所有頂點 i 拆成兩個：X節點集中的 i 和 Y 節點集中的 i' ,
如果有邊 i->j ，則在二分圖中引入邊 i->j'，
設二分圖最大匹配為m, 則結果就是n-m。
廢話 : 一開始需要 n 條路徑, 每增加一個匹配, 就相對減少 1 條路徑
實作後的心得 : 用最大流做最大匹配, 效率有些慢, 不及匈牙利演算法
用盡量少的不相交簡單路徑覆蓋有向無環圖G的所有節點。
額外補充 :
有向無環圖(Directed acyclic graph)簡稱 DAG
解決 :
解決此類問題可以建立一個二分圖模型。
把所有頂點 i 拆成兩個：X節點集中的 i 和 Y 節點集中的 i' ,
如果有邊 i->j ，則在二分圖中引入邊 i->j'，
設二分圖最大匹配為m, 則結果就是n-m。
廢話 : 一開始需要 n 條路徑, 每增加一個匹配, 就相對減少 1 條路徑
實作後的心得 : 用最大流做最大匹配, 效率有些慢, 不及匈牙利演算法