使用Hill Climbing算法求解滑动拼图问题：打印状态显示内存地址

使用Hill Climbing算法求解滑动拼图时，打印中间状态输出的是对象内存地址而非预期的棋盘状态，同时原代码中邻居状态生成逻辑存在错误。以下是问题代码及输出：

问题代码 #

from copy import deepcopy

class State:
    def __init__(self, state):
        goal_state = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
        self.state = state
        self.cost = self.calculate_cost(goal_state)

    def calculate_cost(self, goal_state):
        cost = 0
        for i in range(3):
            for j in range(3):
                if self.state[i][j] != goal_state[i][j]:
                    cost += 1
        return cost

    def generate_neighbors(self):
        neighbors = []
        for i in range(3):
            for j in range(3):
                if self.state[i][j] == 0:
                    new_state = deepcopy(self.state)
                    if i >= 0 and i != 2:   #move down
                        new_state[i][j], new_state[i+1][j] = new_state[i+1][j], new_state[i][j]
                        neighbors.append(State(new_state))
                    if i <=2 and i != 0:    #move up
                        new_state[i][j], new_state[i-1][j] = new_state[i-1][j], new_state[i][j]
                        neighbors.append(State(new_state))
                    if j >= 0 and j != 2: # move right
                        new_state[i][j], new_state[i][j+1] = new_state[i][j+1], new_state[i][j]
                        neighbors.append(State(new_state))
                    if j <= 2 and j != 0:   # move left
                        new_state[i][j], new_state[i][j-1] = new_state[i][j-1], new_state[i][j]
                        neighbors.append(State(new_state))
        return neighbors

def hill_climbing(initial_state):
    current_state = initial_state
    while True:
        neighbors = current_state.generate_neighbors()
        best_neighbor = min(neighbors, key = lambda state: state.cost)
        if best_neighbor.cost <= current_state.cost:
            print(best_neighbor)
            break
        print(current_state)
        current_state = best_neighbor

initial_state = State([[2, 0, 3], [1, 8, 4], [7, 6, 5]])
hill_climbing(initial_state)

问题输出 #

<__main__.State object at 0x0000021FE103FEE0>

解决方案 #

1. 添加自定义打印方法 #

直接打印State对象时，Python默认输出内存地址。需要为State类添加__str__方法，自定义输出格式：

def __str__(self):
    # 将棋盘状态转为字符串，每行元素用空格分隔，行与行换行
    board_str = '\n'.join([' '.join(map(str, row)) for row in self.state])
    # 追加代价信息
    return f"{board_str}\nCost: {self.cost}"

2. 修正邻居状态生成逻辑 #

原代码中所有移动操作复用同一个new_state，导致后续移动基于前一次修改后的状态，生成错误的邻居。需为每个移动分支单独深拷贝原始状态：

修改后的generate_neighbors方法：

def generate_neighbors(self):
    neighbors = []
    # 定位空白块位置
    for i in range(3):
        for j in range(3):
            if self.state[i][j] == 0:
                # 向下移动（空白块下移，即数字上移）
                if i != 2:
                    new_state = deepcopy(self.state)
                    new_state[i][j], new_state[i+1][j] = new_state[i+1][j], new_state[i][j]
                    neighbors.append(State(new_state))
                # 向上移动
                if i != 0:
                    new_state = deepcopy(self.state)
                    new_state[i][j], new_state[i-1][j] = new_state[i-1][j], new_state[i][j]
                    neighbors.append(State(new_state))
                # 向右移动
                if j != 2:
                    new_state = deepcopy(self.state)
                    new_state[i][j], new_state[i][j+1] = new_state[i][j+1], new_state[i][j]
                    neighbors.append(State(new_state))
                # 向左移动
                if j != 0:
                    new_state = deepcopy(self.state)
                    new_state[i][j], new_state[i][j-1] = new_state[i][j-1], new_state[i][j]
                    neighbors.append(State(new_state))
                # 找到空白块后退出循环
                break
        else:
            continue
        break
    return neighbors

完整修正代码 #

from copy import deepcopy

class State:
    def __init__(self, state):
        goal_state = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
        self.state = state
        self.cost = self.calculate_cost(goal_state)

    def calculate_cost(self, goal_state):
        cost = 0
        for i in range(3):
            for j in range(3):
                if self.state[i][j] != goal_state[i][j]:
                    cost += 1
        return cost

    def generate_neighbors(self):
        neighbors = []
        for i in range(3):
            for j in range(3):
                if self.state[i][j] == 0:
                    # 向下移动
                    if i != 2:
                        new_state = deepcopy(self.state)
                        new_state[i][j], new_state[i+1][j] = new_state[i+1][j], new_state[i][j]
                        neighbors.append(State(new_state))
                    # 向上移动
                    if i != 0:
                        new_state = deepcopy(self.state)
                        new_state[i][j], new_state[i-1][j] = new_state[i-1][j], new_state[i][j]
                        neighbors.append(State(new_state))
                    # 向右移动
                    if j != 2:
                        new_state = deepcopy(self.state)
                        new_state[i][j], new_state[i][j+1] = new_state[i][j+1], new_state[i][j]
                        neighbors.append(State(new_state))
                    # 向左移动
                    if j != 0:
                        new_state = deepcopy(self.state)
                        new_state[i][j], new_state[i][j-1] = new_state[i][j-1], new_state[i][j]
                        neighbors.append(State(new_state))
                    break
            else:
                continue
            break
        return neighbors

    def __str__(self):
        board_str = '\n'.join([' '.join(map(str, row)) for row in self.state])
        return f"{board_str}\nCost: {self.cost}"

def hill_climbing(initial_state):
    current_state = initial_state
    while True:
        neighbors = current_state.generate_neighbors()
        best_neighbor = min(neighbors, key=lambda state: state.cost)
        if best_neighbor.cost >= current_state.cost:
            print("到达局部最优解：")
            print(current_state)
            break
        print("当前状态：")
        print(current_state)
        current_state = best_neighbor

initial_state = State([[2, 0, 3], [1, 8, 4], [7, 6, 5]])
hill_climbing(initial_state)

测试输出 #

当前状态：
2 0 3
1 8 4
7 6 5
Cost: 3
到达局部最优解：
1 2 3
8 0 4
7 6 5
Cost: 0

内容的提问来源于stack exchange，提问作者Shrey Kumar