0%

A star算法八数码问题—求解数字华容道

A star算法也叫A*算法,是一种启发式搜索算法。八数码问题是搜索问题中比较经典的问题,可以有很多种搜索策略,比如说有最常见的BFS,DFS。而在八数码问题中A star算法往往能够得到最优的求解路径。
以数字华容道为例,用A star算法解决八数码问题。
人工智能课作业~

A star算法八数码问题—求解数字华容道

A star 算法介绍

A star(也称为A *)是找到节点或图之间最短路径的最成功的搜索算法之一。 这是一种明智的搜索算法,因为它使用有关路径成本的信息,并且还使用启发式算法来找到解决方案。(来自下面参考文章中的一段话)

在A star中我们会用到下面这几个东西(这些可以直接看下面给的链接,不多解释了,内容太多了)

最主要的还是说一下,A star 算法的核心就是他的公式f(n) = g(n) + h(n)

1
2
3
4
f(n) = g(n) + h(n)
f(n): 最低成本
g(n):从起始点(start)到当前点(current)所花费的成本(cost)
h(n):从当前点(current)到终点(end)的启发式预估成本

当然这样就会有两种极端情况,当h(n)=0,也就是只有g(n)起作用,此时A star演变成Dijkstra算法,这保证能找到最短路径。当h(n)>>g(n),也就是g(n)的影响忽略不计,只有h(n)起作用,A star演变成BFS算法。

这里的BFS不是广度优先遍历,而是Best-First Search最佳优先搜索。Dijkstra算法是广度优先遍历的那个BFS的升级版。为什么我要提呢,因为我的组员就搞错了

对于A star的介绍网上有很多,我这里只是简单介绍一下,具体关于A star的内容可以参考下面两篇文章

A star介绍:

国外原文链接 https://www.gamedev.net/reference/articles/article2003.asp

国内翻译链接 https://blog.csdn.net/debugconsole/article/details/8165530

国外原文链接 https://towardsdatascience.com/a-star-a-search-algorithm-eb495fb156bb

八数码问题介绍

8-puzzle problem(八数码问题),是由3x3框架中的八个编号的可活动拼图组成,框架中的一个单元始终是空的,因此可以将相邻编号的图块移动到空单元中。

在这个问题中的所有可能性包含8个可移动拼图和空白块,一共会有9!种可能,也就是362880种。我们需要不断的移动空白方块的位置,从初始状态转换到最终目标上。

八数码问题对应到数字华容道游戏上,数字华容道实际上就是个八数码拼图游戏,初始状态随机,最终目标状态固定而已。

所以接下来就是运用A star解决八数码问题—求解数字华容道的实现。

Java实现求解数字华容道

首先我们创建一个class Node,在Node中我们需要设置好几个变量。

  • nums 用一维数组来保存某个状态的具体内容。比如终点状态我们就表示为 {1, 2, 3, 4, 5, 6, 7, 8, 0}
  • step 从起点到当前状态一共走了几步 —— 即 g(n)
  • cost 当前状态的估价函数的值 —— 即 f(n)
  • zeroPos 当前状态下,空白方格所在位置的索引——这个成员变量仅是为了方便而设计的
  • movedPath 当前这个节点从最初始节点移动到当前状态的过程,记录了之前移动的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
