algorithm - 遗传属性下的极大集

在s的子集上有一个集s和一个布尔值函数f。函数f具有“遗传性质”：如果f（a）为真，b是a的子集，则f（b）为真。
是否有一个算法发现S的最大子集，F在其中被评估为真？集合A在f（a）为真的意义上是最大的，但如果b包含a且大于a，则f（b）为false。

最佳答案

使用回溯伪码：

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做更多的假设。

关于algorithm - 遗传属性下的极大集，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8246773/