使用 Z3 求解器寻找冰冻湖上的路径（求解.冰冻.路径.湖上.寻找...）

本文将详细介绍如何使用 Z3 定理证明器在 Python 中解决冰冻湖寻路问题。我们将详细讲解如何将问题转化为 Z3 可以理解的约束条件，并提供完整的代码示例，帮助读者理解如何使用 Z3 找到从起点到终点的安全路径。本文重点在于如何正确建模问题，以及如何使用 Z3 的 API 来表达约束和求解。

给定一个由 1（安全）和 0（不安全）组成的矩阵，代表一个冰冻湖。目标是找到一条从起始位置到目标位置的安全路径，即路径上的所有单元格都必须是安全的（值为 1）。 只能在相邻的单元格之间移动（上、下、左、右）。

解决此问题的关键在于正确地将问题建模为 Z3 可以理解的约束。我们不应该为矩阵中的每个单元格创建符号变量，而是应该为路径本身创建变量。这允许我们直接约束路径的有效性。

首先，我们需要定义表示路径的变量。 由于我们不知道路径的长度，我们可以假设最坏的情况是路径包含矩阵中的所有单元格。 因此，我们可以为路径中的每个可能的位置创建整数变量，表示其行和列坐标。

from z3 import *

def find_path(matrix, start, end):
    # Define the dimensions of the matrix
    rows = len(matrix)
    cols = len(matrix[0])

    # symbolic look-up into the matrix:
    def lookup(x, y):
        val = 0
        for r in range(rows):
            for c in range(cols):
                val = If(And(x == r, y == c), matrix[r][c], val)
        return val

    # Create a path, there are at most rows*cols elements
    path = []
    for r in range(rows):
        for c in range(cols):
            path.append([FreshInt(), FreshInt()])

在这里，path 是一个列表，其中每个元素都是包含两个 FreshInt() 变量的列表，分别代表行和列的索引。 FreshInt() 创建一个新的整数变量，其名称与之前创建的任何变量不同。 lookup 函数用于查找矩阵中给定坐标的值。

接下来，我们需要添加约束来确保路径有效。 这包括以下内容：

• 路径的第一个元素必须是起始位置。
• 路径中的每个后续元素必须与前一个元素相邻。
• 路径中的每个元素必须是安全的（值为 1）。
• 路径必须最终到达目标位置。
• 路径中的所有位置都是唯一的。

    s = Solver()

    # assert that the very first element of the path is the start position:
    s.add(path[0][0] == start[0])
    s.add(path[0][1] == start[1])

    # for each remaining path-element, make sure either we reached the end, or it's a valid move
    prev = path[0]
    done = False
    for p in path[1:]:
        valid1 = And(p[0] >= 0, p[0] < rows, p[1] >= 0, p[1] < cols)  # Valid coords

        valid2 = Or( And(p[0] == prev[0]-1, p[1] == prev[1])     #    Go up
                   , And(p[0] == prev[0]+1, p[1] == prev[1])     # or Go down
                   , And(p[0] == prev[0],   p[1] == prev[1]+1)   # or Go right
                   , And(p[0] == prev[0],   p[1] == prev[1]-1))  # or Go left

        valid3 = lookup(p[0], p[1]) == 1 # The cell is safe

        # Either we're done, or all valid conditions must hold
        s.add(Or(done, And(valid1, valid2, valid3)))

        prev = p

        # We're done if p is the end position:
        done = Or(done, And(p[0] == end[0], p[1] == end[1]))

    # Make sure the path is unique:
    for i in range(len(path)):
        for j in range(len(path)):
            if j <= i:
                continue
            s.add(Or(path[i][0] != path[j][0], path[i][1] != path[j][1]))

代码解释：

• s = Solver() 创建一个 Z3 求解器实例。
• s.add(path[0][0] == start[0]) 和 s.add(path[0][1] == start[1]) 约束路径的第一个元素为起始位置。
• 循环遍历路径中的其余元素，并添加约束以确保每个元素都与前一个元素相邻，并且是安全的。
  • valid1 确保坐标有效。
  • valid2 确保移动是有效的（上、下、左、右）。
  • valid3 确保单元格是安全的。
  • s.add(Or(done, And(valid1, valid2, valid3))) 添加约束，要求要么已经到达终点，要么所有有效条件都成立。
  • done = Or(done, And(p[0] == end[0], p[1] == end[1])) 检查当前位置是否是终点。
