回覆列表
  • 1 # 使用者2727756007908

    有理數解

    先換個問題的表達:

    對非齊次方程組: 是否有非負整數解,其中 是一個 整數非負矩陣, 是個 整數向量。

    我們知道,這個問題要有解,當且僅當 ,所以可以首先 跑個高斯消元判斷是否有解。

    若 ,那麼這個方程組有唯一解,可以透過高斯消元直接求出唯一解。

    若 ,那麼此方程有無數解,那麼可以搞出通解來:

    其中 是特解, 是基礎解系, 是任意常數。

    非負整數解

    為了方便表達,容我瞎幾把取個名字,下文中用LNE(Linear Nonhomogenous Equations)來表示原問題。

    斷言:LNE是NPC的。(沒有找到相關的論文,這個證明是我自己給出的,若是有大神知道相關文獻,還請指出)

    證明:

    我們嘗試將一個很基礎的NPC問題——SAT(SATISFIABILITY)問題,規約到LNE。

    說簡單點就是,我們要證明一個很難很難很難的問題SAT不比我們的LNE更難。

    我們首先給出SAT問題的一個例項(instance):

    給出一個集合 ,和 個 的子集,分別為 和 ,是否存在一個 整數規劃,使得:

    現在將這個例項等價轉換一下,增加變數,處理掉 :

    聰明的小夥伴可能已經注意到了,現在我們的整數規劃方程已經很接近LNE了。

    唯一的不同在於,LNE中,除了變數必須是非負數外,所有的關係都是相等。

    所以我們引入非負鬆弛變數來消除不等號(感謝 @史石石石的指正):

    這顯然就是一個LNE問題了。

    如果我們有個演算法 ,能解決LNE問題,那麼我們就能用演算法 解決上述例項,從而解決SAT問題。

    所以我們多項式時間內將SAT問題規約到了LNE問題。而由於SAT是NPC的,所以LNE也是NPC的。

    關於解法

    其實這個問題本身就是個整數規劃,所以很適合用整數規劃求解器來解決,CPLEX會是個不錯的選擇。

  • 中秋節和大豐收的關聯?
  • 漢堡包和肉夾饃相比,你更喜歡哪一種?為什麼?