CFG算法中的局部搜索

Question

有没有算法可以在多项式时间内解决下面的问题：

我们正在连接位集中的位：

0只能连接到1
每个位只能连接一次
连接不能相交

给定位集的最大连接数是多少？

Answer 1

这里可以使用动态规划

状态是 (l, r) - 给定字符串的 [l, r] 子串。
状态的值是子串中匹配符号的最大数量。
基本情况很简单：对于所有短于 2 的子串，答案为 0。
对于所有较长的子串，我们可以做两件事：
- 不要将第一个符号与任何东西匹配。
- 将它匹配到某个东西上并独立解决两个较小的子问题（它们是独立的，因为不允许交集）。

就是这样。时间复杂度为 O(n^3)（每个状态有 O(n^2) 个状态和 O(n) 个转换）。这是一个伪代码（为了简洁省略了记忆）：

def calc(l, r)
    if l >= r
        return 0
    res = calc(l + 1, r)
    for k = l + 1 to r
        if match(s[l], s[k]) // match checks that two characters match
            res = max(res, 1 + calc(l + 1, k - 1) + calc(k + 1, r)) 
    return res

Answer 2

实际上，给定的 0 和 1 序列中的最大连接数是这两个值中的最小值 - 序列中 0 的数量和序列中 1 的数量。

不存在无法连接所有少数位的情况。所以这个问题可以在 O(n).

CFG算法中的局部搜索

Local search in CFG algorithm

algorithm

optimization

context-free-grammar