A* 算法求解八数码问题

A* 算法求解八数码问题前面见过宽度优先搜索和深度优先搜索求解八数码问题。那两个方法都是盲目搜索。今天看启发式搜索。A算法:利用评价函数来选择下一个节点。图引用自-北京联合大学彭涛老师在中国慕课的《人工智能概论》。估价函数没有定论,可以有不同方法。这里采用处在错误位置的数字的数量。代码在:github一组测试数据的执行搜索的过程如下:A*算法(宽度优先)求解八数码问题==========宽度优先求解八数码问题,搜索过程是==========[[203..

前面见过宽度优先搜索和深度优先搜索求解八数码问题。那两个方法都是盲目搜索。

今天看启发式搜索。

A算法: 利用评价函数来选择下一个节点。 图引用自 -北京联合大学 彭涛老师在 中国慕课的 《人工智能概论》。

A* 算法求解八数码问题

估价函数没有定论,可以有不同方法。 这里采用处在错误位置的数字的数量。

A* 算法求解八数码问题

代码在: github

一组测试数据的 执行搜索的过程如下: 

A* 算法求解八数码问题

 

A* 算法 (宽度优先)求解八数码问题
========== 宽度优先求解八数码问题,搜索过程是 ==========
[[2 0 3]
 [1 8 4]
 [7 6 5]]
当前节点的深度:1, 代价 F= G+ H (4 = 0 + 4) 
******************** 

[[2 8 3]
 [1 0 4]
 [7 6 5]]
当前节点的深度:2, 代价 F= G+ H (4 = 1 + 3) 
******************** 

[[0 2 3]
 [1 8 4]
 [7 6 5]]
当前节点的深度:2, 代价 F= G+ H (4 = 1 + 3) 
******************** 

[[1 2 3]
 [0 8 4]
 [7 6 5]]
当前节点的深度:3, 代价 F= G+ H (4 = 2 + 2) 
******************** 

[[1 2 3]
 [8 0 4]
 [7 6 5]]
当前节点的深度:4, 代价 F= G+ H (3 = 3 + 0) 
******************** 

求解路径: 
[[2 0 3]
 [1 8 4]
 [7 6 5]]
当前节点的深度:1, 代价 F= G+ H (4 = 0 + 4) 
******************** 

[[0 2 3]
 [1 8 4]
 [7 6 5]]
当前节点的深度:2, 代价 F= G+ H (4 = 1 + 3) 
******************** 

[[1 2 3]
 [0 8 4]
 [7 6 5]]
当前节点的深度:3, 代价 F= G+ H (4 = 2 + 2) 
******************** 

[[1 2 3]
 [8 0 4]
 [7 6 5]]
当前节点的深度:4, 代价 F= G+ H (3 = 3 + 0) 
******************** 

总共搜索步骤是 5, 解决方案移动步骤是3

 

今天的文章A* 算法求解八数码问题分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/13301.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注