• 最后的嵌套循环添加约束，确保路径中的所有位置都是唯一的。

最后，我们使用 Z3 求解器来查找满足所有约束的路径。 如果找到这样的路径，我们将从模型中提取它。

    # Compute the path:
    if s.check() == sat:
        model = s.model()
        walk = []
        for p in path:
            cur = [model[p[0]].as_long(), model[p[1]].as_long()]
            walk.append(cur)
            if (cur[0] == end[0] and cur[1] == end[1]):
                break
        return walk
    else:
        return None

代码解释：

• s.check() == sat 检查求解器是否找到满足所有约束的解。
• model = s.model() 获取模型，该模型包含变量的赋值。
• 循环遍历路径，并从模型中提取每个位置的坐标。
• 如果当前位置是终点，则停止提取路径。
• 返回提取的路径。

from z3 import *

def find_path(matrix, start, end):

    # Define the dimensions of the matrix
    rows = len(matrix)
    cols = len(matrix[0])

    # symbolic look-up into the matrix:
    def lookup(x, y):
        val = 0
        for r in range(rows):
            for c in range(cols):
                val = If(And(x == r, y == c), matrix[r][c], val)
        return val

    # Create a path, there are at most rows*cols elements
    path = []
    for r in range(rows):
        for c in range(cols):
            path.append([FreshInt(), FreshInt()])

    s = Solver()

    # assert that the very first element of the path is the start position:
    s.add(path[0][0] == start[0])
    s.add(path[0][1] == start[1])

    # for each remaining path-element, make sure either we reached the end, or it's a valid move
    prev = path[0]
    done = False
    for p in path[1:]:
        valid1 = And(p[0] >= 0, p[0] < rows, p[1] >= 0, p[1] < cols)  # Valid coords

        valid2 = Or( And(p[0] == prev[0]-1, p[1] == prev[1])     #    Go up
                   , And(p[0] == prev[0]+1, p[1] == prev[1])     # or Go down
                   , And(p[0] == prev[0],   p[1] == prev[1]+1)   # or Go right
                   , And(p[0] == prev[0],   p[1] == prev[1]-1))  # or Go left

        valid3 = lookup(p[0], p[1]) == 1 # The cell is safe

        # Either we're done, or all valid conditions must hold
        s.add(Or(done, And(valid1, valid2, valid3)))

        prev = p

        # We're done if p is the end position:
        done = Or(done, And(p[0] == end[0], p[1] == end[1]))

    # Make sure the path is unique:
    for i in range(len(path)):
        for j in range(len(path)):
            if j <= i:
                continue
            s.add(Or(path[i][0] != path[j][0], path[i][1] != path[j][1]))

    # Compute the path:
    if s.check() == sat:
        model = s.model()
        walk = []
        for p in path:
            cur = [model[p[0]].as_long(), model[p[1]].as_long()]
            walk.append(cur)
            if (cur[0] == end[0] and cur[1] == end[1]):
                break
        return walk
    else:
        return None

# Example usage
matrix = [[1, 1, 1, 0],
          [1, 0, 1, 0],
          [1, 0, 1, 0],
          [1, 0, 0, 0]]
start = (3, 0)
end = (2, 2)

path = find_path(matrix, start, end)
if path:
    print("Valid path found:")
    for cell in path:
        print(f"({chr(ord('A') + cell[0])}{cell[1] + 1})")
else:
    print("No valid path found.")

• 建模是关键： 使用 Z3 解决问题的关键在于正确地将问题建模为约束。 在这个问题中，为路径创建变量而不是为矩阵中的每个单元格创建变量，可以更有效地表达约束。
• 性能： Z3 的性能取决于问题的复杂性。 对于较大的矩阵，可能需要调整约束或使用更高级的技术来提高性能。
• 唯一性约束： 确保路径中的所有位置都是唯一的，这对于避免循环至关重要。

通过使用 Z3 定理证明器，我们可以有效地找到冰冻湖上的安全路径。 这种方法可以推广到其他寻路问题，只需根据特定问题的要求调整约束即可。

以上就是使用 Z3 求解器寻找冰冻湖上的路径的详细内容，更多请关注知识资源分享宝库其它相关文章！