3 A Star算法分析(A Star algorithm analysis)
A Star算法最初来源于DFS与BFS两种搜索策略,将各种不同的搜索问题抽象为搜索树的形式,为其后进行的优化打下基础。A Star算法作为启发式算法中重要的一种,被广泛应用在最优路径求解和一些策略设计的问题上。A Star算法的核心部分,是其中一个估值函数f(n)=g(n)+h(n)的设计。A Star算法的核心是每次选取下一个当前搜索点时,是从全部已探知的但未搜索过的点中,选取f值最小的结点进行展开。而所有“已探知的但未搜索过点”可以通过一个按f值升序的队列(即优先队列)进行排列。这样,在整体的搜索过程中,只要按照类似广度优先的算法框架,从优先队列中弹出队首元素(f值),对其可能子结点计算g、h和f值,直到优先队列为空(无解)或找到终止点为止[3]。A Star算法与BFS和DFS的关联在于,当g(n)=0时,类似于DFS,当h(n)=0时,类似于BFS。
4 软件程序类设计(Software program class design)
系统主要包含UML整体图、Main类、Map2D类、MapOperator类、MapTemp类、PathFinder类、TileAssemble类、TileObjectAbstract类等。在Main类里,通过构建run线程,控制程序界面的显示,加入键盘监听,用来显示菜单以及各类结点的显现。利用Map2D类初始化程序界面,设定界面的宽和高,并且规定了模拟中各节点的大小。使用MapOperator类设定宽度值、长度值以及地点、终点和障碍物的坐标,绘出界面背景以及路径。MapTemp类作为地图类,作用为初始化地图、障碍物等。PathFinder类为算法的核心类,用于构建OpenList与CloseList,增加寻找邻居节点方法、寻找周围最合适节点方法以及构建路径结构方法。TileAssemble继承TileObjectAbstract类,并构建了Start类、Empty类、Block类、Goal类、Path类,可以在面板上画出不同类型节点。TileObjectAbstract类作为一个抽象类,用来判断路径中所寻找的节点是否为障碍物,并且使用displayMyself方法绘出各种元素。
5 系统实现(System implementation)
为了使模拟软件更加易用,直接采用提示面板的方式,用空格键控制菜单的显示与消失。菜单内容上做到了简洁明了。
部分核心代码如下:
public class PathFinder {
private LinkedList m_openList;
private LinkedList m_closedList;
public PathFinder(){
this.m_openList = new LinkedList();
this.m_closedList = new LinkedList(); }
public LinkedList findPath(Map2D map) throws NullPointerException, ClassNotFoundException{
this.m_openList.clear();
this.m_closedList.clear();
Point start = new
Point(map.getTile(TileAssemble.Start.class.getName()));
Point goal = new Point(map.getTile(TileAssemble.Goal.class.getName()));
……
6 系统测试(System test)
(1)普通路径测试。对于普通路径的测试,模拟软件正常的给出了所对应的模拟路线,未出现意料之外的状况发生。由此,对于普通路径的寻找与测试,符合预期,故本模拟软件在实际使用中,可以对于日常大多数普通路径进行模拟,并且都能够给出较为便捷、直观的预测路径。
(2)狭长形陷阱测试。为了充分测试现实中可能出现的路况问题,防止车辆在配送过程中陷入狭长形陷阱,此处模拟线路,可以通过预判以及计算路径花费,正确的避开狭长形陷阱,符合预期。
(3)圆弧形陷阱测试。测试圆弧形陷阱,模拟软件仍能够避开陷阱,而选取较优线路,符合预期。
参考文献(References)
[1] CayS.Horstmann.Java核心技术[M].北京:电子工业出版社,
2011.
[2] 王庆等.电子商务环境下物流配送路径优化研究[J].天津商业
大学学报,2010,(03):27-30.
[3] 周春辉,李诗高.Dijkstra算法与A*算法研究[J].软件导刊,2007,
(1):102-103.
相关专题:江苏警官学院学报 江苏警官学院 江西警察学院学报 湖北警官学院学报 北京警察学院学报 云南警官学院学报 湖南警察学院学报 四川警察学院学报 甘肃政法学院学报 江苏警官学院分数线 经济地理 幼儿园教师发表文章