# A-star-algorithm

**Repository Path**: wtongxue/a-star-algorithm

## Basic Information

- **Project Name**: A-star-algorithm
- **Description**: A*算法解决15数码问题(Java实现)
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-11-29
- **Last Updated**: 2021-11-30

## Categories & Tags

**Categories**: Uncategorized

**Tags**: A-star算法, 15数码问题, 8数码问题

## README

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