网站建设技术交流qq/怎么做私人网站
人工智能经典问题八数码求解
实际上是将求解转为寻找最优节点的问题,算法流程如下:
- 求非0元素的逆序数的和,判断是否有解
- 将开始状态放到节点集,并设置访问标识位为true
- 从节点集中取出h(x)+g(x)最小的节点
- 判断取出的节点的状态是不是最终状态,如果是的话则回溯打印
- 找出取出的节点的状态中的0的位置
- 对取出的节点进行move操作,包含up down left right
- 如果move后的状态的访问标识位为false,则添加。否则什么都不做
需要注意:节点的数据结构如下
- 状态:int数组
- h(x):当前节点的状态到目标状态的距离
- g(x):当前节点的状态到初始状态的距离
- 动作:到当前节点所进行的move类型
- 父节点:记录上一个状态,方便回溯打印
使用go语言实现如下
-
main.go
package mainimport ("container/heap""github.com/gookit/color""log""os""os/signal""syscall" )var (start = []int{2, 8, 3, 1, 6, 4, 7, 0, 5}target = []int{1, 2, 3, 8, 0, 4, 7, 6, 5} ) var (movables = []string{"up", "down", "left", "right"}moveOffsets = map[string]int{"up": -3, "down": 3, "left": -1, "right": 1} ) var (visited = make(map[string]bool) )func main() {color.BgCyan.Println("Y02114562")printFun := func(list []int) {for _, i := range list {color.BgLightCyan.Print(i, ",")}color.BgLightCyan.Print("\n")}printFun(start)printFun(target)if reverseSum(start) != reverseSum(target) {log.Fatal("不可解")}path, steps := solve(start)if steps == -1 {log.Fatal("No solution")}color.BgGreen.Println("只需:", steps, "步")color.BgGreen.Println("操作:", path)quit := make(chan os.Signal, 1)signal.Notify(quit, syscall.SIGINT, syscall.SIGTERM)<-quit }// 启发函数:h(x) 从当前状态到目标的距离 func manhattanDistance(state []int) int {distance := 0for i := 0; i < 9; i++ {if state[i] != 0 {row1, col1 := i/3, i%3// 遍历所有不为0的点,计算他与他的目标位置的曼哈顿距离for j := 0; j < 9; j++ {if state[i] == target[j] {row2, col2 := j/3, j%3distance += abs(row1-row2) + abs(col1-col2)break}}}}return distance }// 启发式搜索:八数码问题求解 func solve(start []int) ([]string, int) {// 创建起始节点startNode := &Node{State: start,Heuristic: manhattanDistance(start),G: 0,PrevMove: "",PrevNode: nil,}// 创建优先队列pq := make(PriorityQueue, 0)heap.Init(&pq)heap.Push(&pq, startNode)visited[listToString(startNode.State)] = true// A*搜索for pq.Len() > 0 {currentNode := heap.Pop(&pq).(*Node)// 到达目标状态,返回路径if listToString(currentNode.State) == listToString(target) {path := make([]string, 0)for currentNode.PrevNode != nil {path = append(path, currentNode.PrevMove)currentNode = currentNode.PrevNode}return func(slice []string) ([]string, int) {for i, j := 0, len(slice)-1; i < j; i, j = i+1, j-1 {slice[i], slice[j] = slice[j], slice[i]}return slice, len(path)}(path)}zeroIndex := func(state []int) int {for i, num := range state {if num == 0 {return i}}return -1}(currentNode.State)for _, move := range movables {if canMove(move, zeroIndex) {newState := make([]int, len(currentNode.State))copy(newState, currentNode.State)newZeroIndex := zeroIndex + moveOffsets[move]newState[zeroIndex], newState[newZeroIndex] = newState[newZeroIndex], newState[zeroIndex]// 创建新节点newNode := &Node{State: newState,Heuristic: manhattanDistance(newState),G: currentNode.G + 1,PrevMove: move,PrevNode: currentNode,}// 如果新状态未被访问,则加入优先队列和已访问集合if !visited[listToString(newState)] {heap.Push(&pq, newNode)visited[listToString(newState)] = true}}}}// 没有找到解return nil, -1 }
-
node.go
package main// Node 节点结构体 type Node struct {State []int // 当前状态Heuristic int // 启发函数值G int // 初始节点到当前节点PrevMove string // 上一步移动的方向PrevNode *Node // 上一步的节点 }// PriorityQueue 优先队列 type PriorityQueue []*Node// Len 优先队列的方法:计算长度 func (pq PriorityQueue) Len() int {return len(pq) }// Less 优先队列的方法:比较优先级 func (pq PriorityQueue) Less(i, j int) bool {return pq[i].Heuristic+pq[i].G < pq[j].Heuristic+pq[j].G }// Swap 优先队列的方法:交换元素 func (pq PriorityQueue) Swap(i, j int) {pq[i], pq[j] = pq[j], pq[i] }// Push 优先队列的方法:向队列中插入元素 func (pq *PriorityQueue) Push(x interface{}) {node := x.(*Node)*pq = append(*pq, node) }// Pop 优先队列的方法:从队列中弹出元素 func (pq *PriorityQueue) Pop() interface{} {old := *pqn := len(old)node := old[n-1]*pq = old[0 : n-1]return node }
-
tool.go
package mainimport "fmt"// 辅助函数:判断是否可移动 func canMove(move string, zeroIndex int) bool {if move == "up" && zeroIndex >= 3 {return true}if move == "down" && zeroIndex <= 5 {return true}if move == "left" && zeroIndex%3 != 0 {return true}if move == "right" && zeroIndex%3 != 2 {return true}return false }// 辅助函数:将[]int转换为字符串 func listToString(state []int) string {str := ""for _, num := range state {str += fmt.Sprintf("%d", num)}return str }// 辅助函数:求除了0之外的逆序和 func reverseSum(arr []int) bool {sum := 0for i := 1; i < len(arr); i++ {if arr[i] != 0 {for j := 0; j < i; j++ {if arr[j] > arr[i] {sum++}}}}return sum%2 != 0 }// 辅助函数:计算绝对值 func abs(num int) int {if num < 0 {return -num}return num }
运行效果
相关文章:

