填寫問券˙抽7-11禮券6檔好股票放一年賺5成攝影界美人正妹指定相機款買太多也不行!7500...
2011-11-11 06:38:43 人氣(382) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[結論] 最少路徑覆蓋問題

0
收藏
0
推薦

問題描述 :
用盡量少的不相交簡單路徑覆蓋有向無環圖G的所有節點。

額外補充 :
有���無環圖(Directed acyclic graph)簡稱 DAG

解決 :
解決此類問題可以建立一個二分圖模型。
把所有頂點 i 拆成兩個:X節點集中的 i 和 Y 節點集中的 i' ,
如果有邊 i->j ,則在二分圖中引入邊 i->j',
設二分圖最大匹配
為m, 則結果就是n-m。

廢話 : 一開始需要 n 條路徑, 每增加一個匹配, 就相對減少 1 條路徑

實作後的心得 : 用最大流做最大匹配, 效率有些慢, 不及匈牙利演算法

台長:Morris
人氣(382) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 亂糟糟筆記 |
此分類下一篇:[C/C++] 模擬鍵盤按鍵 自動回應
此分類上一篇:[WP7主題模擬] Rainmeter

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文