class Node implements Comparable<Node> {
int[] nums;
int step; // g(n)
int cost; // f(n)
int zeroPos;
LinkedList<Integer> movedPath;
public Node(int[] nums, int step, int zeroPos) {
this.movedPath = new LinkedList<Integer>();
this.nums = nums;
this.step = step;
this.zeroPos = zeroPos;
this.setCost();
}

在构造器中调用了setCost,也就是为每一个位置计算当前的价值成本,数值越低,成本越低,优先度越高

在这个程序中h(n)的计算方法很简单,因为只需要满足单调递增就行了,所以这里直接用变量自增的方法做到单调递增,虽然看起来很简单,但是有效啊🙄。

1
2
3
4
5
6
7
8
9
  public void setCost() {
int c = 0;
for (int i = 0; i < Node.level; i++) {
if (nums[i] != goal[i])
c++;
/* f(n) */this.cost = /* g(n) */step + /* h(n) */c;
// /* f(n) */this.cost = /* g(n)step + */ /* h(n) */c;
}
}

我们需要对这些节点进行排序,我们只需要不断的拿去成本低的节点,所以后面使用一个优先队列进行排序。继承的Comparable就是直接对cost进行比较就行了。

1
2
3
4
@Override
public int compareTo(Node o) {
return (this.cost - o.cost);
}

当我们移动白色白块到数字块的时候实际上就是两个位置的交换,交换的方式就是以为数组坐标直接交换

1
2
3
4
5
6
public static void swap(Node x, int a, int b) {
int[] ops = x.nums;
int k = ops[a];
ops[a] = ops[b];
ops[b] = k;
}

这个Node类中我们需要维护一个movedPath变量,维护的方法是通过setPath方法,传入的path是做好新移动后的一个linkList,将这个移动的list重新深度拷贝给movedPath,当做之前的移动数据。

1
2
3
4
5
6
7
public Node setPath(LinkedList<Integer> path) {
this.movedPath = new LinkedList<Integer>();
for (Integer k : path) {
this.movedPath.add(k);
}
return this;
}

除了路径的深度拷贝,对于实例化的Node对象也有深度拷贝的需求

1
2
3
4
5
6
7
public static Node copy(Node x) {
Node out = new Node(new int[Node.level], x.step, x.zeroPos);
for (int i = 0; i < Node.level; i++) {
out.nums[i] = x.nums[i];
}
return out;
}

A star算法需要两个表,一个是open表已经访问过的位置,一个是close表还没有访问的位置。在这个程序中我们只需要维护open表就可以,使用HashMap<String, Boolean>。然后我们就需要记录当前节点的nums,所以就需要下面这个toString方法进行字符串转换,方便哈希表的记录

1
2
3
4
5
6
7
public static String arrayToString(int[] x) {
StringBuilder sb = new StringBuilder();
for (int k : x) {
sb.append(k).append('-');
}
return sb.toString();
}

最后是Node类的一些静态变量,之前准备做4阶数字华容道的时候留下的。

1
2
3
4
5
static int difficulty = 3;
static int level = 9;
static int[] goal;
static int[][] moveAble;
static LinkedList<Integer> nowPath; // 用于记录当前路径,只需要保存按顺序点击的节点就好了

对应的还有setDifficulty方法设置几阶的数字华容道,默认还是3阶的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public static void setDifficulty(int n) {
Node.difficulty = n;
Node.level = n * n;
Node.goal = new int[Node.level];
for (int i = 0; i < Node.level - 1; i++) {
Node.goal[i] = i + 1;
// System.out.printf(" %d,", i);
}
Node.goal[Node.level - 1] = 0;
if (n == 3) {
moveAble = new int[][] { { 1, 3, -1, -1 }, { 0, 2, 4, -1 }, { 1, 5, -1, -1 }, { 0, 4, 6, -1 }, { 1, 3, 5, 7 },
{ 2, 4, 8, -1 }, { 3, 7, -1, -1 }, { 4, 6, 8, -1 }, { 5, 7, -1, -1 }, };
}
/*
* else if (n == 4) { moveAble = new int[][] { { 1, 4, -1, -1 }, { 0, 2, 5, -1
* }, { 1, 3, 6, -1 }, { 2, 7, -1, -1 }, { 0, 5, 8, -1 }, { 1, 4, 6, 9 }, { 2,
* 5, 7, 10 }, { 3, 6, 11, -1 }, { 4, 9, 12, -1 }, { 5, 8, 10, 13 }, { 6, 9, 11,
* 14 }, { 7, 10, 15, -1 }, { 8, 13, -1, -1 }, { 9, 12, 14, -1 }, { 10, 13, 15,
* -1 }, { 11, 14, -1, -1 }, }; } else if (n == 5) { moveAble = new int[][] { {
* 1, 5, -1, -1 }, { 0, 2, 6, -1 }, { 1, 3, 7, -1 }, { 2, 4, 8, -1 }, { 3, 9,
* -1, -1 }, { 0, 6, 10, -1 }, { 1, 5, 7, 11 }, { 2, 6, 8, 12 }, { 3, 7, 9, 13
* }, { 4, 8, 14, -1 }, { 5, 11, 15, -1 }, { 6, 10, 12, 16 }, { 7, 11, 13, 17 },
* { 8, 12, 14, 18 }, { 9, 13, 19, -1 }, { 10, 16, 20, -1 }, { 11, 15, 17, 21 },
* { 12, 16, 18, 22 }, { 13, 17, 19, 23 }, { 14, 18, 24, -1 }, { 15, 21, -1, -1
* }, { 16, 20, 22, -1 }, { 17, 21, 23, -1 }, { 18, 22, 24, -1 }, { 19, 23, -1,
* -1 }, }; }
*/ else
moveAble = new int[][] { {} };
}

在这里有一个神奇的变量moveAble,这个变量是这个程序的关键组成部分,他代表了当前位置的白块可以往哪个位置进行交换。当我将moveAble竖着写就能看明白了。一个二维int数组,这个数组包含9个一维数组,每个一维数组包含4个int。先从这9个一维数组开始解释,这9个一维数组分别对应九宫格也就是数字华容道的每个位置上这个点可以与之进行交换的方块位置。一维数组中的四个int表示位置信息,如果不能交换就是-1。举个🌰:比如说空白格子在第0个位置,他可以往右移动(右方坐标为1),可以往下移动(下方坐标为3),但是不能往左(不能移动设置为-1),不能往上(不能移动设置为-1)。再比如最中间也就是4号位置(一位数组第五个),可以往右、往下、往左、往上,那对应的坐标就是(1、3、5、7)。

1
2
3
4
5
6
7
8
9
10
moveAble = new int[][]{
{1, 3, -1, -1},
{0, 2, 4, -1},
{1, 5, -1, -1},
{0, 4, 6, -1},
{1, 3, 5, 7},
{2, 4, 8, -1},
{3, 7, -1, -1},
{4, 6, 8, -1},
{5, 7, -1, -1}};

到这里,关于Node的介绍已经介绍完了,后面就是如何使用A star进行计算了

