用A*算法求解八数码问题

实现两种启发函数

采取两种策略实现启发函数：

• 策略1：不在目标位置的数字个数
• 策略2：曼哈顿距离（将数字直接移动到对应位置的步数总数）

# 策略1: 不在目标位置的数字个数，即 state 与 goal_state 不相同的数字个数
def h1(state, goal_state):'''state, goal_state - 3x3 list'''distance = 0for i in range(3):for j in range(3):if state[i][j] != goal_state[i][j] and state[i][j] != 0:distance += 1return distance# 功能性函数，用于查找给定数字 num 在 goal_state 中的坐标
def find_num(num, goal_state):for i in range(3):for j in range(3):if goal_state[i][j] == num:return i, jreturn -1, -1# 策略2: 曼哈顿距离之和
def h2(state, goal_state):'''state, goal_state - 3x3 list'''distance = 0for i in range(3):for j in range(3):if state[i][j] == 0:continueif state[i][j] == goal_state[i][j]:continuegoal_i, goal_j = find_num(state[i][j], goal_state)distance += abs(i - goal_i) + abs(j - goal_j)return distance# 测试
start_state = [[2, 8, 3],[1, 6, 4],[7, 0, 5]
]goal_state = [[1, 2, 3],[8, 0, 4],[7, 6, 5]
]# 不在目标位置的数字：1、2、8、6，共 4 个
# 1 需移动 1 步到达正确位置
# 2 需移动 1 步到达正确位置
# 8 需移动 2 步到达正确位置
# 6 需移动 1 步到达正确位置
# 曼哈顿距离共 5 步print(h1(start_state, goal_state))  # 4
print(h2(start_state, goal_state))  # 5

实现A*算法

为了便于替换启发函数，将其作为参数传入函数：

# 定义A*算法函数
def astar(start_state, goal_state, h):'''params:start_state - 3x3 list 初始状态goal_state  - 3x3 list 目标状态h           - function 启发函数returns:expanded_nodes - 扩展节点数run_time       - 算法运行时间path           - 算法运行路径ps. 当路径不存在时，会返回 run_time = 0, path = None'''start_time = time.time()  # 算法开始open_list = [(h(start_state, goal_state), start_state)]  # 存储待扩展的节点的优先队列closed_set = set()  # 存储已经扩展过的节点的集合came_from = {}      # 记录节点之间的关系，即每个节点的父节点是哪个节点expanded_nodes = 0  # 记录扩展节点的数量while open_list:  # 带扩展节点队列不为空_, current_state = heapq.heappop(open_list)  # 弹出优先级最高的节点expanded_nodes += 1if current_state == goal_state:  # 找到目标状态# 回溯路径path = [current_state]while tuple(map(tuple, current_state)) in came_from:current_state = came_from[tuple(map(tuple, current_state))]path.append(current_state)end_time = time.time()  # 记录算法结束时间return expanded_nodes, end_time-start_time, path[::-1]closed_set.add(tuple(map(tuple, current_state)))  # 将当前节点状态加入已扩展节点集合zero_i, zero_j = find_num(0, current_state)  # 找到当前的空格坐标moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 四周的格子for di, dj in moves:new_i, new_j = zero_i + di, zero_j + dj  # 移动的数字if 0 <= new_i < 3 and 0 <= new_j < 3:  # 确保新位置在范围内new_state = [row[:] for row in current_state]  # 拷贝 current_statenew_state[zero_i][zero_j], new_state[new_i][new_j] = current_state[new_i][new_j], current_state[zero_i][zero_j]  # 移动空白格if tuple(map(tuple, new_state)) in closed_set:continue  # 如果新状态已经扩展过，则跳过new_cost = len(came_from) + 1 + h(new_state, goal_state)  # 计算新状态的代价heapq.heappush(open_list, (new_cost, new_state))  # 将新状态加入优先队列came_from[tuple(map(tuple, new_state))] = tuple(map(tuple, current_state))  # 更新新状态的父节点信息# 无可行解return expanded_nodes, 0, None

测试

首先，定义一个函数 print_path() 用于查看路径：

def print_path(path):step = 0for state in path:print("Step. ", step)for row in state:print(row)step += 1

设置初始状态和目标状态进行测试：

# 设置初始状态和目标状态
start_state = [[2, 8, 3],[1, 6, 4],[7, 0, 5]
]goal_state = [[1, 2, 3],[8, 0, 4],[7, 6, 5]
]h1_nodes, h1_times, h1_path = astar(start_state, goal_state, h1)  # 通过 h1 启发函数调用 astar 算法
h2_nodes, h2_times, h2_path = astar(start_state, goal_state, h2)  # 通过 h2 启发函数调用 astar 算法if h1_path:print("调用 h1 启发函数的 A* 算法共扩展 {} 个节点，耗时 {}s，路径如下：".format(h1_nodes, h1_times))# print_path(h1_path)
else:print("调用 h1 启发函数的 A* 算法无法得到可行解。")# print("=" * 50)
if h2_path:print("调用 h2 启发函数的 A* 算法共扩展 {} 个节点，耗时 {}s，路径如下：".format(h2_nodes, h2_times))# print_path(h2_path)
else:print("调用 h2 启发函数的 A* 算法无法得到可行解。")

输出结果：（path 输出过长，这里省略）

调用 h1 启发函数的 A* 算法共扩展 28 个节点，耗时 0.00037217140197753906s，路径如下：
调用 h2 启发函数的 A* 算法共扩展 17 个节点，耗时 0.0002200603485107422s，路径如下：

测试鲁棒性——当可行解不存在时：

# 设置初始状态和目标状态
start_state = [[7, 8, 3],[1, 5, 2],[6, 0, 4]
]goal_state = [[1, 2, 3],[4, 5, 6],[7, 8, 9]
]h1_nodes, h1_times, h1_path = astar(start_state, goal_state, h1)  # 通过 h1 启发函数调用 astar 算法
h2_nodes, h2_times, h2_path = astar(start_state, goal_state, h2)  # 通过 h2 启发函数调用 astar 算法if h1_path:print("调用 h1 启发函数的 A* 算法共扩展 {} 个节点，耗时 {}s，路径如下：".format(h1_nodes, h1_times))# print_path(h1_path)
else:print("调用 h1 启发函数的 A* 算法无法得到可行解。")# print("=" * 50)
if h2_path:print("调用 h2 启发函数的 A* 算法共扩展 {} 个节点，耗时 {}s，路径如下：".format(h2_nodes, h2_times))# print_path(h2_path)
else:print("调用 h2 启发函数的 A* 算法无法得到可行解。")

输出结果：（path 输出过长，这里省略）

调用 h1 启发函数的 A* 算法无法得到可行解。
调用 h2 启发函数的 A* 算法无法得到可行解。

国科大的朋友们提交之前改一改哈！因为作者也是这么交的～