- 浏览: 54571 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (43)
- Java(JVM_JDK_JRE) (16)
- JMail_JBPM_JNI_Maven (1)
- Ajax_JS_JQuery_JQuery UI_ExtJS_正则 (8)
- Flex_ActionScript (0)
- C#_Asp.NET_Silverlight (0)
- SQL/MySQL/Oracle/SQLServer (1)
- WebLogic_Tomcat_JBoss (0)
- Lucene_JUnit_Dom4j_Log4J (2)
- JPA_Hibernate_iBatis (2)
- Android (0)
- HTTP_WebService_FTP (0)
- SaaS_SOA (0)
- JMeter (0)
- erlang (0)
- Spring_Spring security_Spring MVC (4)
- 生活 (2)
- 设计模式_UML (0)
- Linux (4)
- 面试 (1)
- 黑 (1)
- 杂项。。。 (0)
最新评论
-
masterHU:
/**
* 自定义异常类
* @author hK ...
IE标题兰被黑,注册表被锁 -
masterHU:
:lol:
IE标题兰被黑,注册表被锁 -
masterHU:
引用[u][/u]
IE标题兰被黑,注册表被锁 -
masterHU:
引用[img][/img][url][/url][flash= ...
IE标题兰被黑,注册表被锁 -
davencool:
我在redhat5.4下能安装,但是运行后出错了。不知道原因。 ...
Linux 飞鸽。。。。
据我个人所知,目前流行的寻径方法大体有两种,即A* 和Dijkstra(SP算法)
Dijkstra算法:
由Edsger Wybe Dijkstra先生发明(已故)
Dijkstra算法是典型的最短路算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。Dijkstra算法是一种逐步搜索算法,通过为每个顶点n保留目前为止所找到的从m到n的最短路径来工作的。
搜索过程:
假如在第m步搜索到一个最短路径,而该路径上有n个距离源节点最近的节点,则将他们认为是一个节点集合N;在第m+1步,搜索不属于N的距离源节点最近的节点,并搜索到的节点加入到N中;继续搜索,直至到达目的节点,N中的节点集合便是从源节点到目的节点的最短路径。
算法描述:
Dijkstra算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时,源点s的路径长度值被赋为0(d[s]=0), 同时把所有其他顶点的路径长度设为无穷大,即表示我们不知道任何通向这些顶点的路径(对于V中所有顶点v除s外d[v]= ∞)。当算法结束时,d[v]中储存的便是从s到v的最短路径,或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展:如果存在一条从u到v的边,那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径的长度是d+w(u,v)。如果这个值比目前已知的d[v]的值要小,我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d达到它最终的值的时候没条边(u,v)都只被拓展一次。算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点,而集合Q则保留其他所有顶点。集合S 初始状态为空,而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d值的顶点。当一个顶点u从Q中转移到了S中,算法对每条外接边(u,v)进行拓展。
A*(A Star)算法:
A*(A-Star)算法是一种静态路网中求解最短路最有效的方法。
公式表示为:f(n)=g(n)+h(n), 其中f(n) 是节点n从初始点到目标点的估价函数,g(n) 是在状态空间中从初始节点到n节点的实际代价,h(n)是从n到目标节点最佳路径的估计代价。
搜索过程:
创建两个表,OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。遍历当前节点的各个节点,将n节点放入CLOSE中,取n节点的子节点X,->算X的估价值.
While(OPEN!=NULL)
{
从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点) break;
else
{
if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于OPEN表的估价值 )
更新OPEN表中的估价值; //取最小路径的估价值
if(X in CLOSE) 比较两个X的估价值 //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于CLOSE表的估价值 )
更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值
if(X not in both)
求X的估价值;
并将X插入OPEN表中; //还没有排序
}
将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小,从最小路径的节点向下进行。
}
就实际应用而言,A*算法和Dijistra算法的最大区别就在于有无估价值,本质上Dijistra算法相当于A*算法中估价值为0的情况。所以此次我选取A*算法进行Java实现。
抛开理论性的数学概念,通常的A*算法,其实只有两个步骤,一是路径评估,以保证移动的下一个位置离目标最近,评估的结果越精确则寻径的效率也将越高。二是路径查询,也即将评估结果进行反应,而后从新位置再次进行评估指导无路可走为止,以此遍历出可行的路径。
在A*算法的程序实现中,本质上我们只需要关心三点,即起点、终点和地图信息,有了这三项基本数据,我们就可以构建任何情况下的A*实现。
下面我现在提供的是一个A*的Java静态寻径算法实现,逻辑见代码注释。
运行效果如下图(1,1 to 10,13):
(1,1 to 7,9 小房子门口中间)
(1,1 to 6,7 小房子内部)
Dijkstra算法:
由Edsger Wybe Dijkstra先生发明(已故)
Dijkstra算法是典型的最短路算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。Dijkstra算法是一种逐步搜索算法,通过为每个顶点n保留目前为止所找到的从m到n的最短路径来工作的。
搜索过程:
假如在第m步搜索到一个最短路径,而该路径上有n个距离源节点最近的节点,则将他们认为是一个节点集合N;在第m+1步,搜索不属于N的距离源节点最近的节点,并搜索到的节点加入到N中;继续搜索,直至到达目的节点,N中的节点集合便是从源节点到目的节点的最短路径。
算法描述:
Dijkstra算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时,源点s的路径长度值被赋为0(d[s]=0), 同时把所有其他顶点的路径长度设为无穷大,即表示我们不知道任何通向这些顶点的路径(对于V中所有顶点v除s外d[v]= ∞)。当算法结束时,d[v]中储存的便是从s到v的最短路径,或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展:如果存在一条从u到v的边,那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径的长度是d+w(u,v)。如果这个值比目前已知的d[v]的值要小,我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d达到它最终的值的时候没条边(u,v)都只被拓展一次。算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点,而集合Q则保留其他所有顶点。集合S 初始状态为空,而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d值的顶点。当一个顶点u从Q中转移到了S中,算法对每条外接边(u,v)进行拓展。
A*(A Star)算法:
A*(A-Star)算法是一种静态路网中求解最短路最有效的方法。
公式表示为:f(n)=g(n)+h(n), 其中f(n) 是节点n从初始点到目标点的估价函数,g(n) 是在状态空间中从初始节点到n节点的实际代价,h(n)是从n到目标节点最佳路径的估计代价。
搜索过程:
创建两个表,OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。遍历当前节点的各个节点,将n节点放入CLOSE中,取n节点的子节点X,->算X的估价值.
While(OPEN!=NULL)
{
从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点) break;
else
{
if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于OPEN表的估价值 )
更新OPEN表中的估价值; //取最小路径的估价值
if(X in CLOSE) 比较两个X的估价值 //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于CLOSE表的估价值 )
更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值
if(X not in both)
求X的估价值;
并将X插入OPEN表中; //还没有排序
}
将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小,从最小路径的节点向下进行。
}
就实际应用而言,A*算法和Dijistra算法的最大区别就在于有无估价值,本质上Dijistra算法相当于A*算法中估价值为0的情况。所以此次我选取A*算法进行Java实现。
抛开理论性的数学概念,通常的A*算法,其实只有两个步骤,一是路径评估,以保证移动的下一个位置离目标最近,评估的结果越精确则寻径的效率也将越高。二是路径查询,也即将评估结果进行反应,而后从新位置再次进行评估指导无路可走为止,以此遍历出可行的路径。
在A*算法的程序实现中,本质上我们只需要关心三点,即起点、终点和地图信息,有了这三项基本数据,我们就可以构建任何情况下的A*实现。
下面我现在提供的是一个A*的Java静态寻径算法实现,逻辑见代码注释。
运行效果如下图(1,1 to 10,13):
(1,1 to 7,9 小房子门口中间)
(1,1 to 6,7 小房子内部)
Node.java package test.star; import java.awt.Point; import java.util.LinkedList; /** */ /** * <p> * Title: LoonFramework * </p> * <p> * Description:描述路径节点用类 * </p> * <p> * Copyright: Copyright (c) 2008 * </p> * <p> * Company: LoonFramework * </p> * <p> * License: http://www.apache.org/licenses/LICENSE-2.0 * </p> * * @author chenpeng * @email:ceponline@yahoo.com.cn * @version 0.1 */ public class Node implements Comparable { // 坐标 public Point _pos; // 开始地点数值 public int _costFromStart; // 目标地点数值 public int _costToObject; // 父节点 public Node _parentNode; private Node() { } /** */ /** * 以注入坐标点方式初始化Node * * @param _pos */ public Node(Point _pos) { this._pos = _pos; } /** */ /** * 返回路径成本 * * @param node * @return */ public int getCost(Node node) { // 获得坐标点间差值 公式:(x1, y1)-(x2, y2) int m = node._pos.x - _pos.x; int n = node._pos.y - _pos.y; // 取两节点间欧几理德距离(直线距离)做为估价值,用以获得成本 return (int) Math.sqrt(m * m + n * n); } /** */ /** * 检查node对象是否和验证对象一致 */ public boolean equals(Object node) { // 验证坐标为判断依据 if (_pos.x == ((Node) node)._pos.x && _pos.y == ((Node) node)._pos.y) { return true; } return false; } /** */ /** * 比较两点以获得最小成本对象 */ public int compareTo(Object node) { int a1 = _costFromStart + _costToObject; int a2 = ((Node) node)._costFromStart + ((Node) node)._costToObject; if (a1 < a2) { return -1; } else if (a1 == a2) { return 0; } else { return 1; } } /** */ /** * 获得上下左右各点间移动限制区域 * * @return */ public LinkedList getLimit() { LinkedList limit = new LinkedList(); int x = _pos.x; int y = _pos.y; // 上下左右各点间移动区域(对于斜视地图,可以开启注释的偏移部分,此时将评估8个方位) // 上 limit.add(new Node(new Point(x, y - 1))); // 右上 // limit.add(new Node(new Point(x+1, y-1))); // 右 limit.add(new Node(new Point(x + 1, y))); // 右下 // limit.add(new Node(new Point(x+1, y+1))); // 下 limit.add(new Node(new Point(x, y + 1))); // 左下 // limit.add(new Node(new Point(x-1, y+1))); // 左 limit.add(new Node(new Point(x - 1, y))); // 左上 // limit.add(new Node(new Point(x-1, y-1))); return limit; } }PathFinder.java package test.star; import java.awt.Point; import java.util.LinkedList; import java.util.List; /** */ /** * <p> * Title: LoonFramework * </p> * <p> * Description:A*寻径处理用类(此类为演示用,并不意味着算法是最佳实现) * </p> * <p> * Copyright: Copyright (c) 2008 * </p> * <p> * Company: LoonFramework * </p> * <p> * License: http://www.apache.org/licenses/LICENSE-2.0 * </p> * * @author chenpeng * @email:ceponline@yahoo.com.cn * @version 0.1 */ public class PathFinder { // 路径优先等级list(此示例中为内部方法) private LevelList _levelList; // 已完成路径的list private LinkedList _closedList; // 地图描述 private int[][] _map; // 行走区域限制 private int[] _limit; /** */ /** * 以注入地图的2维数组及限制点描述初始化此类 * * @param _map */ public PathFinder(int[][] map, int[] limit) { _map = map; _limit = limit; _levelList = new LevelList(); _closedList = new LinkedList(); } /** */ /** * A*方式寻径,注入开始坐标及目标坐标后运算,返回可行路径的List * * @param startPos * @param objectPos * @return */ public List searchPath(Point startPos, Point objectPos) { // 初始化起始节点与目标节点 Node startNode = new Node(startPos); Node objectNode = new Node(objectPos); // 设定起始节点参数 startNode._costFromStart = 0; startNode._costToObject = startNode.getCost(objectNode); startNode._parentNode = null; // 加入运算等级序列 _levelList.add(startNode); // 当运算等级序列中存在数据时,循环处理寻径,直到levelList为空 while (!_levelList.isEmpty()) { // 取出并删除最初的元素 Node firstNode = (Node) _levelList.removeFirst(); // 判定是否和目标node坐标相等 if (firstNode.equals(objectNode)) { // 是的话即可构建出整个行走路线图,运算完毕 return makePath(firstNode); } else { // 否则 // 加入已验证List _closedList.add(firstNode); // 获得firstNode的移动区域 LinkedList _limit = firstNode.getLimit(); // 遍历 for (int i = 0; i < _limit.size(); i++) { // 获得相邻节点 Node neighborNode = (Node) _limit.get(i); // 获得是否满足等级条件 boolean isOpen = _levelList.contains(neighborNode); // 获得是否已行走 boolean isClosed = _closedList.contains(neighborNode); // 判断是否无法通行 boolean isHit = isHit(neighborNode._pos.x, neighborNode._pos.y); // 当三则判定皆非时 if (!isOpen && !isClosed && !isHit) { // 设定costFromStart neighborNode._costFromStart = firstNode._costFromStart + 1; // 设定costToObject neighborNode._costToObject = neighborNode.getCost(objectNode); // 改变neighborNode父节点 neighborNode._parentNode = firstNode; // 加入level _levelList.add(neighborNode); } } } } // 清空数据 _levelList.clear(); _closedList.clear(); // 当while无法运行时,将返回null return null; } /** */ /** * 判定是否为可通行区域 * * @param x * @param y * @return */ private boolean isHit(int x, int y) { for (int i = 0; i < _limit.length; i++) { if (_map[y][x] == _limit[i]) { return true; } } return false; } /** */ /** * 通过Node制造行走路径 * * @param node * @return */ private LinkedList makePath(Node node) { LinkedList path = new LinkedList(); // 当上级节点存在时 while (node._parentNode != null) { // 在第一个元素处添加 path.addFirst(node); // 将node赋值为parent node node = node._parentNode; } // 在第一个元素处添加 path.addFirst(node); return path; } private class LevelList extends LinkedList { /** */ /** * */ private static final long serialVersionUID = 1L; /** */ /** * 增加一个node * * @param node */ public void add(Node node) { for (int i = 0; i < size(); i++) { if (node.compareTo(get(i)) <= 0) { add(i, node); return; } } addLast(node); } } }TestMap.java package test.star; import java.awt.Graphics; import java.awt.Image; import java.io.File; import java.io.IOException; /** */ /** * <p> * Title: LoonFramework * </p> * <p> * Description:一个简单的地图实现 * </p> * <p> * Copyright: Copyright (c) 2008 * </p> * <p> * Company: LoonFramework * </p> * <p> * License: http://www.apache.org/licenses/LICENSE-2.0 * </p> * * @author chenpeng * @email:ceponline@yahoo.com.cn * @version 0.1 */ public class TestMap { final static private int CS = 32; // 地图描述 final static public int[][] MAP = { { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } }; // 无法移动区域 final static public int[] HIT = { 1 }; // 设定背景方格默认行数 final static private int ROW = 15; // 设定背景方格默认列数 final static private int COL = 15; private Image floorImage; private Image wallImage; public TestMap() { try { floorImage = javax.imageio.ImageIO.read(new File("floor.gif")); wallImage = javax.imageio.ImageIO.read(new File("wall.gif")); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } } public void draw(Graphics g) { for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { switch (MAP[i][j]) { case 0: g.drawImage(floorImage, j * CS, i * CS, null); break; case 1: g.drawImage(wallImage, j * CS, i * CS, null); break; } } } } }Main.java package test.star; import java.awt.Color; import java.awt.Frame; import java.awt.Graphics; import java.awt.Image; import java.awt.Panel; import java.awt.Point; import java.awt.event.WindowAdapter; import java.awt.event.WindowEvent; import java.awt.image.BufferedImage; import java.util.List; /** */ /** * <p> * Title: LoonFramework * </p> * <p> * Description:Java的A*寻径实现 * </p> * <p> * Copyright: Copyright (c) 2008 * </p> * <p> * Company: LoonFramework * </p> * <p> * License: http://www.apache.org/licenses/LICENSE-2.0 * </p> * * @author chenpeng * @email:ceponline@yahoo.com.cn * @version 0.1 */ public class Main extends Panel { /** */ /** * */ final static private long serialVersionUID = 1L; final static private int WIDTH = 480; final static private int HEIGHT = 480; final static private int CS = 32; private TestMap map; private PathFinder astar; // 起始坐标1,1 private static Point START_POS = new Point(1, 1); // 目的坐标10,13 private static Point OBJECT_POS = new Point(8, 6); private Image screen; private Graphics graphics; private List path; public Main() { setSize(WIDTH, HEIGHT); setFocusable(true); screen = new BufferedImage(WIDTH, HEIGHT, BufferedImage.TYPE_INT_RGB); graphics = screen.getGraphics(); map = new TestMap(); // 注入地图描述及障碍物描述 astar = new PathFinder(TestMap.MAP, TestMap.HIT); // searchPath将获得两点间移动路径坐标的List集合 // 在实际应用中,利用Thread分步处理List中坐标即可实现自动行走 path = astar.searchPath(START_POS, OBJECT_POS); } public void update(Graphics g) { paint(g); } public void paint(Graphics g) { // 绘制地图 map.draw(graphics); graphics.setColor(Color.RED); graphics.fillRect(START_POS.x * CS, START_POS.y * CS, CS, CS); graphics.setColor(Color.BLUE); graphics.fillRect(OBJECT_POS.x * CS, OBJECT_POS.y * CS, CS, CS); // 绘制路径 if (path != null) { graphics.setColor(Color.YELLOW); // 遍历坐标,并一一描绘 for (int i = 0; i < path.size(); i++) { Node node = (Node) path.get(i); Point pos = node._pos; // 描绘边框 graphics.fillRect(pos.x * CS + 7, pos.y * CS + 7, CS - 14, CS - 14); } } g.drawImage(screen, 0, 0, this); } public static void main(String[] args) { Frame frame = new Frame(); frame.setTitle("Java的A*寻径实现"); frame.setSize(WIDTH, HEIGHT + 20); frame.setResizable(false); frame.setLocationRelativeTo(null); frame.add(new Main()); frame.setVisible(true); frame.addWindowListener(new WindowAdapter() { public void windowClosing(WindowEvent e) { System.exit(0); } }); } }
发表评论
-
beanshell简介
2011-01-04 17:49 1210我们知道,现在有很多脚本语言,大家平时使用的比较多的包括Per ... -
Eclipse编辑XML自动提示
2010-08-26 11:12 1199IED Eclipse Java EE IDE for Web ... -
JAVA对象怎样实现对一个方法的调用的?
2010-07-18 14:00 757举个例子: public class E ... -
Java中native方法学习
2010-07-18 00:05 944Java不是完美的,Java的不足除了体现在运行速度上要比传统 ... -
正则表达式(根据Tag查询Html内容)
2010-06-24 17:08 1480使用正则表达式查询一段Html中的Title标签,包括内容!! ... -
类集框架的完整结构
2010-06-23 22:32 1001类集框架的几大接口:Collection,Map,Iterat ... -
java jvm 参数 -Xms -Xmx -Xmn -Xss 调优总结
2010-06-22 08:09 1030常见配置举例 堆大小设置 JVM 中最大堆大小有三方面限制: ... -
System.gc()
2010-06-19 22:18 1492int length = 3; Set<Sky&g ... -
各种语言禁止缓存的方法
2010-06-18 17:53 588HTML: <META HTTP-EQUIV=&q ... -
linux配置java环境变量(详细)
2010-06-18 17:50 709现在用linux的朋友越来 ... -
浅谈Java 7的闭包与Lambda表达式之优劣
2010-06-18 13:52 1123前几天Oracle推出了Java 7官方的闭包与Lambda表 ... -
Java注释(Annotation)
2010-06-18 10:25 888Java5中提供了新的注释(Annotation),能够为类提 ... -
session机制详解
2010-06-12 19:47 674虽然session机制在web应用程序中被采用已经很长时间了, ... -
JVM概述
2010-06-12 19:41 715定义 Java Virtual Machi ... -
web.xml详解
2010-06-12 19:38 572部署描述符实际上是一个XML文件,包含了很多描述servlet ...
相关推荐
利用JAVA语言编程实现的经典A*算法,复制到eclipse即可运行
本设计以VC++6.0作为程序开发环境,C语言作为程序开发语言,详细介绍了最短路径的求解算法及其C语言实现过程。系统主要实现了图的创建、单源点最短路径的计算功能。依照本系统可以解决实际生活中许多路径选择问题,...
在有障碍的环境下,机器人通过A*算法能够规划出最短路径。
图论算法 最短路径 最小生成树 连通性 支配集 A*算法 a-star
静态路径最短路径算法是外界环境不变,计算最短路径。主要有Dijkstra算法,A*(A Star)算法。 动态路径最短路是外界环境不断发生变化,即不能计算预测的情况下计算最短路。如在 游戏中敌人或障碍物不断移动的...
A*算法 A star 算法(matlab)版本,可以直接使用,包含路径优化。直接下载即可运行。A*算法 A star 算法(matlab)版本,可以直接使用,包含路径优化。直接下载即可运行。
A*(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法,也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近,最终搜索速度越快。 本实例主要针对自动驾驶技术当中A*算法的应用现象,...
AStar(A*)最短路径探寻的VB.NET(2010)示例代码,带注释
【路径规划】基于A_star算法机器人避障最短路径规划附matlab代码.zip
NULL 博文链接:https://wuzijingaip.iteye.com/blog/855124
代码下载:完整代码,可直接运行 ;运行版本:2014a或2019b;若运行有问题,可私信博主;...海神之光擅长领域擅长路径规划、优化求解、神经网络预测、图像处理、语音处理等多种领域Matlab仿真,具体代码仿真 私信博主。
地杰斯特拉的贪婪思想的A-star算法计算出来最短路径,车辆路径长短和车辆速度两个维度进行了分批调度出发时间,matlab源码
A*算法,A*(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法,也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近,最终搜索速度越快。该资源是用WinForm实现的,可以更直接明了的...
A*算法,A*(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法,也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近,最终搜索速度越快。代码使用c#语言实现,欢迎下载
A star算法 + 随机迷宫 + matlab
这是用D*算法实现机器人路径规划的JAVA程序,适用于动态路径环境下,可以在未知环境中快速的找到可行路线
A-STAR 寻找一种静态路网(本算法中为二维数组)中求解最短路径的解决办法 我们可以通过: var element = new Element(); 来创建二维数组的一个节点。 element自身包含了一些方法: element.setStatus(2);//设置...
A*算法(A-star algorithm)是一种广泛应用的路径规划算法,被设计用来在图形或网络中寻找两个节点之间的最短路径。它是一种启发式搜索算法,结合了广度优先搜索和最佳优先搜索的特点。其核心思想是通过评估每个可能...
以前做的一个关于城市之间最短路径的算法演示。演示如何基于城市之间的权重查找两个城市之间的最短路线。这是图的规划问题。基于A星算法演示。
“A*(A-Star)算法,一种静态路网中求解最短路径最有效的直接搜索方法。Matlab的实现