啟發(fā)式搜索實(shí)驗(yàn)

1、實(shí)驗(yàn)三 搜索推理技術(shù)啟發(fā)式搜索算法A*算法1實(shí)驗(yàn)?zāi)康模?）了解搜索推理的相關(guān)技術(shù)；（2）掌握啟發(fā)式搜索算法或者基于規(guī)則推理的分析方法。2實(shí)驗(yàn)內(nèi)容（2個(gè)實(shí)驗(yàn)內(nèi)容可以選擇1個(gè)實(shí)現(xiàn)）（1）啟發(fā)式搜索算法。熟悉和掌握啟發(fā)式搜索的定義、估價(jià)函數(shù)和算法過程，并求解博弈問題，理解求解流程和搜索順序；（2）產(chǎn)生式系統(tǒng)實(shí)驗(yàn)。熟悉和掌握產(chǎn)生式系統(tǒng)的運(yùn)行機(jī)制，掌握基于規(guī)則推理的基本方法。3實(shí)驗(yàn)報(bào)告要求（1）簡述實(shí)驗(yàn)原理及方法，并請(qǐng)給出程序設(shè)計(jì)流程圖。（A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的直接搜索方法。公式表示為： f(n)=g(n)+h(n),其中 f(n) 是從初始點(diǎn)經(jīng)由節(jié)點(diǎn)n到目標(biāo)點(diǎn)的估價(jià)函數(shù)，

2、g(n) 是在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價(jià)，h(n) 是從n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)。保證找到最短路徑（最優(yōu)解的）條件，關(guān)鍵在于估價(jià)函數(shù)h(n)的選?。汗纼r(jià)值h(n)<= n到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值，這種情況下，搜索的點(diǎn)數(shù)多，搜索范圍大，效率低。但能得到最優(yōu)解。并且如果h(n)=d(n)，即距離估計(jì)h(n)等于最短距離，那么搜索將嚴(yán)格沿著最短路徑進(jìn)行， 此時(shí)的搜索效率是最高的。然后我們通過圖文結(jié)合的形式來解釋下，如下圖：圖中有這么幾個(gè)要點(diǎn)先需要了解：1、類似迷宮圖，分開始節(jié)點(diǎn)(start)、障礙物、結(jié)束節(jié)點(diǎn)(end)，我們需要從start節(jié)點(diǎn)探尋一條到end節(jié)點(diǎn)的路線2、對(duì)于

3、探尋的每一步，都會(huì)以當(dāng)前節(jié)點(diǎn)為基點(diǎn)，掃描其相鄰的八個(gè)節(jié)點(diǎn) 3、計(jì)算當(dāng)前節(jié)點(diǎn)與start節(jié)點(diǎn)及到end的距離4、計(jì)算出最短路徑如果明白了上面的場景描述，下面就可以進(jìn)行分析了。在A*算法中，核心思想是一個(gè)公式，上面已經(jīng)提到過：f(n)=g(n)+h(n)（2）源程序清單：package com.itxxz.ui.suanfa.astar; import java.util.Iterator; import java.util.LinkedList; import java.util.Queue; import com.itxxz.ui.suanfa.astar.Point; public clas

4、s ItxxzAstar / 開始節(jié)點(diǎn) private Point startPoint = null; / 當(dāng)前節(jié)點(diǎn) private Point endPoint = null; / 結(jié)束節(jié)點(diǎn) private Point currentPoint = null; / 最短距離坐標(biāo)節(jié)點(diǎn) private Point shortestFPoint = null; / 迷宮數(shù)組地圖 private static final int mazeArray = 1, 0, 0, 0, 0 , 1, 0, 2, 0, 0 , 1, 0, 0, 0, 1 , 1, 0, 0, 0, 0 , 1, 1, 1,

5、1, 0 , 1, 0, 0, 0, 0 , 3, 0, 1, 1, 1 ; / 迷宮坐標(biāo)對(duì)象 private Point mazePoint = null; / 開啟隊(duì)列，用于存放待處理的節(jié)點(diǎn) Queue<Point> openQueue = null; / 關(guān)閉隊(duì)列，用于存放已經(jīng)處理過的節(jié)點(diǎn) Queue<Point> closedQueue = null; / 起始節(jié)點(diǎn)到某個(gè)節(jié)點(diǎn)的距離 int FList = null; / 某個(gè)節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離 int GList = null; / 起始節(jié)點(diǎn)經(jīng)過某個(gè)節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離 int HList = null; /