【人工智能实验】A*算法求解8数码问题 golang
人工智能经典问题八数码求解 实际上是将求解转为寻找最优节点的问题,算法流程如下: 求非0元素的逆序数的和,判断是否有解将开始状态放到节点集,并设置访问标识位为true从节点集中取出h(x)g(x)最小的节点判断取出的节点的状态是不…...

Kafka学习笔记(二)
目录 第3章 Kafka架构深入3.3 Kafka消费者3.3.1 消费方式3.3.2 分区分配策略3.3.3 offset的维护 3.4 Kafka高效读写数据3.5 Zookeeper在Kafka中的作用3.6 Kafka事务3.6.1 Producer事务3.6.2 Consumer事务(精准一次性消费) 第4章 Kafka API4.1 Producer A…...

Typora for Mac:打造全新文本编辑体验
Typora for Mac是一款与众不同的文本编辑器,它不仅拥有直观易用的界面,还融合了Markdown语法和富文本编辑的功能,为用户带来了前所未有的写作和编辑体验。 一、简洁明了的界面设计 Typora for Mac的界面简洁明了,让用户可以专注…...

TikTok与媒体素养:如何辨别虚假信息?
在当今数字时代,社交媒体平台如TikTok已经成为信息传播和社交互动的主要渠道之一。然而,随之而来的是虚假信息的泛滥,这对用户的媒体素养提出了严峻的挑战。本文将探讨TikTok平台上虚假信息的现象,以及如何提高媒体素养࿰…...

Spring Boot 中使用 ResourceLoader 加载资源的完整示例
ResourceLoader 是 Spring 框架中用于加载资源的接口。它定义了一系列用于获取资源的方法,可以处理各种资源,包括类路径资源、文件系统资源、URL 资源等。 以下是 ResourceLoader 接口的主要方法: Resource getResource(String location)&am…...

