在 python 中使用 bfs 编码 8 个难题时出现哈希错误

Question

我用Python编写了一段代码，使用广度优先搜索算法解决8个难题，但在“if child.state not in Visited:”行中出现了哈希错误。

我用Python编写了一段代码，使用广度优先搜索算法解决8个难题，但在“if child.state not in Visited:”行中出现了哈希错误。

我用Python编写了一段代码，使用广度优先搜索算法解决8个难题，但在“if child.state not in Visited:”行中出现了哈希错误。

class Node:
    def __init__(self, state, parent):
        self.state = state
        self.parent = parent


def get_children(node):
    children = []

    for i in range(3):
        for j in range(3):
            if node.state[i][j] == 0:
                if (i >= 0) and (i != 2):           #move down
                    new_state = list(node.state)
                    new_state[i][j], new_state[i+1][j] = new_state[i+1][j], new_state[i][j]
                    children.append(Node(new_state, node))

                if (i <= 2) and (i != 0):           #move up
                    new_state = list(node.state)
                    new_state[i][j], new_state[i-1][j] = new_state[i-1][j], new_state[i][j]
                    children.append(Node(new_state, node))

                if j >= 0 and j != 2:           #move right
                    new_state = list(node.state)
                    new_state[i][j], new_state[i][j+1] = new_state[i][j+1], new_state[i][j]
                    children.append(Node(new_state, node))

                if j <=  2 and j != 0:           #move left
                    new_state = list(node.state)
                    new_state[i][j], new_state[i][j-1] = new_state[i][j-1], new_state[i][j]
                    children.append(Node(new_state, node))


    return tuple(children)



def bfs(initial_state, goal_state):
    queue = [Node(initial_state, None)]
    visited = set()

    while queue:
        node = queue.pop(0)
        if node.state == goal_state:
            return node

        for child in get_children(node):
            if child.state not in visited:
                queue.append(child)
                visited.add(child.state)

    return None


initial_state = [[1, 2, 3],
                [4, 5, 0],
                [7, 8, 6]]

goal_state = [[1, 2, 3],
              [4, 5, 6],
              [7, 8, 0]]

solution = bfs(initial_state, goal_state)

if solution is not None:
    print("Solution found")
    path = []
    node = solution
    while node is not None:
        path.append(node.state)
        node = node.parent


    path.reverse()
    for state in path:
        print(state)

else:
    print("No solution found")

输出：

Traceback (most recent call last):
  File "D:\algorithms\8_puzzle.py", line 63, in <module>
    solution = bfs(initial_state, goal_state)
  File "D:\algorithms\8_puzzle.py", line 48, in bfs
    if child.state not in visited:
TypeError: unhashable type: 'list'

Answer 1

我在您的代码中发现了两个问题： 第一个是不可散列类型：Python 列表是可变对象，并且不能被散列。一个简单的解决方法是将列表转换为元组。实际上，您还需要将子列表转换为元组。一个简单的函数可以做到这一点是

def to_tuple(x):
    return (tuple(row) for row in mat )

第二个问题（剧透警告，如果你想自己解决它，请停止阅读）是你正在传递你的列表，但你没有正确复制它。 您使用了

new_state = list(node.state)

，这会执行列表的浅表复制。浅复制意味着其中的列表只是通过引用复制。您想要进行深度复制（

from copy import deepcopy

），它还复制node.state

的子数组

完整解决方案

from copy import deepcopy

class Node:
    def __init__(self, state, parent):
        self.state = state
        self.parent = parent

def to_tuple(mat):
    return (tuple(row) for row in mat )

def get_children(node):
    children = []

    for i in range(3):
        for j in range(3):
            if node.state[i][j] == 0:
                if (i >= 0) and (i != 2):           #move down
                    new_state = deepcopy(node.state)
                    new_state[i][j], new_state[i+1][j] = new_state[i+1][j], new_state[i][j]
                    children.append(Node(new_state, node))

                if (i <= 2) and (i != 0):           #move up
                    new_state = deepcopy(node.state)
                    new_state[i][j], new_state[i-1][j] = new_state[i-1][j], new_state[i][j]
                    children.append(Node(new_state, node))

                if j >= 0 and j != 2:           #move right
                    new_state = deepcopy(node.state)
                    new_state[i][j], new_state[i][j+1] = new_state[i][j+1], new_state[i][j]
                    children.append(Node(new_state, node))

                if j <=  2 and j != 0:           #move left
                    new_state = deepcopy(node.state)
                    new_state[i][j], new_state[i][j-1] = new_state[i][j-1], new_state[i][j]
                    children.append(Node(new_state, node))


    return tuple(children)



def bfs(initial_state, goal_state):
    queue = [Node(initial_state, None)]
    visited = set()

    while queue:
        node = queue.pop(0)
        
        if node.state == goal_state:
            return node

        for child in get_children(node):
            if to_tuple(child.state) not in visited:
                queue.append(child)
                visited.add(to_tuple(child.state))

    return None


initial_state = [[1, 2, 3],
                [4, 5, 0],
                [7, 8, 6]]

goal_state = [[1, 2, 3],
            [4, 5, 6],
            [7, 8, 0]]

solution = bfs(initial_state, goal_state)

if solution is not None:
    print("Solution found")
    path = []
    node = solution
    while node is not None:
        path.append(node.state)
        node = node.parent


    path.reverse()
    for state in path:
        print(state)

else:
    print("No solution found")