基于淘宝的网站开发分析,浙江省建设厅门户网站,深圳注册公司需要什么条件,设计网站设计用A*算法求解八数码问题 实现两种启发函数实现A*算法测试 实现两种启发函数
采取两种策略实现启发函数#xff1a;
策略1#xff1a;不在目标位置的数字个数策略2#xff1a;曼哈顿距离#xff08;将数字直接移动到对应位置的步数总数#xff09;
# 策略1: 不在目标位置… 用A*算法求解八数码问题 实现两种启发函数实现A*算法测试 实现两种启发函数
采取两种策略实现启发函数
策略1不在目标位置的数字个数策略2曼哈顿距离将数字直接移动到对应位置的步数总数
# 策略1: 不在目标位置的数字个数即 state 与 goal_state 不相同的数字个数
def h1(state, goal_state):state, goal_state - 3x3 listdistance 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 listdistance 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 Nonestart_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* 算法无法得到可行解。国科大的朋友们提交之前改一改哈因为作者也是这么交的