1688往微信小程序自营商城铺货商品采集API接口
一、背景介绍 随着移动互联网的快速发展,微信小程序作为一种新型的电商形态,正逐渐成为广大商家拓展销售渠道、提升品牌影响力的重要平台。然而,对于许多传统企业而言,如何将商品信息快速、准确地铺货到微信小程序自营商城是一个…...

QStatusBar开发详解
一、QStatusBar接口说明 QStatusBar 类是 Qt 中用于创建和管理状态栏的类。它继承自 QFrame 类,提供了在主窗口底部显示消息、进度等信息的功能。以下是一些 QStatusBar 类的重要接口: 1.1 QStatusBar构造函数 QStatusBar(QWidget *parent nullptr);…...

后端接口性能优化分析-程序结构优化
👏作者简介:大家好,我是爱吃芝士的土豆倪,24届校招生Java选手,很高兴认识大家📕系列专栏:Spring源码、JUC源码🔥如果感觉博主的文章还不错的话,请👍三连支持&…...

【SpringBoot3+Vue3】三【实战篇】-后端(优化)
目录 一、登录优化-redis 1、SpringBoot集成redis 1.1 pom 1.2 yml 1.3 测试程序(非必须) 1.4 启动redis,执行测试程序 2、令牌主动失效(代码优化) 2.1 UserController设置token到redis 2.2 登录拦截器Log…...

DevExpress中文教程 - 如何在macOS和Linux (CTP)上创建、修改报表(上)
DevExpress Reporting是.NET Framework下功能完善的报表平台,它附带了易于使用的Visual Studio报表设计器和丰富的报表控件集,包括数据透视表、图表,因此您可以构建无与伦比、信息清晰的报表。 DevExpress Reports — 跨平台报表组件&#x…...

一个iOS tableView 滚动标题联动效果的实现
效果图 情景 tableview 是从屏幕顶部开始的,现在有导航栏,和栏目标题视图将tableView的顶部覆盖了 分析 我们为了达到滚动到某个分区选中标题的效果,就得知道 展示最顶部的cell或者区头在哪个分区范围内 所以我们必须首先获取顶部的位置 …...

代码执行相关函数以及简单例题
代码/命令 执行系列 相关函数 (代码注入)...

大数据爬虫分析基于Python+Django旅游大数据分析系统
欢迎大家点赞、收藏、关注、评论啦 ,由于篇幅有限,只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 基于Python和Django的旅游大数据分析系统是一种使用Python编程语言和Django框架开发的系统,用于处理和分…...

C# 结构体介绍
文章目录 定义结构体实例化结构体结构体的值类型特性结构体和类的区别限制 C# 中的结构体(Struct)是一种值类型数据结构,用于封装不同或相同类型的数据成一个单一的实体。结构体非常适合用来表示轻量级的对象,比如坐标点、颜色值或…...

【机器学习】特征工程:特征预处理,归一化、标准化、处理缺失值
特征预处理采用的是特定的统计方法(数学方法)将数据转化为算法要求的数字 1. 数值型数据 归一化,将原始数据变换到[0,1]之间 标准化,数据转化到均值为0,方差为1的范围内 缺失值,缺失值处理成均值、中…...

Pytorch torch.norm函数详解用法
torch.norm参数定义 torch版本1.6 def norm(input, p"fro", dimNone, keepdimFalse, outNone, dtypeNone)input input (Tensor): the input tensor 输入为tensorp p (int, float, inf, -inf, fro, nuc, optional): the order of norm. Default: froThe following …...

【DevOps】Git 图文详解(二):Git 安装及配置
Git 图文详解(二):Git 安装及配置 1.Git 的配置文件2.配置 - 初始化用户3.配置 - 忽略.gitignore Git 官网:https://www.git-scm.com/ 下载安装包进行安装。Git 的使用有两种方式: 命令行:Git 的命令通过系…...

亚马逊美国站CPC认证ASTM F963测试项目要求有哪些?
ASTM F963是美国材料和试验联合会(ASTM)制定的儿童玩具安全性的标准规范,专门针对儿童玩具产品的安全性进行了规定和要求。 ASTM F963标准的内容和要求包括: 1、物理机械性能:规定了玩具的物理机械性能要求࿰…...

