python版:
由启发函数,状态移动处理,A*搜索并返回路径构成:
代码为:
class Astar:# A*搜索并返回距离def salvePuzzle(self, init, targ):# 传入初始状态init,目标状态targ，返回移动路径（string形式）open = [(init, self.calcDistH(init, targ))]# open表元素(状态，f值)closed = {}dict_depth = {init: 0}# 深度表，用来记录节点是否被访问过及对应的深度dict_link = {}# 关系字典，用来记录父子关系，孩子-->父亲dict_dirs = {'u': [-1, 0], 'd': [1, 0], 'l': [0, -1], 'r': [0, 1]}# 移动方向，对应二维坐标的变化dirs = ['l', 'r', 'u', 'd']path = []# 用来记录移动路径while (len(open)):open.sort(key=lambda open: open[1])# 每循环一次对列表按由小到大排序一次while (open[0][0] in closed):open.pop([0])# 如果表头元素在closed表中，移出open表if (open[0][0] == targ):print("Successfully!")breaktop = open[0]open[0:1] = []closed[top[0]] = top[1]# 取表头元素，并将表头元素移出open表，压入closed表cur_index = top[0].index('0')for i in range(4):x = cur_index // 3 + dict_dirs[dirs[i]][0]y = cur_index % 3 + dict_dirs[dirs[i]][1]if (x >= 0 and x < 3 and y >= 0 and y < 3):next_index = x * 3 + ynext_state = self.moveMap(top[0], cur_index, next_index)depth = dict_depth[top[0]] + 1# 当前节点不在深度表中，压入深度表和open表，并建立父子关系if ((next_state in dict_depth) == False):dict_depth[next_state] = depthopen.append((next_state, depth + self.calcDistH(next_state, targ)))dict_link[next_state] = top[0]else:# 当前节点在深度表中且当前深度小于深度表中的值，更新深度表，建立父子关系if (depth < dict_depth[next_state]):dict_depth[next_state] = depthdict_link[next_state] = top[0]# 如果当前节点在closed表中，将其移出closed表，将更新后的节点移入open表if (next_state in closed):del closed[next_state]open.append(next_state, depth +self.calcDistH(next_state, targ))# 循环结束，路径关系全部在dict_link中，从目标状态出发寻找路径s = targwhile (s != init):move = s.index('0') - dict_link[s].index('0')if (move == -1):path.append('l')elif (move == 1):path.append('r')elif (move == -3):path.append('u')else:path.append('d')s = dict_link[s]path.reverse()# 将path逆序(如果想要打印出路径每一步的状态，只需要按照path和init就能实现)print("SearchPath->", "".join(path))return "".join(path)# 启发函数(曼哈顿距离)def calcDistH(self, src_map, dest_map):# 采用曼哈顿距离作为估值函数cost = 0for i in range(len(src_map)):if (src_map[i] != '0'):cost += abs(int(src_map[i]) // 3 - i // 3) + \abs(int(src_map[i]) % 3 - i % 3)return cost# 转int然后整除# 状态移动处理def moveMap(self, cur_map, i, j):cur_state = [cur_map[i] for i in range(9)]cur_state[i] = cur_state[j]cur_state[j] = '0'return "".join(cur_state)# 本程序实现了Astar类，可通过创建Astar对象来调用相关方法
# 以下仅为测试用例
test = Astar()
test.salvePuzzle("724506831", "012345678")
Java版与课本步骤相似,具体看注释:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;public class EightNum implements Comparable {int[] number = new int[9];int f;//估计函数int d;//实际代价，走到当前状态的步数int h;//估计代价，当前状态和目标状态有多少个数不同EightNum parent;//记录当前状态的父状态ArrayList<EightNum> result = new ArrayList<>();//保存最终路径//目标状态的可达性判断，通过判断两个状态的逆序数是否相同来判断//注意：需要排除0public boolean isSolvable(EightNum target) {int num = 0;for (int i = 1; i < 9; i++) {for (int j = 0; j < i; j++) {if (number[j] > number[i] && number[j] != 0 && number[i] != 0)num++;if (target.number[j] > target.number[i] && target.number[j] != 0 && number[i] != 0)num++;}}//如果能被2整除，说明同奇或者同偶return num % 2 == 0;}//对状态进行初始化，计算估价函数public void init(EightNum target) {int h = 0;for (int i = 0; i < 9; i++) {if (number[i] != target.number[i])h++;//记录当前状态和目标状态的差距}this.h = h;if (this.parent == null)this.d = 0;elsethis.d = this.parent.d + 1;//实际代价this.f = this.d + this.h;//返回当前状态的估计值}public boolean isTarget(EightNum target) {//判断当前状态是否是目标状态return Arrays.equals(number, target.number);}//重写compareTo@Overridepublic int compareTo(Object o) {EightNum e = (EightNum) o;return this.f - e.f;}//获取0的位置public int getZeroPosition() {int position = -1;for (int i = 0; i < 9; i++) {if (this.number[i] == 0) {position = i;}}return position;}//判断该状态是否在表中，如果在。就返回位置public int isContains(ArrayList<EightNum> arrayList) {for (int i = 0; i < arrayList.size(); i++) {if (Arrays.equals(arrayList.get(i).number, number))return i;}return -1;}//判断能否上移public boolean isMoveUp() {int position = getZeroPosition();return position > 2;}//判断能否下移public boolean isMoveDown() {int position = getZeroPosition();return position < 6;}//判断能否左移public boolean isMoveLeft() {int position = getZeroPosition();return (position) % 3 != 0;}//判断能否右移public boolean isMoveRight() {int position = getZeroPosition();return (position) % 3 != 2;}//实现移动public EightNum moveUp(int move) {EightNum newState = new EightNum();//创建一个对象newState.number = number.clone();//将当前状态赋值给新创建的对象int zero = getZeroPosition();//记录0的位置int position = 0;//记录移动后的位置switch (move) {case 0://上移position = zero - 3;break;case 1://下移position = zero + 3;break;case 2://左移position = zero - 1;break;case 3://右移position = zero + 1;break;}newState.number[zero] = number[position];newState.number[position] = 0;return newState;}//输出单个状态public void output() {for (int i = 0; i < 9; i++) {if (i % 3 == 2)System.out.println(this.number[i]);elseSystem.out.print(this.number[i] + " ");}}//输出路径public void printRoute() {EightNum temp;int count = -1;temp = this;System.out.println("----开始移动----");//路径用链表的方式存放，所以是逆序的//所以把他放到result表中，方便输出while (temp != null) {result.add(temp);temp = temp.parent;count++;}for (int i = result.size() - 1; i >= 0; i--) {System.out.println("第"+ (count-i) +"步:");result.get(i).output();}System.out.println("最小移动步数:" + count);}public void operation(ArrayList<EightNum> open, ArrayList<EightNum> close, EightNum minF, EightNum target) {if (this.isContains(close) == -1) {//判断是否在close表int position = this.isContains(open);//判断是否在open表，存在就返回其在open表中的位置if (position == -1) {//不在open表中this.parent = minF;//链接，设置minF为该子状态的父状态this.init(target);//计算估计函数open.add(this);//放入open表}else {//在open表中if (this.d < open.get(position).d) {//根据移动步数，小的覆盖大的open.remove(position);this.parent = minF;this.init(target);open.add(this);}}}}public static void main(String[] args) {//open表存放已经生成而未考察的节点ArrayList<EightNum> open = new ArrayList<>();//close表存放已经访问过的节点ArrayList<EightNum> close = new ArrayList<>();EightNum start = new EightNum();//存放初始状态EightNum target = new EightNum();//存放目标状态int[] sNum = {2,1,3,8,0,4,6,7,5};//初始状态int[] tNum = {1,2,3,8,0,4,7,6,5};//目标状态start.number = sNum;target.number = tNum;System.out.println("初始状态：");start.output();System.out.println("目标状态：");target.output();if(start.isSolvable(target)){//判断从初始状态到目标状态是否可达start.init(target);//初始化，计算估价函数open.add(start);//加入open表while(!open.isEmpty()){//判断open表是否为空Collections.sort(open);//根据F值对open表进行从小到大排序EightNum minF = open.get(0);//取出最小的，也就是第0个open.remove(0);//从open表移出close.add(minF);//放入close表if(minF.isTarget(target)){//判断是否为目标状态minF.printRoute();//输出完整路径break;}int move;//由minF状态进行扩展并加入到open表//0的位置上移之后的状态不在close和open中设定minF为父状态，并初始化f的估值函数if(minF.isMoveUp()){move = 0;EightNum up = minF.moveUp(move);up.operation(open,close,minF,target);}//0的位置下移之后状态不在close和open中设定minF为其父状态，并初始化f(n)估值函数if (minF.isMoveDown()) {move = 1;EightNum down = minF.moveUp(move);down.operation(open, close, minF, target);}//0的位置左移之后状态不在close和open中设定minF为其父状态，并初始化f(n)估值函数if (minF.isMoveLeft()) {move = 2;EightNum left = minF.moveUp(move);left.operation(open, close, minF, target);}//0的位置右移之后状态不在close和open中设定minF为其父状态，并初始化f(n)估值函数if (minF.isMoveRight()) {move = 3;EightNum right = minF.moveUp(move);right.operation(open, close, minF, target);}}}elseSystem.out.println("目标状态不可达");}
}