求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中最大布尔可满足性问题的算法

回答

相关问题