通付盾Web3专题 | KYT/AML:Web3合规展业的必要条件
与传统证券一样,基于区块链技术发展出来的虚拟资产交易所经历了快速发展而缺乏有效监管的行业早期。除了科技光环加持的各种区块链项目方、造富神话之外,交易所遭到黑客攻击、内部偷窃作恶、甚至经营主体异常而致使投资人血本无归的案例亦令人触目惊心。…...

Centos8配置Zabbix5.0中文汉化
1.点击【Sign in】按钮,输入用户名和密码进入Zabbix的首页,结果如图。 2.点击左边导航栏的【User settings】链接,进入用户个性化设置界面,结果如图。 3.在搭建Zabbix的虚拟机上使用yum命令下载中文包。 yum install glibc-langpa…...

元数据管理,数字化时代企业的基础建设
随着新一代信息化、数字化技术的应用,众多领域通过科技革命和产业革命实现了深度化的数字改造,进入到以数据为核心驱动力的,全新的数据处理时代,并通过业务系统、商业智能BI等数字化技术和应用实现了数据价值,从数字经…...

大数据之Hive:regexp_extract函数案例
目录 一、正则的通配符简介1、正则表达式的符号及意义2、各种操作符的运算优先级: 二、案例数据要求分析实现输出结果实现2实现3 总结 一、正则的通配符简介 1、正则表达式的符号及意义 符号含义实列/做为转意,即通常在"/"后面的字符不按原来…...

tsconfig.json无法写入文件“XXXX“因为它会覆盖输入文件
在开发ts项目的时候,包错提示无法写入文件: tsconfig.json无法写入文件"XXXX"因为它会覆盖输入文件 这是tsconfig.json文件配置问题,需要加入下面的配置就好了: {"compilerOptions": {"outDir": …...

本周Github有趣项目:draw-a-ui等
有趣的项目、工具和库 gpt-crawler 抓取网站以生成知识文件,从而从 URL 创建您自己的自定义 GPT。 需要步骤: 配置运行爬虫、 将您的数据上传到 OpenAI:使用此选项通过 UI 访问您生成的知识,您可以轻松与他人共享 创建自定义助…...

VBA如何快速识别Excel单元格中的文本数字
Excel中一种非常特殊的数字,这些数字看似数字,其实是文本格式(下文简称为文本数字),在单元格的左上角会有一个绿色小三角作为标志,如B1:B3单元格。 在编程时为什么需要区分普通数字和文本数字呢ÿ…...

Mysql数据库 16.SQL语言 数据库事务
一、数据库事务 数据库事务介绍——要么全部成功要么全部失败 我们把完成特定的业务的多个数据库DML操作步骤称之为一个事务 事务——就是完成同一个业务的多个DML操作 例: 数据库事务四大特性 原子性(A):一个事务中的多个D…...

docker 部署Redis集群(三主三从,以及扩容、缩容)
1:创建6个redis容器 docker run -d --name redis01 --net host --privilegedtrue -v /opt/redis/redis01:/data redis:6.0.8 --cluster-enabled yes --appendonly yes --port 6381 docker run -d --name redis02 --net host --privilegedtrue -v /opt/redis/redis0…...

JavaScript 浮点数运算的精度问题及解决
JavaScript 浮点数运算的精度问题及解决 在 JavaScript 中整数和浮点数都属于 Number 数据类型,当浮点数做数学运算的时候,你经常会发现一些问题,举几个例子: 0.1 0.2 0.30000000000000004 console.log(0.1 0.2) 0.3000000…...

基于STM32的无线传感器网络(WSN)通信方案设计与实现
无线传感器网络(Wireless Sensor Network,简称WSN)是由一组分布式的无线传感器节点组成的网络,用于监测和收集环境中的各类物理信息。本文将基于STM32微控制器,设计并实现一个简单的无线传感器网络通信方案,…...

Flink和Kafka连接时的精确一次保证
Flink写入Kafka两阶段提交 端到端的 exactly-once(精准一次) kafka -> Flink -> kafka 1)输入端 输入数据源端的 Kafka 可以对数据进行持久化保存,并可以重置偏移量(offset) 2)Flink内…...