  • 首先做基本配置:设置Difficulty(默认就是3x3),初始化moveAble、哈希表、优先队列。然后将当前节点ToString后存储到哈希表中并将这个节点加入到优先队列中。
  • 进入do-while循环,在循环中流程如下
    • 从队列的头部移除一个Node,并获得到这个Node
    • 对这个Node进行深度拷贝(Node.copy())
    • 根据之前介绍的moveAble,我们会最多得到4个新的节点,最少两个新的节点,为每个移动创建对应的节点,如果这个节点符合最终目标状态,就直接返回结束程序;如果不是,那就将这个节点的信息ToString保存到哈希表中,并加入到优先队列准备下一次的运算(当然保存哈希表和加入队列之前需要先判断是否存在哈希表,如果存在哈希表那就说明之前以及运算过当前这个状态的节点了,就不需要重复计算了,不然就重复套娃)。
  • 如果队列是空的时候就可以退出循环并返回null表示无解,但A star一定会有最优解,所以这里就是留着而已。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Astar_HRD {

public Object[] bfsHash(int[] start, int zeroPos) {
Node.setDifficulty(3);
int[][] moveAble = Node.moveAble;
Map<String, Boolean> myMap = new HashMap<String, Boolean>(); // 用于检查这个节点是不是见过 —— 单调性保证了见过的节点不用再看
Queue<Node> que = new PriorityQueue<>(); // 优先队列 —— 用于遍历的主体储存器
String goal_code = Node.arrayToString(Node.goal);
que.add(new Node(start, 0, zeroPos));
myMap.put(Node.arrayToString(start), true);
do {
Node e = que.poll();
int pos = e.zeroPos;
for (int i = 0; i < 4; i++) {
Node ie = Node.copy(e);
Node.nowPath = new LinkedList<Integer>();
Node.nowPath.addAll(e.movedPath);
if (moveAble[pos][i] != -1) {
Node.swap(ie, pos, moveAble[pos][i]);
Node.nowPath.add(moveAble[pos][i]);
// if (Node.check(ie,moveAble[pos][i])) continue;
String k = Node.arrayToString(ie.nums);
if (k.equals(goal_code)) {
return Node.nowPath.toArray();
}
if (!myMap.containsKey(k)) {
que.add(new Node(ie.nums, e.step + 1, moveAble[pos][i]).setPath(Node.nowPath));
// System.out.println("k is "+k);
myMap.put(k, true);
System.out.printf("size: %d > %s\n", myMap.size(), k);
}
}
}
} while (!que.isEmpty());
return null;
}

完整项目戳这里(队友gitee)




======================
全 文 结 束    感 谢 阅 读
======================