路径导航与启发式搜索

问题介绍

介绍需要求解的问题

随着生活水平的不断发展，我们出行的需求越来越高，需要到达的目的地也越来越远，很多地方都是我们不熟悉的地方。在那些地方怎么才能从一个点到达另一个点？在这么多可能的路径中哪一条才是最短的？或者说，车流量最少的、速度最快的、花费时间最少的、途径收费项目最少的……

这样的问题，在现实生活中，我们成为路径导航问题，或者是寻路问题等。

模型的建立

现在把问题抽象成一个长、宽都是100的正方形，在这个正方形中依次排布了100×100的单位边长为1的小正方形，小正方形表示的是每个点。用2种不同的颜色表示每个点的含义：例如，黑色表示这是一个障碍物，不能通行；白色表示这个点是可以通行的道路。

不失一般性，上面的模型也适用于现实中的导航。100×100的正方形，可以类似地扩展成200×200、1000×800。同时，道路就用白色的点表示，建筑物是黑色的点，河流是黑色的点，但是河流上的桥梁是白色的点……

在这样一张地图上，给定一个起点，给定一个终点，需要找到一条从起点到终点的合法路径，并尽可能使得这条路是最短的。我们定义最短，意思是经过的步数最少，此时每经过一个小正方形，权重加1。

不失一般性，这样找到的路径在现实中也是有意义的。例如，在上面的求解中，每经过一个小正方形，权重加1，如果在现实生活中，我们想要找到一条花费时间最少的路（尽管这条路不是最短的），那么我们可以根据不同路口的车流量不同，对相应的小正方形赋予不同的权重；又例如，如果我们不想走高速，那么可以把高速路对应的小正方形的花销定义为无穷大……

为什么要采用我们介绍的方法求解

很容易想到的是，我们生活的世界如此庞大，“条条大路通罗马”，不可能枚举出所有的可能的路径，然后排个序，找到最短的。

甚至，就是对于上面抽象出的这个100×100的小正方形，其中存在的路径可能也太多了，即使在计算机的帮助下，枚举所有可能，然后找到最短路，这效率也非常低。

所以我们需要用到启发式算法、局部搜索算法。

启发式搜索是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的。

启发式搜索中，定义了一个评价函数对各个子结点进行计算，其目的就是用来估算出“有希望”的结点来。

要对OPEN表进行排序的时候，就按照这种“希望”进行排序。最有希望通向目标结点的待扩展结点会被优先扩展。

程序设计与算法分析

一般图搜索框架重塑

在这个问题中，采用的算法框架仍旧是一般图搜索框架，这在上一次作业《皇后问题》中已经给出了详细的算法说明和完整代码。

这里只简要重塑这个框架。

while (true) {
    if (open.isEmpty())
        return false;
    Node currentNode = open.poll();
    closed.add(currentNode);
    if (isTarget(currentNode)) {
        latest = currentNode;
        return true;
    }
    ArrayList<Node> m = expand(currentNode);
    if (m.isEmpty()) 
        continue;
    else 
        setPointer(m, currentNode);
}

需要修改的地方是设置父节点时候，要注意对OPEN表和CLOSED表的维护，其中对OPEN表排序需要按照启发式函数的评估值来排序。

由于每次都是评估值最小的排在最前面，所以其实可以在加入到OPEN表的时候就直接加入到恰当的位置，于是，OPEN表可以用优先级队列PriorityQueue来实现。

if (!open.contains(node) && !closed.contains(node)) {
    
} else if (open.contains(node)) {
    if (newDissipative < node.getDissipative()) {
        
    }
} else if (newDissipative < node.getDissipative()) {
    
}

数据存放形式与数据结构定义

• OPEN表：用于存放刚生成的节点

• CLOSED表：用于存放将要扩展或已扩展的节点

• Node：表示结点

• parent：指向父节点

数据域成员声明

• source：起点

• terminal：终点

• maze：地图，值为true表示可以通行，值为false表示这是障碍物

