做电商网站商标,大于二高端网站建设,自己做的视频可以同时上传到几家网站,建设公司网站需要多少天最短路径算法#xff1a; A*算法擅长解决静态路径中最短距离问题#xff0c;而又不同于Dijkstra算法和Floyd算法#xff0c;该算法综合了BFS和Dijkstra算法优点#xff1a;在进行启发式搜索提高算法效率的同时#xff0c;可以保证找到一条最优路径(基于评估函数#xff0…最短路径算法 A*算法擅长解决静态路径中最短距离问题而又不同于Dijkstra算法和Floyd算法该算法综合了BFS和Dijkstra算法优点在进行启发式搜索提高算法效率的同时可以保证找到一条最优路径(基于评估函数例如曼哈顿距离、欧式距离)Floyd算法更多地使用场景在于机器人路径规划、游戏规划、卫星路径探寻等领域。
A*算法与最短路径计算
对于地理环境中的一个固定地面位置它至少可以被标记为两种状态跟可使用区、不可使用区(障碍区)同时可以把该固定位置视为九宫格里面的中心点。
可以确定该中心点的移动方向包含8个上下左右左上、右上、左下、右下因此A*算法的寻路流程可以通过三个步骤完成。
1.从中心点开始把它放入一个待计算的开放列表开放列表可以理解成一个准备进行路径分析的队列。
2.寻找中心点周围可达到的方格集这些方格的状态需要是可以使用的将这些方格的来源都标记为中心点。
3.在开放列表中移除刚刚分析的中心点将该中心点放入关闭列表中关闭列表表示后续不再对该表进行可达路径分析。
通过3步已经完成了开放列表的获取但是如何从开放列表中选择下一步的移动方格是A*算法思想中最核心的内容。A*算法利用公式f(n)g(n)h(n)筛选下一步移动方格其中g(n)代表从起初开始的方格移动当当前方格的移动距离h(n)表示从即将移动到的方格到终点方格的距离两者相加得到f(n)即为当前预估的可能路径这种可能路径中最小的值对应的方格即为当前可以从开放列表中选择的下一步移动方格选择该方格之后再依次重复上述步骤知道邻近的方格中存在终点方格(或终点方格进入了开放列表)‘
上述步骤中g(n)和h(n)是获取A*计算计算的关键值
1.g(n)的计算
g(n)定义的是起点方格到当前方格的距离从方格不同位置移动多产生的距离在实际应用中每个方向的距离都有可能不同g(n)则是从起点方格开始通过不断的方位移动累计的距离和。
2.h(n)的计算
h(n)是对当前方格到目的地方格距离的估算估算方法
常见的距离计算公式有这么几种
1、曼哈顿距离这个名字听起来好高端说白了就是上面我们讲的横向格子数纵向格子数
2、欧式距离这个名字听起来也很高端说白了就是两点间的直线距离sqrt((x1-x2)2 (y1-y2)2)
算法源码
Main.java:
package com.simplemain.astar;public class Main
{// 地图元素static final char START S; // 起点static final char END E; // 终点static final char SPACE .; // 空地static final char WALL W; // 墙static final char VISITED -; // 被访问过static final char ON_PATH ; // 在结果路径上// 地图字符串static final String[] S_MAP {. . . . . . . . . . . . . . . . . . . ., . . . W W W W . . . . . . . . . . . . .,. . . . . . W . . . . . . . . . . . . ., . . . . . . W . . . . . . . . . . . . ., . . S . . . W . . . . . . . . . . . . ., . . . . . . W . . . . . . . . . . . . ., . . . . . . W . . . . . . . . . . . . ., . . . . . . W . . . . . . . . . . . . ., . . . W W W W . . . . . . . . . . . . ., . . . . . . . . . . . . . . . . . E . .};// 地图static char[][] MAP new char[S_MAP[0].replace( , ).length()][S_MAP.length];// 地图最大尺寸static Point MAX_PNT new Point(MAP.length, MAP[0].length);// 起点static Point START_PNT null;// 终点static Point END_PNT null;public static void main(String[] args){genMap();printMap();search();printMap();}/*** 用地图字符串产生地图数据*/static void genMap(){int idx 0;for (String s : S_MAP){char[] cs s.replace( , ).toCharArray();for (int i 0; i cs.length; i){MAP[i][idx] cs[i];switch (cs[i]){case START:START_PNT new Point(i, idx);break;case END:END_PNT new Point(i, idx);break;}}idx;}}/*** 打印地图*/static void printMap(){for (int j 0; j MAX_PNT.y; j){for (int i 0; i MAX_PNT.x; i){System.out.printf(%c , MAP[i][j]);}System.out.printf(\n);}System.out.printf(\n);}/*** 搜索算法*/static void search(){final MinHeap heap new MinHeap(); // 用最小堆来记录扩展的点final int[][] directs {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 可以扩展的四个方向heap.add(new Data(START_PNT, 0, 0, null)); // 把起始点放入堆Data lastData null; // 找到的最后一个点的数据,用来反推路径for (boolean finish false; !finish !heap.isEmpty(); ){final Data data heap.getAndRemoveMin(); // 取出f值最小的点final Point point data.point;if (MAP[point.x][point.y] SPACE) // 将取出的点标识为已访问点{MAP[point.x][point.y] VISITED;}for (int[] d : directs) // 遍历四个方向的点{final Point newPnt new Point(point.x d[0], point.y d[1]);if (newPnt.x 0 newPnt.x MAX_PNT.x newPnt.y 0 newPnt.y MAX_PNT.y){char e MAP[newPnt.x][newPnt.y];if (e END) // 如果是终点,则跳出循环,不用再找{lastData data;finish true;break;}if (e ! SPACE) // 如果不是空地,就不需要再扩展{continue;}final Data inQueueData heap.find(newPnt);if (inQueueData ! null) // 如果在堆里,则更新g值{if (inQueueData.g data.g 1){inQueueData.g data.g 1;inQueueData.parent data;}}else // 如果不在堆里,则放入堆中{double h h(newPnt);Data newData new Data(newPnt, data.g 1, h, data);heap.add(newData);}}}}// 反向找出路径for (Data pathData lastData; pathData ! null; ) {Point pnt pathData.point;if (MAP[pnt.x][pnt.y] VISITED){MAP[pnt.x][pnt.y] ON_PATH;}pathData pathData.parent;}}/*** h函数*/static double h(Point pnt){
// return hBFS(pnt);return hEuclidianDistance(pnt);
// return hPowEuclidianDistance(pnt);
// return hManhattanDistance(pnt);}/*** 曼哈顿距离,小于等于实际值*/static double hManhattanDistance(Point pnt){return Math.abs(pnt.x - END_PNT.x) Math.abs(pnt.y - END_PNT.y);}/*** 欧式距离,小于等于实际值*/static double hEuclidianDistance(Point pnt){return Math.sqrt(Math.pow(pnt.x - END_PNT.x, 2) Math.pow(pnt.y - END_PNT.y, 2));}/*** 欧式距离平方,大于等于实际值*/static double hPowEuclidianDistance(Point pnt){return Math.pow(pnt.x - END_PNT.x, 2) Math.pow(pnt.y - END_PNT.y, 2);}/*** BFS的h值,恒为0*/static double hBFS(Point pnt){return 0;}}MinHeap.java:
package com.simplemain.astar;import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;public class MinHeap
{private final ArrayListData queue new ArrayList();private int endPnt 0;private final MapString, Data index new HashMap();public Data getAndRemoveMin(){if (isEmpty()){return null;}Data head queue.get(0);Data last queue.get(endPnt - 1);queue.set(0, last);endPnt--;index.remove(getKey(head.point));topDown();return head;}public Data find(Point pnt){return index.get(getKey(pnt));}public void add(Data data){if (queue.size() endPnt){queue.set(endPnt, data);}else{queue.add(data);}endPnt;index.put(getKey(data.point), data);bottomUp();}public boolean isEmpty(){return endPnt 0;}private String getKey(Point pnt){return String.format(%d-%d, pnt.x, pnt.y);}private void topDown(){for (int cur 0; cur endPnt; ){int left 2 * cur 1;int right 2 * cur 2;Data dc queue.get(cur);Data dl left endPnt ? queue.get(left) : null;Data dr right endPnt ? queue.get(right) : null;int next -1;Data dn dc;if (dl ! null dl.f() dn.f()){next left;dn dl;}if (dr ! null dr.f() dn.f()){next right;dn dr;}if (next 0 next endPnt){queue.set(next, dc);queue.set(cur, dn);cur next;}else{break;}}}private void bottomUp(){for (int cur endPnt - 1; cur 0; ){int parent (cur - 1) / 2;if (parent 0){break;}Data dc queue.get(cur);Data dp queue.get(parent);if (dc.f() dp.f()){queue.set(parent, dc);queue.set(cur, dp);cur parent;}else{break;}}}
}Point.java:
package com.simplemain.astar;public class Point
{int x, y;Point(int x, int y){this.x x;this.y y;}public boolean equals(Object o){return o ! null o instanceof Point ((Point)o).x x ((Point)o).y y;}
}
Data.java:
package com.simplemain.astar;public class Data
{Point point;double g;double h;Data parent;public Data(Point p, double g, double h, Data parent){this.point p;this.g g;this.h h;this.parent parent;}double f(){return g h;}
}gitHub代码https://github.com/simplemain/astar
代码出自https://blog.csdn.net/qq_41325698/article/details/81874529
