关键字：八数码、BFS、堆优化BFS、双向BFS、
A*算法、迭代加深、IDA*
题目
$3*3$的棋盘，移动空格位置，问初始状态到目标状态的最小步数。（便于书写，空格记为$x$）
简要分析
最短路径问题想到BFS，从初始状态开始逐层扩展（扩展出2/3/4个状态），最先到达目标状态的即为最小的步数。
棋盘的状态数：$9阶乘=362880$
关于是否有解
对于 $奇数*奇数$ 的数码问题来说，移动$x$不改变逆序对个数的奇偶性。因此，对于$3*3$的八数码而言，目标状态12345678x逆序对个数是0即偶数，因此初始状态的逆序对个数为偶数时才有解。
0x01 BFS
分析
广度优先搜索，使用dist数组记录每个状态的最短距离，path数组记录每个状态的路径。
代码
import java.util.*;
/**
* 八数码问题： BFS
*/
public class EightDigital_T1_BFS{
private static final int N = 3;
private static String end = "12345678x";
private static int[] dx = {1, 0, -1, 0}, dy = {0, -1, 0, 1};
private static String[] move = {"D", "L", "U", "R"};
private static Map<String, String> path = new HashMap<>(); // 记录路径
private static Map<String, Integer> dist = new HashMap<>(); // 记录距离
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String start = sc.nextLine().replace(" ", "");
//System.out.println(start);
if(calcInversionPair(start) % 2 == 1){
System.out.println("-1");
return ;
}
bfs(start);
System.out.println(path.get(end)); // 输出路径
System.out.println(dist.get(end)); // 输出步数
sc.close();
}
private static void bfs(String start){
Queue<String> q = new LinkedList<>();
q.add(start);
path.put(start, "");
dist.put(start, 0);
while(!q.isEmpty()){
String state = q.poll();
if(end.equals(state)){
// 结束
break;
}
String curPath = path.get(state);
Integer curDist = dist.get(state);
// 找x的位置
int x = -1, y = -1;
for(int i = 0 ; i < N*N ; i ++){
if(state.charAt(i) == 'x'){
x = i / N;
y = i % N;
break;
}
}
for(int i = 0 ; i < 4 ; i ++){
int a = x + dx[i];
int b = y + dy[i];
if(a < 0 || b < 0 || a >= N || b >= N) continue;
String newState = generateState(state, x*N+y, a*N+b);
if(dist.get(newState) != null) continue;
path.put(newState, curPath + move[i]);
dist.put(newState, curDist + 1);
q.add(newState);
}
}
}
/**
* 字符串s中下标a, b交换位置， 并输出新串（不能改变原串）
*/
private static String generateState(String state, int i1, int i2){
char[] ch = state.toCharArray();
ch[i1] = state.charAt(i2);
ch[i2] = state.charAt(i1);
return new String(ch);
}
/**
* 逆序对的数量，对于 奇数*奇数 的数码问题来说，移动x不改变逆序对个数的奇偶性，因此
* 对于八数码而言，12345678x逆序对个数是0偶数，因此初始状态的逆序对个数为偶数时才有解
*/
private static int calcInversionPair(String s){
int num = 0;
for(int i = 0 ; i < N * N ; i ++){
for(int j = i + 1 ; j < N * N ; j ++){
if(s.charAt(i) == 'x' || s.charAt(j) == 'x')
continue;
if (s.charAt(j) > s.charAt(i))
num++;
}
}
return num;
}
}
0x02 双向BFS
分析
双向BFS搜素，初始状态和目标状态同时进行搜索（两边轮流，每次各扩展一层），当两边搜索的状态有重合时，说明搜索过程相遇，即首尾相接。合并两个路径即可。
rq、rpath和rdist分别为从目标状态开始搜索的队列、路径和距离。
注意点，因为最终要找的路径是重合状态 → 目标状态，而从目标状态开始搜索的路径rpath里是目标状态 → 重合状态，因此要：
- 路径
rpath需要取反方向（比如目标状态向左搜索，则记录的路径是向右） - 合并的时候，
rpath路径要reverse()取反。
代码改动（基于0x01 BFS）
- rq、rpath和rdist
- path.put时取反、输出路径时reverse
代码
import java.util.*;
/**
* 八数码问题： 双向BFS
*/
public class EightDigital_T2_TwoWayBFS{
private static final int N = 3;
private static String end = "12345678x";
private static int[] dx = {1, 0, -1, 0}, dy = {0, -1, 0, 1};
private static String[] move = {"D", "L", "U", "R"};
private static Map<String, String> path = new HashMap<>(); // 记录路径
private static Map<String, String> rpath = new HashMap<>(); // 记录路径
private static Map<String, Integer> dist = new HashMap<>(); // 记录距离
private static Map<String, Integer> rdist = new HashMap<>(); // 记录路径
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String start = sc.nextLine().replace(" ", "");
//System.out.println(start);
if(calcInversionPair(start) % 2 == 1){
System.out.println("-1");
return ;
}
bfs(start);
//System.out.println(path.get(end)); // 输出路径
//System.out.println(dist.get(end)); // 输出步数
sc.close();
}
private static void bfs(String start){
Queue<String> q = new LinkedList<>();
Queue<String> rq = new LinkedList<>(); //从目标状态开始的反向搜索队列
q.add(start); rq.add(end);
path.put(start, ""); rpath.put(end, "");
dist.put(start, 0); rdist.put(end, 0);
while(!q.isEmpty()){
// 0正向, 1反向
boolean r = search(q, path, rpath, dist, rdist, 0);
if(r) break;
r = search(rq, rpath, path, rdist, dist, 1);
if(r) break;
}
}
// 从队列中取出一个状态进行扩展
private static boolean search(
Queue<String> q,
Map<String, String> path,
Map<String, String> rpath,
Map<String, Integer> dist,
Map<String, Integer> rdist,
int order
){
String state = q.poll();
String curPath = path.get(state);
Integer curDist = dist.get(state);
// 找x的位置
int x = -1, y = -1;
for(int i = 0 ; i < N*N ; i ++){
if(state.charAt(i) == 'x'){
x = i / N;
y = i % N;
break;
}
}
for(int i = 0 ; i < 4 ; i ++){
int a = x + dx[i];
int b = y + dy[i];
if(a < 0 || b < 0 || a >= N || b >= N) continue;
String newState = generateState(state, x*N+y, a*N+b);
if(dist.get(newState) != null) continue;
if(order == 0){
// 正向
path.put(newState, curPath + move[i]);
}else{
// 逆向
path.put(newState, curPath + move[(i + 2) % 4]);
}
dist.put(newState, curDist + 1);
if(rdist.get(newState) != null){
if(order == 0){
// 正序
StringBuilder strbud = new StringBuilder(rpath.get(newState));
System.out.println(path.get(newState) + strbud.reverse().toString());
}else{
// 逆序
StringBuilder strbud = new StringBuilder(path.get(newState));
System.out.println(rpath.get(newState) + strbud.reverse().toString());
}
return true;
}
q.add(newState);
}
return false;
}
/**
* 字符串s中下标a, b交换位置， 并输出新串（不能改变原串）
*/
private static String generateState(String state, int i1, int i2){
char[] ch = state.toCharArray();
ch[i1] = state.charAt(i2);
ch[i2] = state.charAt(i1);
return new String(ch);
}
/**
* 逆序对的数量，对于 奇数*奇数 的数码问题来说，移动x不改变逆序对的奇偶性，因此
* 对于八数码而言，12345678x逆序对是0偶数，因此初始状态的逆序对只有为偶数时才有解
*/
private static int calcInversionPair(String s){
int num = 0;
for(int i = 0 ; i < N * N ; i ++){
for(int j = i + 1 ; j < N * N ; j ++){
if(s.charAt(i) == 'x' || s.charAt(j) == 'x')
continue;
if (s.charAt(j) > s.charAt(i))
num++;
}
}
return num;
}
}优化代码（交替逐层扩展）
交替逐层扩展。由于两端扩展节点个数可能差别很大，所以每次选择节点个数少的队列进行扩展。
import java.util.*;
/**
* 八数码问题： 双向BFS 交替逐层扩展
*/
public class EightDigital_T2_TwoWayAlternateBFS{
private static final int N = 3;
private static String end = "12345678x";
private static int[] dx = {1, 0, -1, 0}, dy = {0, -1, 0, 1};
private static String[] move = {"D", "L", "U", "R"};
private static Map<String, String> path = new HashMap<>(); // 记录路径
private static Map<String, String> rpath = new HashMap<>(); // 记录路径
private static Map<String, Integer> dist = new HashMap<>(); // 记录距离
private static Map<String, Integer> rdist = new HashMap<>(); // 记录路径
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String start = sc.nextLine().replace(" ", "");
//System.out.println(start);
if(calcInversionPair(start) % 2 == 1){
System.out.println("-1");
return ;
}
bfs(start);
//System.out.println(path.get(end)); // 输出路径
//System.out.println(dist.get(end)); // 输出步数
sc.close();
}
private static void bfs(String start){
Queue<String> q = new LinkedList<>();
Queue<String> rq = new LinkedList<>(); //从目标状态开始的反向搜索队列
q.add(start); rq.add(end);
path.put(start, ""); rpath.put(end, "");
dist.put(start, 0); rdist.put(end, 0);
while(!q.isEmpty()){
boolean r;
if(q.size() < rq.size()){
// 优先遍历节点少的队列
// 0正向, 1反向
r = search(q, path, rpath, dist, rdist, 0);
}else{
r = search(rq, rpath, path, rdist, dist, 1);
}
if(r) break;
}
}
// 从队列中取出一个状态进行扩展
private static boolean search(
Queue<String> q,
Map<String, String> path,
Map<String, String> rpath,
Map<String, Integer> dist,
Map<String, Integer> rdist,
int order
){
String state = q.poll();
String curPath = path.get(state);
Integer curDist = dist.get(state);
// 找x的位置
int x = -1, y = -1;
for(int i = 0 ; i < N*N ; i ++){
if(state.charAt(i) == 'x'){
x = i / N;
y = i % N;
break;
}
}
for(int i = 0 ; i < 4 ; i ++){
int a = x + dx[i];
int b = y + dy[i];
if(a < 0 || b < 0 || a >= N || b >= N) continue;
String newState = generateState(state, x*N+y, a*N+b);
if(dist.get(newState) != null) continue;
if(order == 0){
// 正向
path.put(newState, curPath + move[i]);
}else{
// 逆向
path.put(newState, curPath + move[(i + 2) % 4]);
}
dist.put(newState, curDist + 1);
if(rdist.get(newState) != null){
if(order == 0){
// 正序
StringBuilder strbud = new StringBuilder(rpath.get(newState));
System.out.println(path.get(newState) + strbud.reverse().toString());
System.out.println(dist.get(newState) + rdist.get(newState));
}else{
// 逆序
StringBuilder strbud = new StringBuilder(path.get(newState));
System.out.println(rpath.get(newState) + strbud.reverse().toString());
System.out.println(dist.get(newState) + rdist.get(newState));
}
return true;
}
q.add(newState);
}
return false;
}
/**
* 字符串s中下标a, b交换位置， 并输出新串（不能改变原串）
*/
private static String generateState(String state, int i1, int i2){
char[] ch = state.toCharArray();
ch[i1] = state.charAt(i2);
ch[i2] = state.charAt(i1);
return new String(ch);
}
/**
* 逆序对的数量，对于 奇数*奇数 的数码问题来说，移动x不改变逆序对的奇偶性，因此
* 对于八数码而言，12345678x逆序对是0偶数，因此初始状态的逆序对只有为偶数时才有解
*/
private static int calcInversionPair(String s){
int num = 0;
for(int i = 0 ; i < N * N ; i ++){
for(int j = i + 1 ; j < N * N ; j ++){
if(s.charAt(i) == 'x' || s.charAt(j) == 'x')
continue;
if (s.charAt(j) > s.charAt(i))
num++;
}
}
return num;
}
}
0x03 优先队列BFS
分析
使用优先队列，每次扩展当前最小代价的节点
注意，这里实际上并没有真正优化。
使用优先队列优化BFS很常见，以Dijkstra算法为例，因为点与点距离权值的不同，每一层搜索完毕后，距初始点的距离都不太一样，因此可以使用优先队列找到最短距离的那个点进行扩展。但是对于八数码而言，每一层搜索完毕后，距离初始点的距离都一样，因为下一层距当前层的距离都是1。
代码改动（基于0x01 BFS）：
- 增加自定义类/结构体Pair
- 队列 → 优先队列（排序：按初始状态到当前状态的步数）
代码
import java.util.*;
/**
* 八数码问题： 堆优化BFS（实际上并没有优化）
*/
public class EightDigital_T3_PriorityQueueBFS{
private static final int N = 3;
private static String end = "12345678x";
private static int[] dx = {1, 0, -1, 0}, dy = {0, -1, 0, 1};
private static String[] move = {"D", "L", "U", "R"};
private static Map<String, String> path = new HashMap<>(); // 记录路径https://www.acwing.com/user/myspace/notification/1/
private static Map<String, Integer> dist = new HashMap<>(); // 记录距离
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String start = sc.nextLine().replace(" ", "");
//System.out.println(start);
if(calcInversionPair(start) % 2 == 1){
System.out.println("-1");
return ;
}
bfs(start);
System.out.println(path.get(end));
sc.close();
}
private static void bfs(String start){
Queue<Pair> q = new PriorityQueue<>();
q.add(new Pair(start, 0));
path.put(start, "");
dist.put(start, 0);
while(!q.isEmpty()){
Pair p = q.poll();
String state = p.state;
if(end.equals(state)){
// 结束
break;
}
String curPath = path.get(state);
Integer curDist = dist.get(state);
// 找x的位置
int x = -1, y = -1;
for(int i = 0 ; i < N*N ; i ++){
if(state.charAt(i) == 'x'){
x = i / N;
y = i % N;
break;
}
}
for(int i = 0 ; i < 4 ; i ++){
int a = x + dx[i];
int b = y + dy[i];
if(a < 0 || b < 0 || a >= N || b >= N) continue;
String newState = generateState(state, x*N+y, a*N+b);
if(dist.get(newState) != null) continue;
path.put(newState, curPath + move[i]);
dist.put(newState, curDist + 1);
q.add(new Pair(newState, curDist + 1));
}
}
}
/**
* 字符串s中下标a, b交换位置， 并输出新串（不能改变原串）
*/
private static String generateState(String state, int i1, int i2){
char[] ch = state.toCharArray();
ch[i1] = state.charAt(i2);
ch[i2] = state.charAt(i1);
return new String(ch);
}
/**
* 逆序对的数量，对于 奇数*奇数 的数码问题来说，移动x不改变逆序对的奇偶性，因此
* 对于八数码而言，12345678x逆序对是0偶数，因此状态只有为偶数时才有解
*/
private static int calcInversionPair(String s){
int num = 0;
for(int i = 0 ; i < N * N ; i ++){
for(int j = i + 1 ; j < N * N ; j ++){
if(s.charAt(i) == 'x' || s.charAt(j) == 'x')
continue;
if (s.charAt(j) > s.charAt(i))
num++;
}
}
return num;
}
static class Pair implements Comparable<Pair>{
String state;
Integer dist;
Pair(String state, Integer dist){
this.state = state;
this.dist = dist;
}
@Override
public int compareTo(Pair p){
return Integer.compare(this.dist, p.dist);
}
}
}0x04 A*
分析
本质：优先队列BFS + 估价函数
在优先队列中，每次取出的是已经计算的距离初始状态最近的状态（最优解），但这并不能保证在未来的计算中仍然是最近的状态，因此考虑每次取出的是当前的距离+ 未来的估计距离最近的状态。计算估计距离的函数即估价函数。
估价函数
经验得出，八数码问题的估价函数为：当前状态的每个点到目标状态的点的曼哈顿距离之和作为估计距离。
注意，估计距离不能大于真实距离。
代码改动（基于0x03 优先队列BFS）：
- 添加估价函数
f() - 自定义结构体里原来存放的是当前状态距初始状态的距离，改为：当前状态距初始状态的距离 + 当前状态距目标状态的估计距离。此时优先队列按此进行排序。
- $66$行添加
&& dist.get(newState) <= curDist + 1，估计距离和真实距离存在偏差，因此计算过的点，如果计算的值偏大的话需要再计算一遍。
代码
import java.util.*;
/**
* 八数码问题： A*
*/
public class EightDigital_T4_Astar{
private static final int N = 3;
private static String end = "12345678x";
private static int[] dx = {1, 0, -1, 0}, dy = {0, -1, 0, 1};
private static String[] move = {"D", "L", "U", "R"};
private static Map<String, String> path = new HashMap<>();
private static Map<String, Integer> dist = new HashMap<>();
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String start = sc.nextLine().replace(" ", "");
//System.out.println(start);
if(calcInversionPair(start) % 2 == 1){
System.out.println("-1");
return ;
}
bfs(start);
System.out.println(path.get(end));
sc.close();
}
// 估价函数， 每个点到目标点的曼哈顿距离之和
private static int f(String state){
int sum = 0;
for(int i = 0 ; i < N*N ; i ++){
char c = state.charAt(i);
if(c != 'x'){
int distIdx = c - '1';
// 横坐标距离 + 纵坐标距离
sum += Math.abs(distIdx / N - i / N) + Math.abs(distIdx % N - i % N);
}
}
return sum;
}
private static void bfs(String start){
Queue<Pair> q = new PriorityQueue<>();
q.add(new Pair(start, f(start)));
path.put(start, "");
dist.put(start, 0);
while(!q.isEmpty()){
Pair p = q.poll();
String state = p.state;
if(end.equals(state)){
// 结束
break;
}
String curPath = path.get(state);
Integer curDist = dist.get(state);
// 找x的位置
int x = -1, y = -1;
for(int i = 0 ; i < N*N ; i ++){
if(state.charAt(i) == 'x'){
x = i / N;
y = i % N;
break;
}
}
for(int i = 0 ; i < 4 ; i ++){
int a = x + dx[i];
int b = y + dy[i];
if(a < 0 || b < 0 || a >= N || b >= N) continue;
String newState = generateState(state, x*N+y, a*N+b);
if(dist.get(newState) != null && dist.get(newState) <= curDist + 1 ) continue;
path.put(newState, curPath + move[i]);
dist.put(newState, curDist + 1);
q.add(new Pair(newState, curDist + 1 + f(newState)));
}
}
}
/**
* 字符串s中下标a, b交换位置， 并输出新串（不能改变原串）
*/
private static String generateState(String state, int i1, int i2){
char[] ch = state.toCharArray();
ch[i1] = state.charAt(i2);
ch[i2] = state.charAt(i1);
return new String(ch);
}
/**
* 逆序对的数量，对于 奇数*奇数 的数码问题来说，移动x不改变逆序对的奇偶性，因此
* 对于八数码而言，12345678x逆序对是0偶数，因此状态只有为偶数时才有解
*/
private static int calcInversionPair(String s){
int num = 0;
for(int i = 0 ; i < N * N ; i ++){
for(int j = i + 1 ; j < N * N ; j ++){
if(s.charAt(i) == 'x' || s.charAt(j) == 'x')
continue;
if (s.charAt(j) > s.charAt(i))
num++;
}
}
return num;
}
static class Pair implements Comparable<Pair>{
String state;
Integer dist;
Pair(String state, Integer dist){
this.state = state;
this.dist = dist;
}
@Override
public int compareTo(Pair p){
return Integer.compare(this.dist, p.dist);
}
}
}0x05 迭代加深（ID-DFS）
分析
搜索树会因为深度不断增加，分支数呈指数级增长，导致规模过大，而实际答案的层次较浅。会导致在其他不必要的分支上花费过多时间。本质上是限制搜索的深度。
迭代加深的搜索深度从1开始逐层递增，当限制的最大深度搜完还是没搜到目标状态时就让深度限制加1然后重新搜索，这样就能保证当某一层搜到目标状态时，是最小步数。
需要注意，迭代加深唯一的不好之处在于，会重复计算很多遍低层的分支。但这个计算对于深度很高的指数级的分支来说几乎是可以忽略的。
代码
import java.util.*;
/**
* 八数码问题： ID-DFS
*/
public class EightDigital_T5_IDDFS{
private static final int N = 3;
private static String end = "12345678x";
private static int[] dx = {1, 0, -1, 0}, dy = {0, -1, 0, 1};
private static String[] move = {"D", "L", "U", "R"};
private static Map<String, String> path = new HashMap<>(); // 记录路径
private static Map<String, Integer> dist = new HashMap<>(); // 记录距离
private static int maxDep;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String start = sc.nextLine().replace(" ", "");
//System.out.println(start);
if(calcInversionPair(start) % 2 == 1){
System.out.println("-1");
return ;
}
dist.put(start, 0);
maxDep = 1;
while(!dfs(0, start)) {
path.clear();
path.put(start, "");
dist.clear();
dist.put(start, 0);
maxDep++;
}
System.out.println(path.get(end));
sc.close();
}
private static boolean dfs(int curDep, String state){
if(end.equals(state)){
// 结束
//System.out.println(curDep);
return true;
}
if(curDep >= maxDep) return false;
String curPath = path.get(state);
Integer curDist = dist.get(state);
// 找x的位置
int x = -1, y = -1;
for(int i = 0 ; i < N*N ; i ++){
if(state.charAt(i) == 'x'){
x = i / N;
y = i % N;
break;
}
}
// 扩展状态
for(int i = 0 ; i < 4 ; i ++){
int a = x + dx[i];
int b = y + dy[i];
if(a < 0 || b < 0 || a >= N || b >= N) continue;
String newState = generateState(state, x*N+y, a*N+b);
//if(dist.get(newState) != null) continue;
path.put(newState, curPath + move[i]);
dist.put(newState, curDist + 1);
if(dfs(curDep + 1, newState)){
return true;
}
}
return false;
}
/**
* 字符串s中下标a, b交换位置， 并输出新串（不能改变原串）
*/
private static String generateState(String state, int i1, int i2){
char[] ch = state.toCharArray();
ch[i1] = state.charAt(i2);
ch[i2] = state.charAt(i1);
return new String(ch);
}
/**
* 逆序对的数量，对于 奇数*奇数 的数码问题来说，移动x不改变逆序对的奇偶性，因此
* 对于八数码而言，12345678x逆序对是0偶数，因此状态只有为偶数时才有解
*/
private static int calcInversionPair(String s){
int num = 0;
for(int i = 0 ; i < N * N ; i ++){
for(int j = i + 1 ; j < N * N ; j ++){
if(s.charAt(i) == 'x' || s.charAt(j) == 'x')
continue;
if (s.charAt(j) > s.charAt(i))
num++;
}
}
return num;
}
}0x06 迭代加深A*（IDA*）
分析
迭代加深DFS结合A*算法。对搜索深度进行优化，使用当前深度 + 未来估计步数 > 深度限制 作为条件
估价函数
同 0x04 A* ，估计函数使用当前状态的每个点到目标状态的点的曼哈顿距离之和作为估计距离。
代码改动（基于0x05 迭代加深（ID-DFS））：
- 添加估价函数（直接复制 0x04 A* 里的
f()） - $39$行
if(curDep >= maxDep)改为if(curDep + f(state) >= maxDep)，即使用已计算的距离+未来估计距离。
代码
import java.util.*;
/**
* 八数码问题： IDA*
*/
public class EightDigital_T6_IDAstar{
private static final int N = 3;
private static String end = "12345678x";
private static int[] dx = {1, 0, -1, 0}, dy = {0, -1, 0, 1};
private static String[] move = {"D", "L", "U", "R"};
private static Map<String, String> path = new HashMap<>(); // 记录路径
private static Map<String, Integer> dist = new HashMap<>(); // 记录距离
private static int maxDep;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String start = sc.nextLine().replace(" ", "");
//System.out.println(start);
if(calcInversionPair(start) % 2 == 1){
System.out.println("-1");
return ;
}
dist.put(start, 0);
maxDep = 1;
while(!dfs(0, start)) {
path.clear();
path.put(start, "");
dist.clear();
dist.put(start, 0);
maxDep++;
}
System.out.println(path.get(end));
sc.close();
}
private static boolean dfs(int curDep, String state){
if(end.equals(state)){
// 结束
//System.out.println(curDep);
return true;
}
if(curDep + f(state) >= maxDep) return false;
String curPath = path.get(state);
Integer curDist = dist.get(state);
// 找x的位置
int x = -1, y = -1;
for(int i = 0 ; i < N*N ; i ++){
if(state.charAt(i) == 'x'){
x = i / N;
y = i % N;
break;
}
}
// 扩展状态
for(int i = 0 ; i < 4 ; i ++){
int a = x + dx[i];
int b = y + dy[i];
if(a < 0 || b < 0 || a >= N || b >= N) continue;
String newState = generateState(state, x*N+y, a*N+b);
//if(dist.get(newState) != null) continue;
path.put(newState, curPath + move[i]);
dist.put(newState, curDist + 1);
if(dfs(curDep + 1, newState)){
return true;
}
}
return false;
}
/**
* 字符串s中下标a, b交换位置， 并输出新串（不能改变原串）
*/
private static String generateState(String state, int i1, int i2){
char[] ch = state.toCharArray();
ch[i1] = state.charAt(i2);
ch[i2] = state.charAt(i1);
return new String(ch);
}
/**
* 逆序对的数量，对于 奇数*奇数 的数码问题来说，移动x不改变逆序对的奇偶性，因此
* 对于八数码而言，12345678x逆序对是0偶数，因此状态只有为偶数时才有解
*/
private static int calcInversionPair(String s){
int num = 0;
for(int i = 0 ; i < N * N ; i ++){
for(int j = i + 1 ; j < N * N ; j ++){
if(s.charAt(i) == 'x' || s.charAt(j) == 'x')
continue;
if (s.charAt(j) > s.charAt(i))
num++;
}
}
return num;
}
// 估价函数， 每个点到目标点的曼哈顿距离之和
private static int f(String state){
int sum = 0;
for(int i = 0 ; i < N*N ; i ++){
char c = state.charAt(i);
if(c != 'x'){
int distIdx = c - '1';
// 横坐标距离 + 纵坐标距离
sum += Math.abs(distIdx / N - i / N) + Math.abs(distIdx % N - i % N);
}
}
return sum;
}
}实战性能测试
测试
双向BFS、双向交替BFS、A*和IDA*性能。这里微改代码使用$4*4$棋盘数据测试。
| 字符串 | 步数 | 双向BFS | 双向交替BFS | A*时间 | IDA*时间 |
|---|---|---|---|---|---|
| 154278x36bac9edf | 29 | 210ms | 189ms | 781ms | >30s |
| 1234c9x7d85ba6fe | 31 | 439ms | 349ms | 5470ms | >30s |
| 273f56189a4xdebc | 31 | 567ms | 460ms | 2212ms | >30s |
| 72143df56cx8a9eb | 36 | 3454ms | 3061ms | 25710ms | >30s |
| 621478cbd5ef9x3a | 40 | 7704ms | 9756ms | 45502ms | >30s |
| 16f9527xd4b3ae8c | 40 | 17003ms | 22371ms | ||
| 1f3764b82dxea9c5 | 40 | 19716ms | 31038ms |
经测试，针对该问题而言，
双向BFS的性能很好，双向交替BFS稍弱，A*凑合，IDA*8太行（毕竟DFS）
- - - 结束 - - -