为什么 Z3 的微小搜索速度很慢 space？

Question

我正在尝试制作一个 Z3 程序（在 Python 中），它生成执行某些任务（例如，添加两个 n 位数字）的布尔电路，但性能非常糟糕，以至于无法正常工作-force 搜索整个解决方案 space 会更快。这是我第一次使用 Z3，所以我可能会做一些影响我性能的事情，但我的代码看起来不错。

以下是从我的代码中复制过来的here:

from z3 import *

BITLEN = 1 # Number of bits in input
STEPS = 1 # How many steps to take (e.g. time)
WIDTH = 2 # How many operations/values can be stored in parallel, has to be at least BITLEN * #inputs

# Input variables
x = BitVec('x', BITLEN)
y = BitVec('y', BITLEN)

# Define operations used
op_list = [BitVecRef.__and__, BitVecRef.__or__, BitVecRef.__xor__, BitVecRef.__xor__]
unary_op_list = [BitVecRef.__invert__]
for uop in unary_op_list:
    op_list.append(lambda x, y : uop(x))

# Chooses a function to use by setting all others to 0
def chooseFunc(i, x, y):
    res = 0
    for ind, op in enumerate(op_list):
        res = res + (ind == i) * op(x, y)
    return res

s = Solver()
steps = []

# First step is just the bits of the input padded with constants
firststep = Array("firststep", IntSort(), BitVecSort(1))
for i in range(BITLEN):
    firststep = Store(firststep, i * 2, Extract(i, i, x))
    firststep = Store(firststep, i * 2 + 1, Extract(i, i, y))
for i in range(BITLEN * 2, WIDTH):
    firststep = Store(firststep, i, BitVec("const_0_%d" % i, 1))
steps.append(firststep)

# Generate remaining steps
for i in range(1, STEPS + 1):
    this_step = Array("step_%d" % i, IntSort(), BitVecSort(1))
    last_step = steps[-1]

    for j in range(WIDTH):
        func_ind = Int("func_%d_%d" % (i,j))
        s.add(func_ind >= 0, func_ind < len(op_list))

        x_ind = Int("x_%d_%d" % (i,j))
        s.add(x_ind >= 0, x_ind < WIDTH)

        y_ind = Int("y_%d_%d" % (i,j))
        s.add(y_ind >= 0, y_ind < WIDTH)

        node = chooseFunc(func_ind, Select(last_step, x_ind), Select(last_step, y_ind))
        this_step = Store(this_step, j, node)

    steps.append(this_step)

# Set the result to the first BITLEN bits of the last step
if BITLEN == 1:
    result = Select(steps[-1], 0)
else:
    result = Concat(*[Select(steps[-1], i) for i in range(BITLEN)])

# Set goal
goal = x | y
s.add(ForAll([x, y], goal == result))

print(s)
print(s.check())
print(s.model())

代码基本上将输入布置为单独的位，然后在每个 "step" 5 个布尔函数中的一个可以对上一步的值进行操作，其中最后一步代表最终结果。

在这个例子中，我生成了一个电路来计算两个 1 位输入的布尔 OR，电路中有一个 OR 函数，所以解决方案很简单。

我有一个解 space 只有 5*5*2*2*2*2=400:

5个可能的功能（两个功能节点）
每个函数有 2 个输入，每个都有两个可能的值

此代码需要几秒钟才能运行并提供正确答案，但我觉得它应该立即运行因为只有 400 种可能的解决方案，其中有相当一部分是有效的.如果我将输入增加到两位长，解决方案 space 的大小为 (5^4)*(4^8)=40,960,000 并且永远不会在我的计算机上完成，尽管我觉得这应该很容易做到与 Z3.

我也有效地尝试了相同的代码，但使用我在 chooseFunc() 中使用的相同技巧将 Arrays/Store/Select 替换为 Python 列表和 "selected" 变量。代码是 here 并且它运行与原始代码的执行时间大致相同，因此没有加速。

我是否在做一些会大大降低求解器速度的事情？谢谢！

Answer 1

您的 op_list 中有重复的 __xor__；但这并不是真正的主要问题。随着位大小的增加，速度变慢是不可避免的，但乍一看，您可以（并且应该）避免在此处将整数推理与布尔值混合使用。我会将您的 chooseFunc 编码如下：

def chooseFunc(i, x, y):
    res = False;
    for ind, op in enumerate(op_list):
        res = If(ind == i, op (x, y), res)
    return res

看看这是否以任何有意义的方式提高了运行倍。如果没有，接下来要做的就是尽可能地摆脱数组。

为什么 Z3 的微小搜索速度很慢 space？

Why is Z3 slow for tiny search space?

python

boolean-logic

z3

z3py