→ firejox:DP 應該可以O(n*2^n)吧.... 05/24 21:02
※ 引述《tkcn (小安)》之銘言：
: 如果問題是要找出一組 one-to-one 對應，
: 可以把問題轉成 Maximum Bipartite Matching，
: 然後用 Hangerian Algorithms(匈牙利演算法) 去找出一組解。
: 這類問題如果只需要計算所有解的 "數量" 且數字不大時， (n<20)
: "也許" 還有機會用 DP 算出。複雜度大概 O( 2^n * ... )
: 至於要算到 20*33，我個人是認為沒有辦法。
提供一下DP解法。
Bipartite Matching 就是有兩堆東西，然後連連看：
http://163.27.162.1/98music/%E9%80%A3%E9%80%A3%E7%9C%8B.jpg
想要連連看，第一直覺，
當然就是第一個連第一個、第二個連第二個、....這樣囉。
接下來才會繼續考慮其他的連法。
事實上我們可以把下面的東西重新排列一下，
就可以一直保持一連一、二連二了。
所以方法就是：
窮舉下面東西的全部排列方式，
每一種排列方式都很容易就能計算出連連看的結果了。
用DP的話，可以 O(n^2 * 2^n) 解出來。
大致上就跟 Travelling Salesman Problem 的 DP 解法長得差不多。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.154.35
※ 編輯: DJWS 來自: 59.115.154.35 (05/24 17:06)