当前位置: 首页 > news >正文

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

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

  • 实现两种启发函数
  • 实现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* 算法无法得到可行解。

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

相关文章:

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

用A*算法求解八数码问题 实现两种启发函数实现A*算法测试 实现两种启发函数 采取两种策略实现启发函数&#xff1a; 策略1&#xff1a;不在目标位置的数字个数策略2&#xff1a;曼哈顿距离&#xff08;将数字直接移动到对应位置的步数总数&#xff09; # 策略1: 不在目标位置…...

分布式之Ribbon使用以及原理

Ribbon使用以及原理 1、负载均衡的两种方式 服务器端负载均衡 传统的方式前端发送请求会到我们的的nginx上去&#xff0c;nginx作为反向代理&#xff0c;然后路由给后端的服务器&#xff0c;由于负载均衡算法是nginx提供的&#xff0c;而nginx是部署到服务器端的&#xff0c;所…...

android JNI float *转MutableList

data class Test(var data:MutableList<Float> )JNIEXPORT void JNICALL Java_NativeUtils_assignFloatArrayToHealth(JNIEnv *env, jclass clazz, jobject obj, jfloatArray cData) {jclass objClass env->GetObjectClass(obj);// 获取 Test类中的 data 属性jfieldI…...

chatgpt与人类有何不同?

ChatGPT和人类之间存在多个显著的差异。 首先&#xff0c;ChatGPT是一种基于人工智能技术的计算机程序&#xff0c;通过机器学习和自然语言处理等技术&#xff0c;从大量的数据中获取知识并生成语言输出。它主要依赖于算法和数据进行工作&#xff0c;能够迅速处理和检索信息&a…...

论文笔记:Evaluating the Performance of Large Language Models on GAOKAO Benchmark

1 论文思路 采用zero-shot prompting的方式&#xff0c;将试题转化为ChatGPT的输入 对于数学题&#xff0c;将公式转化为latex输入 主观题由专业教师打分 2 数据 2010~2022年&#xff0c;一共13年间的全国A卷和全国B卷 3 结论 3.1 不同模型的zeroshot 高考总分 3.2 各科主…...

MySQL 数据库查询与数据操作:使用 ORDER BY 排序和 DELETE 删除记录

使用 ORDER BY 进行排序 使用 ORDER BY 语句按升序或降序对结果进行排序。 ORDER BY 关键字默认按升序排序。要按降序排序结果&#xff0c;使用 DESC 关键字。 示例按名称按字母顺序排序结果&#xff1a; import mysql.connectormydb mysql.connector.connect(host"l…...

数据结构入门(3)2.链表接口实现

目录 前言 头文件 动态申请一个结点 单链表打印 单链表尾插 单链表的头插 单链表的尾删 单链表头删 单链表查找 单链表在pos位置之后插入x 单链表删除pos位置之后的值 在pos的前面插入 删除pos位置 销毁顺序表 前言 本文将介绍链表常见的功能的实现 头文件 #…...

vscode中解决驱动编写的时候static int __init chrdev_init()报错的问题

目录 错误出错原因解决方法 错误 在入口函数上&#xff0c;出现 expected a ; 这样的提示 出错原因 缺少了 __KERNEL __ 宏定义 解决方法 补上__KERNEL__宏定义 具体做法&#xff1a;在vscode中按下ctrlshiftp &#xff0c;输入&#xff1a;C/C:Edit Configurations&#xff0…...

fastgpt本地详细部署以及配置

目录 一、Docker部署1、docker安装2、docker启动3、添加用户到 docker 组:4、验证 Docker 安装:二、one_api 本地部署1、linux系统部署2、windows系统部署三、向量模型部署(m3e)四、chatglm2模型本地部署五、fastgpt模型本地部署1、下载配置文件2、文件配置--docker-compos…...

【故障分类】基于注意力机制的卷积神经网络结合双向长短记忆神经网络CNN-BiLSTM-attention实现数据分类附matlab代码

摘要&#xff1a; ntion机制加权 4. 加权后的特征进行分类 需求分析 本文旨在实现一个通用的数据分类模型&#xff0c;可应用于不同领域的数据分类任务。 设计方案 设计一个CNN网络结构&#xff0c;提取输入数据的特征 将特征序列输入到BiLSTM网络&#xff0c;进行时序建模…...

vue接入百度地图获取经纬度

通过城市名称和城市中心经纬度来获取当前所在地图&#xff0c;当前经纬度中心获取可以通过后端获取 静态文件包&#xff0c;替换baidu.html中的ak值&#xff0c;ak值通过百度地图官方网站申请 申请&#xff1a;百度地图API申请步骤 - 知乎 代码示例文件&#xff1a; 链接&a…...

交流负载箱的特点和优势有哪些?

交流负载箱广泛应用于电力系统、新能源、轨道交通、航空航天等领域。它具有以下特点和优势&#xff1a; 1. 灵活性高&#xff1a;交流负载箱可以根据实际需求&#xff0c;调整输出电流、电压、功率等参数&#xff0c;以满足不同场景下的测试需求。同时&#xff0c;它还可以实现…...

Java线程锁之Lock的使用

Lock 的使用 Lock 是java 1.5 中引入的线程同步工具&#xff0c;它主要用于多线程下共享资源的控制。本质上Lock 仅仅是一个接口&#xff0c; 可以通过显式定义同步锁对象来实现同步&#xff0c;能够提供比synchronized 更广泛的锁定操作&#xff0c;并支持多个相关的 Lock接…...

简站wordpress主题看上去差不多 实际大不一样

有人说简站wordpress主题&#xff0c;都差不多嘛。我表示无语。表面看上去是差不多的&#xff0c;实际的细节是不一样的。 下面以编号&#xff1a;JZP4431和编号&#xff1a;JZP4878这两个主题为例子来讲一下&#xff0c;简站wordpress主题&#xff0c;在细节方面的不一样之处…...

(完美方案)解决mfc140u.dll文件丢失问题,快速且有效的修复

唉&#xff0c;又是丢失了mfc140u.dll&#xff0c;这该怎么办呢&#xff1f;如果你的电脑突然找不到或丢失mfc140u.dll文件&#xff0c;那就真是太糟糕了。别担心&#xff0c;我分享给你一些干货&#xff0c;告诉你如何快速解决mfc140u.dll丢失的问题。 一.mfc140u.dll属性功能…...

并发通信(网络进程线程)

如果为每个客户端创建一个进程&#xff08;或线程&#xff09;&#xff0c;因为linux系统文件标识符最多1024位&#xff0c;是有限的。 所以使用IO复用技术&#xff0c;提高并发程度。 阻塞与非阻塞 阻塞式复用 非阻塞复用 信号驱动IO 在属主进程&#xff08;线程中声明&…...

WPF 该线程是用不接受参数的 ThreadStart 委托创建的。

创建无参数线程是无法发去传递参数的&#xff0c;需要把 《 thread.Start(“张三”); 》改为《 thread.Start(); 》 把参数去掉就可以了。 public RegisterWindow(){InitializeComponent();//无参数线程Thread thread new Thread(pageLoad);thread.IsBackground true;//thr…...

FreeRTOS学习第9篇--队列介绍

目录 FreeRTOS学习第9篇--队列介绍1. 数据传输的方法1.1 任务之间如何传输数据1.2 队列的本质 2. 队列的工作原理和实现2.1 创建队列2.2 向队列发送数据2.3 从队列接收数据 3. 使用队列进行任务间的通信3.1 通信示例3.2 同步示例 结论 FreeRTOS学习第9篇–队列介绍 本文目标&a…...

qt如何配置ros环境

在Qt5.7的版本可以使用bash -i -c来启动qt&#xff0c;让Qt自己识别系统环境&#xff0c;不知道为什么Qt在之后的版本&#xff0c;这样使用都失效了。因为它会默认把CMAKE_PREFIX_PATH修改掉。 网上还有安装ros插件版本的qt creator&#xff0c;感觉失去了一些灵活性。 自己测试…...

20240310-1-Java后端开发知识体系

Java 基础 知识体系 Questions 1. HashMap 1.8与1.7的区别 1.71.8底层结构数组链表数组链表/红黑树插入方式头插法尾插法计算hash值4次位运算5次异或运算1次位运算1次异或运算扩容、插入先扩容再插入先插入再扩容扩容后位置计算重新hash原位置或原位置旧容量 (1) 扩容因子…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...