6、* * 構(gòu)造函數(shù) * * param maze * 迷宮圖 * param startPoint * 起始節(jié)點(diǎn) * param endPoint * 結(jié)束節(jié)點(diǎn) */ public ItxxzAstar(Point mazePoint, Point startPoint, Point endPoint) this.mazePoint = mazePoint; this.startPoint = startPoint; this.endPoint = endPoint; openQueue = new LinkedList<Point>(); openQueue.offer(start

7、Point); closedQueue = new LinkedList<Point>(); FList = new intmazePoint.lengthmazePoint0.length; GList = new intmazePoint.lengthmazePoint0.length; HList = new intmazePoint.lengthmazePoint0.length; for (int i = 0; i < mazePoint.length; i+) for (int j = 0; j < mazePoint0.length; j+) FListi

8、j = Integer.MAX_VALUE; GListij = Integer.MAX_VALUE; HListij = Integer.MAX_VALUE; / 起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的距離 GListstartPoint.getX()startPoint.getY() = 0; / 當(dāng)前節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離 HListstartPoint.getX()startPoint.getY() = getPointDistance( startPoint.getX(), startPoint.getY(), endPoint.getX(), endPoint.getY(); / f(x) = g(x

9、) + h(x) FListstartPoint.getX()startPoint.getY() = GListstartPoint.getX()startPoint .getY() + HListstartPoint.getX()startPoint.getY(); /* * 計(jì)算當(dāng)前坐標(biāo)與結(jié)束坐標(biāo)之間的距離 * * 計(jì)算方法為每向相信坐標(biāo)移動(dòng)一次算作一個(gè)距離單位 * */ private int getPointDistance(int current_x, int current_y, int end_x, int end_y) return Math.abs(current_x - e

10、nd_x) + Math.abs(current_y - end_y); /* * 數(shù)組迷宮地圖 * * 0、可通行 1、障礙 2、開始節(jié)點(diǎn) 3、結(jié)束節(jié)點(diǎn) * */ public static void main(String args) / 創(chuàng)建節(jié)點(diǎn)迷宮圖 Point mazePoint = new PointmazeArray.lengthmazeArray0.length; for (int i = 0; i < mazePoint.length; i+) for (int j = 0; j < mazePoint0.length; j+) mazePointij = new

11、 Point(i, j, mazeArrayij); Point start = mazePoint12; Point end = mazePoint60; ItxxzAstar star = new ItxxzAstar(mazePoint, start, end); star.start(); System.out.println(mazeArray.length + "," + mazeArray0.length); star.printPath(); /* * 開始迷宮搜索 * */ public void start() while (currentPoint =

12、 findShortestFPoint() != null) if (currentPoint.getX() = endPoint.getX() && currentPoint.getY() = endPoint.getY() return; updateNeighborPoints(currentPoint); /* * 獲取距離最短的坐標(biāo)點(diǎn) * */ public Point findShortestFPoint() currentPoint = null; shortestFPoint = null; int shortestFValue = Integer.MAX_VA

13、LUE; Iterator<Point> it = openQueue.iterator(); while (it.hasNext() currentPoint = it.next(); if (FListcurrentPoint.getX()currentPoint.getY() <= shortestFValue) shortestFPoint = currentPoint; shortestFValue = FListcurrentPoint.getX()currentPoint.getY(); if (shortestFValue != Integer.MAX_VAL

14、UE) System.out .println("【移除節(jié)點(diǎn)】:" + shortestFPoint.getValue() + "" + shortestFPoint.getX() + "," + shortestFPoint.getY() + ""); openQueue.remove(shortestFPoint); closedQueue.offer(shortestFPoint); return shortestFPoint; /* * 更新臨近節(jié)點(diǎn) */ private void updateNeighb

15、orPoints(Point currentPoint) int current_x = currentPoint.getX(); int current_y = currentPoint.getY(); System.out.println("當(dāng)前節(jié)點(diǎn)：" + current_x + "," + current_y + ""); / 上 if (checkPosValid(current_x - 1, current_y) System.out.print("上"); updatePoint(mazePointc

16、urrent_xcurrent_y, mazePointcurrent_x - 1current_y); / 下 if (checkPosValid(current_x + 1, current_y) System.out.print("下"); updatePoint(mazePointcurrent_xcurrent_y, mazePointcurrent_x + 1current_y); / 左 if (checkPosValid(current_x, current_y - 1) System.out.print("左"); updatePoin

17、t(mazePointcurrent_xcurrent_y, mazePointcurrent_xcurrent_y - 1); / 右 if (checkPosValid(current_x, current_y + 1) System.out.print("右"); updatePoint(mazePointcurrent_xcurrent_y, mazePointcurrent_xcurrent_y + 1); System.out.println("-"); /* * 檢查該節(jié)點(diǎn)是否有效 * */ private boolean checkPos

18、Valid(int x, int y) / 檢查x,y是否越界， 并且當(dāng)前節(jié)點(diǎn)不是墻 if (x >= 0 && x < mazePoint.length) && (y >= 0 && y < mazePoint0.length) && (mazePointxy.getValue() != 1) / 檢查當(dāng)前節(jié)點(diǎn)是否已在關(guān)閉隊(duì)列中，若存在，則返回 "false" Iterator<Point> it = closedQueue.iterator(); Point point

19、= null; while (it.hasNext() if (point = it.next() != null) if (point.getX() = x && point.getY() = y) return false; return true; return false; /* * 更新當(dāng)前節(jié)點(diǎn) */ private void updatePoint(Point lastPoint, Point currentPoint) int last_x = lastPoint.getX(); int last_y = lastPoint.getY(); int current

20、_x = currentPoint.getX(); int current_y = currentPoint.getY(); / 起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的距離 int temp_g = GListlast_xlast_y + 1; / 當(dāng)前節(jié)點(diǎn)到目的位置的距離 System.out.print(" " + current_x + "," + current_y + "" + mazePointcurrent_xcurrent_y.getValue(); int temp_h = getPointDistance(current_x, cu

21、rrent_y, endPoint.getX(), endPoint.getY(); System.out.println("到目的位置的距離 :" + temp_h); / f(x) = g(x) + h(x) int temp_f = temp_g + temp_h; System.out.println("f(x) = g(x) + h(x) :" + temp_f + "=" + temp_g + "+" + temp_h); / 如果當(dāng)前節(jié)點(diǎn)在開啟列表中不存在，則：置入開啟列表，并且“設(shè)置” / 1) 起

22、始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)距離 / 2) 當(dāng)前節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離 / 3) 起始節(jié)點(diǎn)到目的節(jié)點(diǎn)距離 if (!openQueue.contains(currentPoint) openQueue.offer(currentPoint); currentPoint.setFather(lastPoint); System.out.println("添加到開啟列表:" + currentPoint.getValue() + "" + currentPoint.getX() + "," + currentPoint.getY() + "&

23、quot;); / 起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的距離 GListcurrent_xcurrent_y = temp_g; / 當(dāng)前節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離 HListcurrent_xcurrent_y = temp_h; / f(x) = g(x) + h(x) FListcurrent_xcurrent_y = temp_f; else / 如果當(dāng)前節(jié)點(diǎn)在開啟列表中存在，并且， / 從起始節(jié)點(diǎn)、經(jīng)過上一節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)、至目的地的距離 < 上一次記錄的從起始節(jié)點(diǎn)、到當(dāng)前節(jié)點(diǎn)、至目的地的距離， / 則：“更新” / 1) 起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)距離 / 2) 當(dāng)前節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離 / 3) 起始節(jié)點(diǎn)

24、到目的節(jié)點(diǎn)距離 if (temp_f < FListcurrent_xcurrent_y) / 起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的距離 GListcurrent_xcurrent_y = temp_g; / 當(dāng)前節(jié)點(diǎn)到目的位置的距離 HListcurrent_xcurrent_y = temp_h; / f(x) = g(x) + h(x) FListcurrent_xcurrent_y = temp_f; / 更新當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn) currentPoint.setFather(lastPoint); System.out.println("currentPoint:" + cur

25、rentPoint.getValue() + "" + currentPoint.getX() + "," + currentPoint.getY() + ""); System.out.println("currentPoint.father:" + currentPoint.getFather().getValue() + "" + currentPoint.getFather().getX() + "," + currentPoint.getFather().getY(

26、) + ""); /* * 打印行走路徑 * */ public void printPath() System.out.println("= 開始打印行走路徑【用 8 表示】 ="); Point father_point = null; int result = new intmazeArray.lengthmazeArray0.length; for (int i = 0; i < mazeArray.length; i+) for (int j = 0; j < mazeArray0.length; j+) resultij = 0; int step = 0; father_point = mazePointendPoint.getX()endPoint.