求python中最大布爾可滿足性問題的算法

我在使用python求解最大布爾可滿足性問題的算法時遇到了一些麻煩。我應該實現一個求解函數，它使用一個參數f（對應於公式的python函數），它返回一個滿足f且具有最大可能數目的True值的值列表。我得到了下面的輔助函數：求python中最大布爾可滿足性問題的算法

def count(values): 
    return len([v for v in values if v == True])

可以以這種方式使用：

count([True, False, True, False]) 
    2

這是確切的問題給出：

實現遞歸函數解決（F ），它將第一個參數作爲單個函數f（即對應於公式的Python函數）。函數f可以採用任何非零數量的參數。函數solve（f）應該返回一個滿足f且具有最大可能數量的True值的值列表（與滿足f的任何其他值列表一樣多）。

這是我到目前爲止有：

def solve(f, values = []): 
    if (len(values) == len(variables(f))): 
     if(f(*values) == True): 
      return values

這基本上是基本情況。但現在我完全卡住了。

如果有人能爲我完成這件事，並解釋他們做了什麼，我會永遠感激！

非常感謝！

編輯1： 這裏的函數變量（F）

def variables(f): 
    return list(f.__code__.co_varnames)

來源

2014-01-29 Aleksander

小撇：'[True，False，True，False] .count（True）'也返回2，內置於:) – mhlester

什麼是變量（f）？ f總是返回一個布爾值嗎？我不明白這個問題。 – RemcoGerlich

什麼是函數f的域和共域？如果域是無限的，那麼解的數量也可能是無限的。什麼時候「滿意」？ – Hyperboreus

我不知道這是不是以任何方式最佳，但在這裏，測試所有可能的輸入一個簡單的遞歸解決方案：

def solve(f, values=[]): 
    if len(variables(f)) == len(values): 
     if f(*values): 
      return values 
     else: 
      return None 

    true_results = solve(f, values+[True]) 
    false_results = solve(f, values+[False]) 
    if false_result is None: 
     return true_result 
    if true_result is None or count(false_result) > count(true_result): 
     return false_result 
    return true_result

來源

2014-01-29 22:17:41 Blckknght

求python中最大布爾可滿足性問題的算法

回答

相關問題