• result：最终找到的路径，以链表的形式返回

• progress：找路期间曾经试图访问过的点，以链表的形式返回

方法声明

/**
 * 评估函数的h(x)的值
 * @param source 起点
 * @param terminal 终点
 * @param parent 当前的点的父亲
 * @param node 当前的点
 * @return h(x)的值
 */
private double heuristic(Node source, Node terminal, Node parent, Node node) 

/**
 * 获得给定的点的邻居，邻居的定义是周围8个点
 * @param node 给定的点
 * @return 给定点的邻居
 */
private ArrayList<Node> getNeighbours(Node node) 

/**
 * 判断当前点是不是合法，合法的定义是不超过地图边界，且不是障碍物
 * @param x 横坐标
 * @param y 纵坐标
 * @return 如果合法，返回true，否则，false
 */
private boolean isValid(int x, int y) 

/**
 * 判断当前点是不是终点
 * @param node 当前点
 * @return 如果已经到了终点，返回true，否则，false
 */
private boolean isTarget(Node node) 

/**
 * 以链表的形式返回最终找到的路径
 * @return 最终找到的路径
 */
public LinkedList<Node> getResult() 

/**
 * 以链表的形式获得曾经试图访问过的点
 * @return 曾经试图访问过的点
 */
public LinkedList<Node> getProgress()

图形用户界面相关、交互相关

为了方便程序的调试，以及为了比较三种算法之间的优劣，我顺手写了图形用户界面。

因为这部分内容与本次作业的核心算法关系不大，所以下面不再详细给出这部分的数据定义、算法描述，只简要做出如下说明：

黑色：障碍，表示不能通过的地方

白色：道路，表示可以走的地方

红色：最终的路径

蓝色：曾经试图寻找的点，蓝色区域越大，说明搜索效率越低，找了那么多才找到这条路，蓝色区域越小说明搜索效率越高

算法

题目描述中有一些地方有歧义

为了更加清晰地表示下面的3种算法，做如下约定：

1．输入一定合法

不论是地图还是起点终点，输入的格式和数据一定合法，不存在非法数据或者错误格式。

2．下标从0开始

所描述的点，例如(5,4)表示的是第6行第5列。

3．8个方向是等价的

不存在“上、下、左、右”比“左上、左下、右上、右下”要优先的情况

4．走1步的花销定义为1

不论这一步是水平还是垂直走，还是斜着走，只要是走1步，花销就是1

从(0,0)走到(1,1)，是右下，这里花销不是，仍取1

5．从起点到终点的最优路线只看花销

只要花销是一样的，那么这几条路只是走法上的不同，在优劣程度上认为是一样

例如，下面2种走法，看作是等价的，区别只是走法的不同，而没有优劣之分，因为他们的花销都是5

起点	途径	途径	途径	途径	终点

****	途径	途径	****	****	****
起点	****	****	途径	途径	终点

最短路径算法

算法描述

首先看Dijkstra算法的描述：

