算法之A星算法（寻路）
2024-08-21 06:39:27
1.启发式搜索：启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
2.估价算法：从当前节点移动到目标节点的预估损耗。
预估算法有：曼哈顿（manhattan）等。
3.算法特点：理论上时间是最优的，但空间增长是指数型的。
4.java实现：上下左右移动
package cn.liushaofeng.algorithm; import java.util.ArrayList;
import java.util.List; /**
* A Star Algorithm
* @author liushaofeng
* @date 2015-8-24 下午11:05:48
* @version 1.0.0
*/
public class AstarAlgorithm
{
private List<Node> openList = null;
private List<Node> closeList = null;
private int[][] map; /**
* default constructor
* @param map data map
*/
public AstarAlgorithm(int[][] map)
{
this.map = map;
this.openList = new ArrayList<Node>();
this.closeList = new ArrayList<Node>();
} /**
* find path
* @param srcNode source node
* @param desNode destination node
* @return node path
*/
public Node findPath(Node srcNode, Node desNode)
{
init(srcNode);
do
{
if (openList.isEmpty())
{
break;
} Node node = openList.get(0);
List<Node> aroundPoint = getAroundPoint(srcNode, node, desNode);
openList.addAll(aroundPoint);
closeList.add(node);
openList.remove(node); } while (!findDes(desNode)); return findNodePath(desNode);
} private Node findNodePath(Node desNode)
{
for (Node node : openList)
{
if (node.getX() == desNode.getX() && node.getY() == desNode.getY())
{
return node;
}
}
return null;
} private boolean findDes(Node desNode)
{
for (Node node : openList)
{
if (node.getX() == desNode.getX() && node.getY() == desNode.getY())
{
return true;
}
}
return false;
} private void init(Node srcNode)
{
openList.add(srcNode);
} // top bottom left and right, four points
private List<Node> getAroundPoint(Node srcNode, Node nextNode, Node desNode)
{
int x = srcNode.getX();
int y = srcNode.getY(); int[] xData = new int[2];
int[] yData = new int[2];
if (x - 1 >= 0)
{
xData[0] = x - 1;
}
if (x + 1 < map.length)
{
xData[1] = x + 1;
} if (y - 1 >= 0)
{
yData[0] = y - 1;
}
if (y + 1 < map[0].length)
{
yData[1] = y + 1;
} List<Node> tmpList = new ArrayList<Node>(); for (int i : xData)
{
Node node = new Node(i, y, srcNode);
if (!isObstacle(node) && !inClosetList(node))
{
calcWeight(srcNode, node, desNode);
tmpList.add(node);
}
} for (int i : yData)
{
Node node = new Node(x, i, srcNode);
if (!isObstacle(node) && !inClosetList(node))
{
calcWeight(srcNode, node, desNode);
tmpList.add(node);
}
} return tmpList;
} private void calcWeight(Node parentNode, Node node, Node desNode)
{
node.setG(parentNode.getG() + 10);
int h = Math.abs(node.getX() - desNode.getX()) + Math.abs(node.getY() - desNode.getY());
node.setWeight(node.getG() + h * 10);
} private boolean inClosetList(Node nextNode)
{
for (Node node : closeList)
{
if (node.getX() == nextNode.getX() && node.getY() == nextNode.getY())
{
return true;
}
}
return false;
} private boolean isObstacle(Node nextNode)
{
return map[nextNode.getX()][nextNode.getY()] == 1;
} public static void main(String[] args)
{
int[][] map =
{
{ 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0 } }; AstarAlgorithm astar = new AstarAlgorithm(map);
Node pathNode = astar.findPath(new Node(3, 1, null), new Node(3, 5, null));
System.out.println(pathNode == null ? "Can not find path!" : pathNode.toString());
}
}
查看代码
数据模型
package cn.liushaofeng.algorithm; import java.util.ArrayList;
import java.util.List; /**
* Node
* @author liushaofeng
* @date 2015-8-24 下午09:48:53
* @version 1.0.0
*/
public class Node
{
private Node parentNode;
private int x;
private int y; private int weight;
private int g; /**
* default constructor
* @param x x point
* @param y y point
* @param parentNode parent node
*/
public Node(int x, int y, Node parentNode)
{
this.x = x;
this.y = y;
this.parentNode = parentNode;
} public int getG()
{
return g;
} public void setG(int g)
{
this.g = g;
} public Node getParentNode()
{
return parentNode;
} public void setParentNode(Node parentNode)
{
this.parentNode = parentNode;
} public int getX()
{
return x;
} public void setX(int x)
{
this.x = x;
} public int getY()
{
return y;
} public void setY(int y)
{
this.y = y;
} public int getWeight()
{
return weight;
} public void setWeight(int weight)
{
this.weight = weight;
} @Override
public String toString()
{
return getPath();
} private String getPath()
{
List<Node> dataList = new ArrayList<Node>();
Node node = this;
while (node != null)
{
dataList.add(node);
node = node.getParentNode();
} StringBuffer sb = new StringBuffer();
for (int i = dataList.size() - 1; i >= 0; i--)
{
if (i == 0)
{
sb.append("(" + dataList.get(i).getX() + "," + dataList.get(i).getY() + ")");
} else
{
sb.append("(" + dataList.get(i).getX() + "," + dataList.get(i).getY() + ")->");
}
}
return sb.toString();
}
}
查看代码
代码待调试。
最新文章
- OpenCV进阶之路：一个简化的视频摘要程序
- 配置SQL Server去使用 Windows的 Large-Page/Huge-Page allocations
- 关于登录的会话控制, 终极解决方案 - chunyu
- Asp.Net WebAPI Get提交、Post提交处理
- logstash 利用drop 丢弃过滤日志
- HDU 1269 裸奔的强联通分量
- DEV中gridview常用属性的设置
- how to use the curses library in unix?
- git学习笔记之一
- Django学习（八）---修改文章和添加文章
- 新概念英语（1-71）He's awful！
- HTML 动画收藏
- UPUPW配置
- Win系统的快捷键
- python的数据结构之栈
- SSM项目 单元测试中 注入bean 空指针异常
- Maven MyEclipse创建web项目没有src/maim/java
- maven部署项目流程（区分环境）
- C语言：用字符读取流和输出流来读写入数据。(文本文件)
- js 延时