A-star-algorithm

介绍

A*算法解决15数码问题(Java实现)

一、15数码问题

15数码问题：一个4*4的16宫格棋盘上，摆放有15个将牌，每一个都刻有1-15中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。所要求解的问题：是给定一种初始布局(初始状态)和一个目标布局(目标状态),问如何移动数码实现从初始状态到目标状态的转变。

二、A*算法

2.1 什么是A*算法？

A*算法，A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。A*算法是一种启发式搜索算法，启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到达到目标。在搜索过程中需要根据启发函数来帮助选择搜索路径。

2.2 启发函数设计

• 启发函数：f(n) = g(n) + P(n) g(n):从初始结点 s 到结点 n 路径的耗散值 P(n):每一个数码与其目标位置间的距离的总和

三、解决思路

①将初始状态结点加入OPEN
②找到OPEN中f(n)最小的结点 n
③如果该结点（n）达到目标状态，回溯结果进行输出，程序结束。否则进行下一步
④从OPEN中移除结点n，加入CLOSED，遍历n所有邻近结点（即可以移动到达的位置所对应的状态），设置这些邻近结点父结点为n，并给其它字段赋值，判断邻近结点是否在CLOSED，若在则不进行操作，否则进行下一步
⑤将该邻近结点加入OPEN，返回②