这个算法是通过为每个顶点 v 保留目前为止所找到的从s到v的最短路径来工作的。初始时，原点 s 的路径权重被赋为 0 （d[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把d[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于所有顶点的集合 V 中的任意顶点 v， 若 v 不为 s 和上述 m 之一， d[v] = ∞）。当算法结束时，d[v] 中存储的便是从 s 到 v 的最短路径，或者如果路径不存在的话是无穷大。——该段引用自Wikipedia

那么就可以得到算法的主要思想。

首先从起点出发，试着往周围的8个点走，这时候这8个点都是1步就能到达的。之后，取这8个点的其中一个（因为这8个点距离起点都是1，所以都是最短的），继续找它的周围8个点，那么这些点的都是距离起点需要2步才能到达的。

每次都取待扩展的结点中，距离起点最短的结点往外扩展，这样搜索出来的路可以保证是最短路径。

在算法的实现过程中，如果一个点周围的8个点，有障碍物，或者已经超出了地图的边界，那么直接丢弃。

伪代码表示

于是，可以得到Dijkstra算法的伪代码描述。

对于图G中的每一个点V
初始化d[v] = Infinity，previous[v] = undefined   
d[s] = 0
S = empty
Q = 所有的V
while Q 非空
u = 取出(Q)中最小的点
把u加入到S
对于u能够走到的每一个v
if d[v] > d[u] + w(u,v)
d[v] = d[u] + w(u,v)，previous[v] = u

流程图

从这里可以看到，如果用一般图搜索框架来实现Dijkstra算法，用OPEN表存放所有的待扩展的结点，每次取出最小值，就是一个以当前“最短值”作为标准的优先级队列，而每次取出的u，相当于是更新父节点，并且维护OPEN表和CLOSED表。

image-20210328201448802 image-20210328201502641

那么对于一般图搜索框架，需要修改以下部分。

for (Node node : m) {
    double newDissipative = 计算出新的评估值;
    if (!open.contains(node) && !closed.contains(node)) {
        node.setDissipative(newDissipative);
        open.add(node);
        node.setParent(parent);
    } else if (open.contains(node)) {
        if (newDissipative < node.getDissipative()) {
            node.setDissipative(newDissipative);
            node.setParent(parent);
        }
    } else if (newDissipative < node.getDissipative()) {
        node.setDissipative(newDissipative);
        node.setParent(parent);
        closed.remove(node);
        open.add(node);
    }
}

在这里，新的评估值就是 parent.getDissipative()+1。

A*算法

算法描述

启发式搜索算法A，一般简称为A算法，是一种典型的启发式搜索算法。

其基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的结点来扩展。

评价函数的形式如下：

当

在算法的评价函数中，使用的启发函数是处在的下界范围，即满足时，则把这个算法称为算法。

算法实际上是分支界限和动态规划原理及使用下界范围的相结合的算法。

首先令就是最短路径算法中的评估值。也就是说，始终是距离起点的距离。

事实上，最短路径算法是极端情况下的算法，这时候，一定满足下界范围条件，所以一定能找到最佳路径（只要问题有解），这里的最佳路径指的是最短路径。

下面逐一考虑。

启发式函数的选取

标准启发式函数可以采用曼哈顿距离。

dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
h(n) = dx + dy

相邻方块之间的最低成本显然为1，这是因为我们可以朝着8个方向前进，从上文的约定中，可以发现，8个方向是等价的。

不失一般性，如果认为斜着走比横平竖直地走要花费更大的成本，那么对应的，只是相差一个常系数D，例如，这个为。在这里，为了简化问题，取。

更进一步，也可以使用对角线距离。

地图允许对角线移动，所以需要一个不同的启发式函数。

dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
h(n) = D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)

首先计算不能走对角线的时候需要走的距离，然后减去走对角线可以省下的距离。

当的时候，上面这个等式的值其实就是切比雪夫距离，而当且时，上面这个等式的值其实就是可视距离。

在我的算法中，我将会采用作为启发式函数，也就是可视距离。

多思考一步。

如果地图允许以任意角度移动，而不仅限于那8个方向，那么欧几里得距离也是可以作为启发式函数的。

dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
h(n) = D * sqrt(dx * dx + dy * dy)

但是，如果是这种情况，那么可能无法直接使用A*，因为g(n)与h(n)不匹配。由于欧几里德距离比曼哈顿或对角距离短，所以仍然会得到最短路径，但A*的运行时间会更长。

——该段引用自斯坦福大学GameProgramming - Heuristics

至此，我已经找到了启发式函数的计算方法。

但是在查阅相关文献的时候，我看到了进一步的优化方法，所以我认为有必要在这里提及一下斯坦福大学GameProgramming – Heuristics中提到的一个Breaking ties*的算法。

heuristic *= (1.0 + p)
p <(minimum cost of taking one step)/(expected maximum path length)

这略微打破了启发式的“可接受性”，但在游戏中它几乎从不重要。、

这种“破坏”的推动的结果是，A*探索的地图比以前少得多。

当然，如果有障碍，它仍然需要探索以找到解决方案，但，在障碍通过后，A *探索的很少。

image-20210328202154806

除了上面提到的方法，还可以用另一种方法来计算“Breaking Ties”。

dx1 = current.x - goal.x
dy1 = current.y - goal.y
dx2 = start.x - goal.x
dy2 = start.y - goal.y
cross = abs(dx1*dy2 - dx2*dy1)
heuristic += cross*0.001

但是考虑到这次作业的地图规模比较小，是100×100，而且事实上，我本地测试过斯坦福大学的这种“Breaking Ties”的优化，但是效果很不明显，并没有比最基本的A*算法快了多少（虽然确实少搜索了那么一些格子，但是数量差别不大），所以最终我没有采用这种优化方法。

伪代码表示

OPEN=(s)
f(s)=g(s)+h(s)
LOOP:
if OPEN为空 return FAIL
取出OPEN表的第一个元素n
if n是目标 return SUCCESS
从OPEN表移除n，加入到CLOSED表
扩展n为{m}
计算f(n,mi)=g(n,mi)+h(mi)
标记m到n的指针
mj加入到OPEN表
if f(n,mk)<f(mk) f(mk)=f(n,mk)
if f(n,ml)<f(ml) f(ml)=f(n,ml)并重新放回OPEN表
OPEN表按照f值从小到大排序（如果使用优先级队列自动完成，这一步省略）
GO LOOP

局部搜索

局部搜索算法是从爬山法改进而来。

局部搜索算法中最基本的思想，即在搜索过程中，始终向着离目标最接近的方向搜索。

局部搜索从一个初始解出发，然后搜索解的邻域，如有更优的解则移动至该解并继续执行搜索，否则返回当前解。局部搜索的优点是简单、灵活及易于实现，缺点是容易陷入局部最优且解的质量与初始解和邻域的结构密切相关。常见的改进方法有模拟退火、禁忌搜索等。

——该段引用自Wikipedia

下面从最简单的局部搜索来分析。

第1种方案，每次都取最小的走，这个算最基本的局部搜索。

第2种方案，也是只看，但是有一定的概率取差的，这个算是局部搜索的改进。

考虑一种极端情况，有一定概率取差的，这个概率无限趋于0，也就是只取比自己好的，不会取比自己查的，就回到了第1种方案。

第3种也是只看，但有一定概率取差的，而且这个概率会变。

模拟退火就属于这种方案。当温度较高的时候，接受劣解的概率比较大，在初始高温下，几乎以100%的概率接受劣解。随着温度的下降，接受劣解的概率逐渐减少，直到温度趋于0时，接受劣解的概率也同时趋于0。这样将有利于算法从局部最优解中跳出，求得问题的全局最优解。

在实际的代码过程中，我经过测试，发现对于100×100的规模的图，因为起点终点已经给定，所以直接使用第1种方案就已经得到了令人满意的结果。

相比之下，第2和第3种方案因为引入了随机的过程，计算量加大，且不可控性加大，对求解这类问题并没有显著性的改善（虽然在求解超大规模问题的时候能够提高效率），因此，最后我并没有采用任何优化的算法进行局部搜索，我只用了最原始的方案。

实验结果

程序运行说明

image-20210328202331121

gui包内的三个类都是处理图形用户界面的，与寻路部分的核心代码无关。

handler包内的ConstanValue是一些常量的定义，Darw类负责绘图，InputHandler负责交互用户的输入。

main包的代码是核心代码，Node是辅助类，用来记录每个点的信息，Main类是主程序部分。

程序运行的入口是navigator项目的main包的Main类的main()方法。

程序运行后会给出Prompt，只要按照提示依次输入，以回车结束就可以了。

image-20210328202345627

如果程序能够找到解，会在图形用户界面绘制这样一条路径。

GUI界面中，黑色代表障碍物，白色代表可以走的路，蓝色代表曾经试图搜索过的区域，红色代表最后的路径。

image-20210328202354705

如果不存在这样一条路径，程序会给出提示。

img

需要注意的是，地图文件名区分大小写，且需要与程序处于同一个工作目录，除非给定的是绝对路径，而不单纯是文件名。

- 请确保输入文件位于程序的工作目录

- 即Project目录，而非bin（Release、Debug）目录

- 除非修改过配置，那么服从配置文件的工作目录

- 请确保文件是UTF-8格式编码的

- 请确保文件具有读取权限

- 请确保文件名大小写正确

正确性验证

首先考虑极端的情况。

在一张完全空白的图上，即没有任何障碍物的时候，应该无论如何都能找到一条路径。

而且显然的是，这条路一定会尽可能朝着起点终点的连线走斜着过去，直到45°角走到横平竖直的时候，再直接过去。

image-20210328202513178 image-20210328202519149

再考虑具有障碍物的情况。

image-20210328202529097 image-20210328202534923

显然也是正确的，首先往目标的方向走，然后遇到障碍物了，就贴着障碍物走，绕过障碍物以后，直接往目标方向走。

注意一个细节。

image-20210328202543993

在这一部分，路径没有傻傻的直接朝着目标方向走，虽然继续往右是距离目标最近的。

但是继续往右，3步以后就会撞到障碍物，然后不得不继续向下，那么这时候就会多很多没用的步骤。

我的程序，在一直往右走到某个点以后，非常聪明地发现继续向右并不是最好的选择，而这个时候右下方可以有效地走到障碍物的边缘，然后继续。

同样的，绕过障碍物以后，也有类似的细节。

image-20210328202552721

这两个细节也同时说明了，启发式函数，我选的是很好的。

最后考虑一种无解的情况。

三种算法都能规避这种情况，正常判断出无解。

image-20210328202600358

一般情况，以老师发的测试数据的0.1.txt和0.55.txt，分别选取一个代表。

image-20210328202608480 image-20210328202613628 image-20210328202617843 image-20210328202621923

三种算法的比较

下面是不同的地图下，3中算法的路径图，可以发现，红色线条的路径找的都是一样的，关键的不同点在于蓝绿色部分的大小不一样，也就是搜索的空间（效率）有高低。

	最短路径算法	A*算法	局部搜索
empty	image-20210328202653596	image-20210328202659101	image-20210328202706779
block	image-20210328202711532	image-20210328202716408	image-20210328202722607
0.1	img	img	img
0.55	img	img	img

在empty图中，我是从(10,10)走到(30,30)，3种算法都是花费21步。

但是明显的是，A*算法比最短路径算法少了很多搜索范围，因为他尽可能往目标方向走。

而局部搜索甚至不考虑距离起点的距离，一昧的往终点走，它的搜索空间就是最终答案，一点都不浪费。

在block图中我是从(6,0)走到(24,60)，蓝绿色的区域大小区别更明显了。

最短路径算法几乎查完了整张图才能找到终点。

A*算法找的就明显少了很多，只有一小块区域。

而局部搜索甚至更高效，直接往目的地方向去，只在障碍物的边缘多找了那么一小圈。

一般情况下，也可以看出，最短路径的搜索效率是最差的。

即使面对如此多的障碍物，A*搜索的搜索区域也比最短路径少，而局部搜索就更少。

image-20210328202811833 image-20210328202815965

程序源代码

核心代码

package main;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;

import handler.ConstantValue;
import handler.Draw;
import handler.InputHandler;;

public class Main {

    public static void main(String[] args) throws Exception {
        // 处理输入
        InputHandler inputHandler = new InputHandler();
        inputHandler.input();
        boolean[][] maze = inputHandler.getMaze();
        Node source = inputHandler.getSource();
        Node terminal = inputHandler.getTerminal();
        // 开始搜索
        Search s = new Search(source, terminal, maze);
        if (s.start()) {
            // 找到结果，就获得结果，并绘制，然后输出
            LinkedList<Node> progress = s.getProgress();
            LinkedList<Node> result = s.getResult();
            Draw.draw(maze, progress, result);
            System.out.println("总共走了 " + result.size() + " 步。");
            System.out.println("找到路径，请查看图形用户界面。");
        } else {
            // 找不到结果，就是答案不存在
            // Draw.draw(maze, new LinkedList<Node>(), new LinkedList<Node>());
            System.out.println("不存在这样一条路径！");
        }

    }
}

class Search {

    private Node source; // 起点
    private Node terminal; // 终点
    private boolean[][] maze = new boolean[ConstantValue.SIZE][ConstantValue.SIZE]; // 迷宫

    public Search(Node source, Node terminal, boolean[][] maze) {
        this.source = source;
        this.terminal = terminal;
        this.maze = maze;
    }

    PriorityQueue<Node> open = new PriorityQueue<Node>(); // OPEN表
    LinkedList<Node> closed = new LinkedList<Node>(); // CLOSED表
    LinkedList<Node> progress = new LinkedList<Node>(); // 哪些区域是被搜索过的，用来比较算法优劣
    Node latest;

    public boolean start() {
        /*
         * 起点的权重定义为0 事实上，因为起点一定在路径中，所以无所谓它的g(x)和h(x)到底是什么，直接定义为0就好了
         * 
         */
        source.setDissipative(0);

        open.add(source);

        while (true) {
            if (open.isEmpty()) {
                return false;
            }
            Node currentNode = open.poll();
            progress.add(currentNode);
            closed.add(currentNode);
            if (isTarget(currentNode)) {
                latest = currentNode;
                return true;
            }
            ArrayList<Node> m = expand(currentNode);
            if (m.isEmpty()) {
                continue;
            } else {
                setPointer(m, currentNode);
            }
        }
    }

    private void setPointer(ArrayList<Node> m, Node parent) {
        for (Node node : m) {

            double newDissipative;

            /*
             * 三种算法的区别只是这里的评估值不一样
             */

            // // 最短路径算法
            // newDissipative = parent.getDissipative() + 1;

            // A*算法
            newDissipative = parent.getDissipative() + 1;
            newDissipative += heuristic(source, terminal, parent, node);

            // // 局部搜索算法
            // newDissipative = heuristic(source, terminal, parent, node);

            // 如果不在OPEN表，且不在CLOSED表，更新评估值，设置父结点，然后加入OPEN表
            if (!open.contains(node) && !closed.contains(node)) {
                node.setDissipative(newDissipative);
                open.add(node);
                node.setParent(parent);
            } else if (open.contains(node)) {
                // 如果在OPEN表中，且新的评估值小于旧的评估值，更新评估值，然后更新父结点
                if (newDissipative < node.getDissipative()) {
                    node.setDissipative(newDissipative);
                    node.setParent(parent);
                }
            } else if (newDissipative < node.getDissipative()) {
                // 不然就是在CLOSED表中，如果新的评估值小于旧的评估值，然后更新父结点，然后从CLOSED表中移除并加入OPEN表
                node.setDissipative(newDissipative);
                node.setParent(parent);
                closed.remove(node);
                open.add(node);
            }
        }
    }

    /**
     * 评估函数的h(x)的值
     * 
     * @param source
     *            起点
     * @param terminal
     *            终点
     * @param parent
     *            当前的点的父亲
     * @param node
     *            当前的点
     * @return h(x)的值
     */
    private double heuristic(Node source, Node terminal, Node parent, Node node) {
        return Math.abs(terminal.x - node.x) + Math.abs(terminal.y - node.y)
                + (Math.sqrt(2) - 2) * Math.min(Math.abs(terminal.x - node.x), Math.abs(terminal.y - node.y));
    }

    private ArrayList<Node> expand(Node node) {
        return getNeighbours(node);
    }

    /**
     * 获得给定的点的邻居，邻居的定义是周围8个点
     * 
     * @param node
     *            给定的点
     * @return 给定点的邻居
     */
    private ArrayList<Node> getNeighbours(Node node) {
        ArrayList<Node> m = new ArrayList<Node>();
        for (int i = -1; i <= 1; ++i) {
            for (int j = -1; j <= 1; ++j) {
                if (i == 0 && j == 0)
                    continue;
                int x = node.x + i;
                int y = node.y + j;

                if (isValid(x, y)) {
                    m.add(new Node(x, y));
                }
            }
        }
        return m;
    }

    /**
     * 判断当前点是不是合法，合法的定义是不超过地图边界，且不是障碍物
     * 
     * @param x
     *            横坐标
     * @param y
     *            纵坐标
     * @return 如果合法，返回true，否则，false
     */
    private boolean isValid(int x, int y) {
        if (x < 0 || x >= ConstantValue.SIZE || y < 0 || y >= ConstantValue.SIZE)
            return false;
        return (maze[x][y]);
    }

    /**
     * 判断当前点是不是终点
     * 
     * @param node
     *            当前点
     * @return 如果已经到了终点，返回true，否则，false
     */
    private boolean isTarget(Node node) {
        return (node.x == terminal.x && node.y == terminal.y);
    }

    /**
     * 以链表的形式返回最终找到的路径
     * 
     * @return 最终找到的路径
     */
    public LinkedList<Node> getResult() {
        LinkedList<Node> result = new LinkedList<Node>();
        Node node = latest;
        while (node != null) {
            result.addFirst(node);
            node = node.getParent();
        }
        return result;
    }

    /**
     * 以链表的形式获得曾经试图访问过的点
     * 
     * @return 曾经试图访问过的点
     */
    public LinkedList<Node> getProgress() {
        return progress;
    }
}

package main;

import java.awt.Point;

public class Node extends Point implements Comparable<Node> {

    private static final long serialVersionUID = 1L;

    private Node parent;
    private double dissipative;

    public double getDissipative() {
        return dissipative;
    }

    public void setDissipative(double dissipative) {
        this.dissipative = dissipative;
    }

    public Node getParent() {
        return parent;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

    public Node(int x, int y) {
        super(x, y);
        parent = null;
    }

    @Override
    public int compareTo(Node o) {
        if (dissipative < o.dissipative)
            return -1;
        else if (dissipative == o.dissipative)
            return 0;
        else
            return 1;
    }

}

图形用户界面与交互相关

package gui;

public class Field {
    private int width;
    private int height;
    private Road[][] field;
    
    public Field(int width, int height) {
        this.width = width;
        this.height = height;
        field = new Road[height][width];
    }
    
    public int getWidth() { return width; }
    public int getHeight() { return height; }
    
    public Road replace(int row, int col, Road newRoad) {
        Road ret = field[row][col];
        field[row][col] = newRoad;
        return ret;
    }
    
    public Road get(int row, int col) {
        return field[row][col];
    }
    
    public void clear() {
        for ( int i=0; i<height; i++ ) {
            for ( int j=0; j<width; j++ ) {
                field[i][j] = null;
            }
        }
    }
}

package gui;

import java.awt.Color;
import java.awt.Graphics;
 
public class Road {
    
    
    private Color color;
    
    public Road(Color color) {
        this.color = color;
    }

    public void draw(Graphics g, int x, int y, int size) {
        g.setColor(color);
        g.drawRect(x, y, size, size);
        g.fillRect(x, y, size, size);
    }
}

package gui;

import java.awt.Dimension;
import java.awt.Graphics;

import javax.swing.JPanel;

import handler.ConstantValue;

public class View extends JPanel {

    private static final long serialVersionUID = 1L;
    
    private Field theField;
    
    public View(Field field) {
        theField = field;
    }

    @Override
    public void paint(Graphics g) {
        super.paint(g);
        for ( int row = 0; row<theField.getHeight(); row++ ) {
            for ( int col = 0; col<theField.getWidth(); col++ ) {
                Road road = theField.get(row, col);
                if ( road != null ) {
                    road.draw(g, col*ConstantValue.GRID_SIZE, row*ConstantValue.GRID_SIZE, ConstantValue.GRID_SIZE);
                }
            }
        }
    }

    @Override
    public Dimension getPreferredSize() {
        return new Dimension(theField.getWidth()*ConstantValue.GRID_SIZE+1, theField.getHeight()*ConstantValue.GRID_SIZE+1);
    }

}

package handler;

import java.awt.Color;

public class ConstantValue {
    public static final int SIZE = 100;
    public static final int GRID_SIZE = 500 / SIZE;
    public static final Color COLOR_FOR_PROGRESS = new Color(0x3C, 0xF5, 0xEB);
    public static final Color COLOR_FOR_RESULT = Color.RED;
    public static final Color COLOR_FOR_BLOCK = Color.BLACK;
    public static final Color COLOR_FOR_PASSABLE_AREA = Color.WHITE;
    public static final String GUI_TITLE = "路径导航 by 张臻炜";

    private ConstantValue() {

    }

}

package handler;

import java.awt.Color;
import java.util.LinkedList;

import javax.swing.JFrame;

import gui.Field;
import gui.Road;
import gui.View;
import main.Node;

public class Draw {

    public static void draw(boolean[][] maze, LinkedList<Node> progress, LinkedList<Node> result) {
        Field field = new Field(ConstantValue.SIZE, ConstantValue.SIZE);
        for (int row = 0; row < field.getHeight(); row++) {
            for (int col = 0; col < field.getWidth(); col++) {
                Color c;
                if (maze[row][col] == true) {
                    c = ConstantValue.COLOR_FOR_PASSABLE_AREA;
                } else {
                    c = ConstantValue.COLOR_FOR_BLOCK;
                }
                field.replace(row, col, new Road(c));
            }
        }

        for (Node node : progress) {
            Color c = ConstantValue.COLOR_FOR_PROGRESS;
            field.replace(node.x, node.y, new Road(c));
        }

        for (Node node : result) {
            Color c = ConstantValue.COLOR_FOR_RESULT;
            field.replace(node.x, node.y, new Road(c));
        }

        View view = new View(field);
        JFrame frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setResizable(false);
        frame.setTitle(ConstantValue.GUI_TITLE);
        frame.add(view);
        frame.pack();
        frame.setVisible(true);

    }

}

package handler;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

import main.Node;

public class InputHandler {
    String fileName;
    Node source;
    Node terminal;

    public void input() {
        Scanner in = new Scanner(System.in);
        System.out.println("请输入地图的文件名：");
        fileName = in.nextLine();
        System.out.println("请输入起点的横纵坐标，以一个空格分隔，以回车结束：");
        source = new Node(in.nextInt(), in.nextInt());
        System.out.println("请输入终点的横纵坐标，以一个空格分隔，以回车结束：");
        terminal = new Node(in.nextInt(), in.nextInt());
        in.close();
    }

    public String getFileName() throws Exception {
        if (fileName == null) {
            throw new Exception("请先输入文件名");
        } else {
            return fileName;
        }

    }

    public Node getSource() throws Exception {
        if (source == null) {
            throw new Exception("请先输入起点！");
        } else {
            return source;
        }

    }

    public Node getTerminal() throws Exception {
        if (terminal == null) {
            throw new Exception("请先输入终点！");
        } else {
            return terminal;
        }

    }

    public boolean[][] getMaze() throws FileNotFoundException {
        Scanner in = new Scanner(new File(fileName));
        boolean[][] maze = new boolean[ConstantValue.SIZE][ConstantValue.SIZE];
        for (int i = 0; i < ConstantValue.SIZE; ++i) {
            String s = in.nextLine();
            for (int j = 0; j < ConstantValue.SIZE; ++j) {
                maze[i][j] = (s.charAt(j) == '0');
            }
        }
        in.close();
        return maze;
    }

}