遺傳屬性下的最大集合

我對S的子集有一個集合S和一個布爾值函數f。函數f具有「遺傳屬性」：如果f（A）爲真且B是A的子集，那麼f（B）是真的。遺傳屬性下的最大集合

有沒有一種算法可以找到S的最大子集，其中f的計算結果爲真？集合A在f（A）爲真的意義上是最大的，但如果B包含A並且大於A，那麼f（B）是假的。

2011-11-23 wye.bee

你知道f的表示嗎？這是功課嗎？ – Per

我被困在一個小型的研究項目上。 f如下給出：如果S是一組布爾變量，那麼f是限制於這些變量的CNF表達式的可解性。 –

相反的情況是否適用 - 也就是說，如果f（E）對於所有屬於A的子集的E都是真的，那麼f（A）必須爲真？或者可能存在一些A（B，C），其中f（B）和f（C）爲真，但f（A）爲假？ – Kevin

使用回溯。僞代碼：

def A(c,r,u): 
    # c - current set 
    # r - remaining elements 
    # u - unused, forbidden elements 
    if r == []: 
     for i in u: 
      if f(c + [i]): # Check if c is really maximal 
       return 
     print c 
    else: 
     x = r[0] 
     r' = r without first element 
     if f(c + [x]): 
      A(c + [x], r', u) 
     A(c, r', u + [x])

潤A（[]，[A_1，A_2，...，A_N]，[]）

這有指數的複雜性，你不能避免，例如，如果f（A）= A具有至多n/2個元素，則存在指數級的許多最大集合。你需要更多的關於f來獲得更好的算法。

來源

2011-11-23 18:19:52 sdcvvc

它的工作原理！謝謝。 –

遺傳屬性讓你可以很好地修剪搜索空間。創建元素的排序，如果沒有的話。然後，只創建具有排序元素的集合。

開始與一個元素集 - 找到那些滿足（1）

然後創建全2個元素集 - 爲每一個元素集，試圖從追加（1）較大所有集合...（2）重要事項：記住它們之間的關係：如果{s，b}在（2）中，記住{s，b} .tail（）集合{s}和{b}（s < b）作爲{b}並將{s，b}添加到集合{s} .offspring。

現在只需要增加一些元素。打電話（2）「老」，開始創建「新」。對於舊的每個s，嘗試追加s.tail.offspring中的每個t，形成一個更多元素的集合。如果滿足，將它添加到「新」，將它的.tail（設置爲t）並將其設置爲s.offspring。因此你可以得到所有令人滿意的3元素。（爲了優化你現在可以忘掉所有來自「舊」的尾巴，並讓gc擺脫上一代）重複從3元素中獲得4元素等。

最大集合是那些在成功並且也有空的.offspring。

來源

2011-11-23 18:21:19

評估f意味着測試CNF公式的可滿足性。我傾向於將搜索最大集合與SAT求解器集成在一起。

從DPLL底座開始，進行以下修改。

除了作爲真或假，一個變量可以是除去。當DPLL選擇一個變量分支時，該分支有三種方式。
單位傳播是相同的。
純字面消除現在不起作用。但是，我們可以在純變量（有用的真值或去除）上進行雙向分支而不是三向分支。
遞增檢查對於每個分配的變量，是否有一個子句只滿足該分配。如果不是，則修剪 - 此子樹不包含最大解決方案。
如果部分賦值滿足所有子句，則將刪除和未賦值的變量集合添加到輸出中。可能有重複。

來源

2011-11-23 19:10:01 Per

遺傳屬性下的最大集合

回答

相關問題