python - 如何进一步优化“Lights Out”变体的求解器？

我仍在解决this problem，它取自当前的“ Google Foobar”挑战。它是“ Lights Out”游戏的一种变体，其中按下一个灯光将翻转同一行和同一列上每个灯光的状态。

我以前尝试过using a BFS，结果对于n> 6来说太慢了，而我需要处理2

我使用@Aryabhata概述的strategy来找到某些系统Ax = b的特殊解决方案x'，该解决方案可以与此问题的实例相关联（有关详细信息，请参见here）。
找到A的零位空间的base后，我计算x'的所有和以及基向量的线性组合。
这些和的集合是原始问题的所有解决方案的集合，因此我可以通过蛮力找到达到最小值的解决方案。
应该注意的是，即使对于n个，零空间也是空的（A是可逆的），因此x'达到了最小值，因为它是唯一的解决方案。如果n为奇数，则空空间基数中的向量数为2n-2，因此搜索空间的大小为2 ^（2n-2），在最坏的情况下（n = 15）为2 ^ 28。


这是我的程序：

from itertools import product


MEMO = {}


def bits(iterable):
    bit = 1
    res = 0
    for elem in iterable:
        if elem:
            res |= bit
        bit <<= 1
    return res


def mask(current, n):
    if (current, n) in MEMO:
        return MEMO[(current, n)]

    result = 0
    if current < n:
        for j in xrange(n):
            result += (2 ** ((current - 1)*n + j) + 2 ** (current*n + j))
    else:
        for i in xrange(n):
            result += (2 ** (i*n + current - n) + 2 ** (i*n + current - n + 1))

    MEMO[(current, n)] = result

    return result


# See: https://math.stackexchange.com/a/441697/4471
def check(matrix, n):
    parities = [sum(row) % 2 for row in matrix]
    for i in xrange(n):
        parities.append(sum([row[i] for row in matrix]) % 2)

    return len(set(parities)) == 1


def minimize(matrix, current, n):
    if current == 0:
        # See: https://stackoverflow.com/a/9831671/374865
        return bin(matrix).count("1")
    else:
        return min(minimize(matrix ^ mask(current, n), current - 1, n),
                   minimize(matrix, current - 1, n))


def solve(matrix, n):
    result = [0 for i in xrange(n) for j in xrange(n)]

    for i, j in product(xrange(n), repeat=2):
        if matrix[i][j]:
            for k in xrange(n):
                result[i*n + k] ^= 1
                result[k*n + j] ^= 1
            result[i*n + j] ^= 1

    if n % 2 == 0:
        return sum(result)
    else:
        return minimize(bits(result), 2*n - 2, n)


def answer(matrix):
    n = len(matrix)

    if n % 2 == 0:
        return solve(matrix, n)
    else:
        if check(matrix, n):
            return solve(matrix, n)
        else:
            return -1

我已经尝试过对其进行优化：例如，矩阵通过函数bits编码为二进制数，而函数mask创建用于将基数的单个元素添加到x'的二进制掩码。这些掩码也被记住，因为它们经常使用，因此它们仅被计算一次。

然后使用成语bin(n).count('1')来计数位数，该成语should be最快的实现方式（我将其与Kernighan的经典作法进行比较）。

那么，我还能采取什么措施来提高程序的性能呢？以下是一些测试案例：

print answer([
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]), 1

print answer([
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
]), 14

print answer([
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
]), 15

print answer([
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]), 14

print answer([
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]), 15

编辑：我通过了这一轮。此实现可以正确解决5个测试用例中的4个，然后我强行解决了第五个。我仍然对进一步的优化或其他算法感兴趣！

编辑2：This answer，尤其是this paper提供了一个证明这一特殊问题是NP-难的问题（第3节），这表明我们不应该寻求多项式算法。所以问题就变成了：“我们能得到的最佳指数是多少？”。

最佳答案

我尝试了关于线性代数的所有事情，由于它是GF2，所以我认为我找不到多项式解。由于最大数量为15，因此我进一步将其优化为大约2 ^ 15。

对于偶数

因此，对于n而言，还有比标准线性代数更快的方法。例如，如果您有这样的事情，
0000010000000000
一个解决方案应该是（将点的行和列恰好翻转n次）
0100111101000100
如果考虑一下，如果您有想要翻转的点，则可以翻转行和列的每个点一次。 （如果这很有意义），那么很容易找到一个特定的解决方案。

如果我有这样的事情
0100001000100000
一种解决方案可能是
1131122112210120
并且由于两次翻转没有区别，因此解决方案可以简化为
1111100110010100

然后是奇数

如果n是奇数，我只能搜索。但是，我们可以扩展n-> n + 1，以使问题的解决方案不应包含最后一行和最后一列的翻转点。

如果您有3x3之类的东西：
010001001
您可以随时尝试将解决方案扩展到类似以下内容：
010x001x001xxxxx
首先，您将确定3乘3的所有点，
11111001 + ?10010100
在哪应该解决
000x000x000xxxxx
如您所见，无论如何翻转，除非xxx是相同的位，否则您将无法满足。然后，您可以尝试翻转底部的所有组合，然后通过确定翻转是否导致行的最小数量为1，来确定是否进行右侧翻转。

我真的很无能为力，希望事情会很清楚。

关于python - 如何进一步优化“Lights Out”变体的求解器？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27436275/