下面是使用 Java 实现 A* 算法的示例代码：
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;
class Node implements Comparable<Node> {
private int x;
private int y;
private int f; // f(n) = g(n) + h(n)
private int g; // 到起点的实际代价
private int h; // 到目标点的估计代价
private Node parent;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public int getF() {
return f;
}
public void setF(int f) {
this.f = f;
}
public int getG() {
return g;
}
public void setG(int g) {
this.g = g;
}
public int getH() {
return h;
}
public void setH(int h) {
this.h = h;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.f, other.f);
}
}
public class AStarAlgorithm {
private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private int[][] grid;
private int numRows;
private int numCols;
private Node startNode;
private Node endNode;
public AStarAlgorithm(int[][] grid) {
this.grid = grid;
this.numRows = grid.length;
this.numCols = grid[0].length;
}
public List<Node> findPath(int startX, int startY, int endX, int endY) {
startNode = new Node(startX, startY);
endNode = new Node(endX, endY);
PriorityQueue<Node> openSet = new PriorityQueue<>();
Set<Node> closedSet = new HashSet<>();
startNode.setG(0);
startNode.setH(manhattanDistance(startNode, endNode));
startNode.setF(startNode.getG() + startNode.getH());
openSet.add(startNode);
while (!openSet.isEmpty()) {
Node currNode = openSet.poll();
if (currNode.equals(endNode)) {
return reconstructPath(currNode);
}
closedSet.add(currNode);
for (int[] direction : DIRECTIONS) {
int newX = currNode.getX() + direction[0];
int newY = currNode.getY() + direction[1];
if (isValid(newX, newY) && !closedSet.contains(new Node(newX, newY))) {
Node neighbor = new Node(newX, newY);
int tentativeG = currNode.getG() + 1;
if (!openSet.contains(neighbor) || tentativeG < neighbor.getG()) {
neighbor.setParent(currNode);
neighbor.setG(tentativeG);
neighbor.setH(manhattanDistance(neighbor, endNode));
neighbor.setF(neighbor.getG() + neighbor.getH());
if (!openSet.contains(neighbor)) {
openSet.add(neighbor);
}
}
}
}
}
return null;
}
private int manhattanDistance(Node node1, Node node2) {
return Math.abs(node1.getX() - node2.getX()) + Math.abs(node1.getY() - node2.getY());
}
private boolean isValid(int x, int y) {
return x >= 0 && x < numRows && y >= 0 && y < numCols && grid[x][y] != 1;
}
private List<Node> reconstructPath(Node node) {
List<Node> path = new ArrayList<>();
while (node != null) {
path.add(node);
node = node.getParent();
}
Collections.reverse(path);
return path;
}
public static void main(String[] args) {
int[][] grid = {
{0, 0, 0, 1, 0},
{1, 1, 0, 1, 0},
{0, 0, 0, 0, 0},
{0, 1, 1, 1, 1},
{0, 0, 0, 0, 0}
};
AStarAlgorithm astar = new AStarAlgorithm(grid);
List<Node> path = astar.findPath(0, 0, 4, 4);
if (path != null) {
for (Node node : path) {
System.out.println("(" + node.getX() + ", " + node.getY() + ")");
}
} else {
System.out.println("No path found!");
}
}
}这个示例代码使用 A* 算法实现了从起点到终点的路径搜索。在 findPath 方法中，使用优先队列 openSet 存储待探索的节点，使用集合 closedSet 存储已经探索过的节点。通过计算节点的 f(n) 值（f(n) = g(n) + h(n)）来评估节点的优先级，优先探索具有较小 f(n) 值的节点。
注意：此示例代码中的 grid 是一个二维数组，其中 0 表示可以通过的路径，1 表示障碍物。将起点和终点的坐标传递给 findPath 方法，将返回路径上的所有节点。如果找不到路径，返回 null。
请注意，这只是 A* 算法的一种实现方式，还有其他的实现方式可供选择。
下面是一个使用A*算法的Java源码示例：
import java.util.*;
class Node implements Comparable<Node> {
int x, y; // 节点的坐标
int g, h; // g值为起点到当前节点的实际距离，h值为当前节点到终点的估计距离
Node parent; // 父节点
public Node(int x, int y) {
this.x = x;
this.y = y;
}
public int f() {
return g + h;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.f(), o.f());
}
}
class AStar {
private int[][] grid;
private int rows, cols;
private Node startNode, endNode;
public AStar(int[][] grid, int rows, int cols, int startX, int startY, int endX, int endY) {
this.grid = grid;
this.rows = rows;
this.cols = cols;
startNode = new Node(startX, startY);
endNode = new Node(endX, endY);
}
public List<Node> findPath() {
List<Node> openSet = new ArrayList<>();
Set<Node> closedSet = new HashSet<>();
openSet.add(startNode);
while (!openSet.isEmpty()) {
Node currentNode = openSet.get(0);
// 寻找f值最小的节点
for (int i = 1; i < openSet.size(); i++) {
if (openSet.get(i).f() < currentNode.f()) {
currentNode = openSet.get(i);
}
}
openSet.remove(currentNode);
closedSet.add(currentNode);
if (currentNode.x == endNode.x && currentNode.y == endNode.y) {
return buildPath(currentNode);
}
List<Node> neighbors = getNeighbors(currentNode);
for (Node neighbor : neighbors) {
if (closedSet.contains(neighbor)) {
continue;
}
int newG = currentNode.g + 1;
boolean isOpenSetContainsNeighbor = openSet.contains(neighbor);
if (!isOpenSetContainsNeighbor || newG < neighbor.g) {
neighbor.g = newG;
neighbor.h = manhattanDistance(neighbor, endNode);
neighbor.parent = currentNode;
if (!isOpenSetContainsNeighbor) {
openSet.add(neighbor);
}
}
}
}
return null;
}
private int manhattanDistance(Node node1, Node node2) {
return Math.abs(node1.x - node2.x) + Math.abs(node1.y - node2.y);
}
private boolean isValidPosition(int x, int y) {
return x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == 0;
}
private List<Node> getNeighbors(Node node) {
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
List<Node> neighbors = new ArrayList<>();
for (int i = 0; i < 4; i++) {
int newX = node.x + dx[i];
int newY = node.y + dy[i];
if (isValidPosition(newX, newY)) {
neighbors.add(new Node(newX, newY));
}
}
return neighbors;
}
private List<Node> buildPath(Node endNode) {
List<Node> path = new ArrayList<>();
Node currentNode = endNode;
while (currentNode != null) {
path.add(0, currentNode);
currentNode = currentNode.parent;
}
return path;
}
}
public class Main {
public static void main(String[] args) {
int rows = 5;
int cols = 5;
int[][] grid = {
{0, 0, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 1},
{0, 0, 0, 0, 0}
};
int startX = 0;
int startY = 0;
int endX = 4;
int endY = 4;
AStar aStar = new AStar(grid, rows, cols, startX, startY, endX, endY);
List<Node> path = aStar.findPath();
if (path != null) {
for (Node node : path) {
System.out.println("(" + node.x + ", " + node.y + ")");
}
} else {
System.out.println("No path found.");
}
}
}这个示例代码实现了一个迷宫路径查找的问题。grid数组表示迷宫地图，0表示可以通过的通路，1表示障碍物。startX和startY是起点的坐标，endX和endY是终点的坐标。程序会使用A*算法查找从起点到终点的最短路径，并将路径上的节点打印出来。如果没有找到路径，输出”No path found.”。
发布者：luotuoemo，转转请注明出处：https://www.jintuiyun.com/118770.html
