Problem: 无链接
文章目录
- 思路
- 解题方法
- 复杂度
- Code
思路
这是一个经典的A寻路算法问题。A算法是一种启发式搜索算法，题解结合了最佳优先搜索和Dijkstra算法的优点，能够在寻找最短路径的过程中避免大量的无谓搜索，提高了效率。
在这个问题中，我们需要找到从起点到终点的最短路径。我们可以使用A*算法，通过一个优先队列（堆）来存储待搜索的节点，每次从堆中取出代价最小的节点进行搜索，直到找到终点。
解题方法
首先，我们需要定义一个二维数组distance，用来存储从起点到每个点的最短距离。初始时，所有点的距离都设为无穷大，只有起点的距离设为0。
然后，我们定义一个优先队列heap，用来存储待搜索的节点。每个节点的代价由两部分组成：从起点到该节点的已知最短距离，以及该节点到终点的估计距离（启发式函数）。我们每次从堆中取出代价最小的节点进行搜索。
在搜索过程中，我们需要更新每个节点的最短距离，并将其邻居节点加入到堆中。如果某个节点已经被访问过，那么我们就不需要再次访问它。
最后，当我们找到终点时，就可以返回其最短距离了。
复杂度
时间复杂度:
O ( n 2 l o g n ) O(n^2 log n) O(n2logn)，其中n是网格的大小。这是因为在最坏的情况下，我们需要访问网格中的每个节点，并在堆中进行插入和删除操作。
空间复杂度:
O ( n 2 ) O(n^2) O(n2)，主要是因为我们需要存储每个节点的最短距离和访问状态。
Code
import java.util.PriorityQueue;
public class AStarAlgorithm {
public static int[] move = { -1, 0, 1, 0, -1 };
public static int minDistance1(int[][] grid, int startX, int startY, int targetX, int targetY) {
if (grid[startX][startY] == 0 || grid[targetX][targetY] == 0) {
return -1;
}
int n = grid.length;
int m = grid[0].length;
boolean[][] vis = new boolean[n][m];
int[][] distance = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
distance[i][j] = Integer.MAX_VALUE;
}
}
distance[startX][startY] = 1;
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[2] - b[2]);
heap.add(new int[] { startX, startY, distance[startX][startY] });
while (!heap.isEmpty()) {
int[] records = heap.poll();
int x = records[0];
int y = records[1];
if (vis[x][y]) {
continue;
}
vis[x][y] = true;
if (x == targetX && y == targetY) {
return distance[x][y];
}
// 开枝散叶
for (int i = 0; i < 4; i++) {
int nx = x + move[i];
int ny = y + move[i + 1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && grid[nx][ny] == 1
&& distance[x][y] + 1 < distance[nx][ny]) {
distance[nx][ny] = distance[x][y] + 1;
heap.add(new int[] { nx, ny, distance[nx][ny] });
}
}
}
return -1;
}
public static int minDistance2(int[][] grid, int startX, int startY, int targetX, int targetY) {
if (grid[startX][startY] == 0 || grid[targetX][targetY] == 0) {
return -1;
}
int n = grid.length;
int m = grid[0].length;
boolean[][] vis = new boolean[n][m];
int[][] distance = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
distance[i][j] = Integer.MAX_VALUE;
}
}
distance[startX][startY] = 1;
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[2] - b[2]);
heap.add(new int[] { startX, startY, 1 + f1(startX, startY, targetX, targetY) });
while (!heap.isEmpty()) {
int[] record = heap.poll();
int x = record[0];
int y = record[1];
if (vis[x][y]) {
continue;
}
vis[x][y] = true;
if (x == targetX && y == targetY) {
return distance[x][y];
}
// 开枝散叶
for (int i = 0; i < 4; i++) {
int nx = x + move[i];
int ny = y + move[i + 1];
if (nx >= 0 && ny >= 0 && nx < n && ny < m && !vis[nx][ny] && grid[nx][ny] == 1
&& distance[x][y] + 1 < distance[nx][ny]) {
distance[nx][ny] = distance[x][y] + 1;
heap.add(new int[] { nx, ny, distance[nx][ny] + f1(nx, ny, targetX, targetY) });
}
}
}
return -1;
}
// 曼哈顿距离
public static int f1(int x, int y, int targetX, int targetY) {
return (Math.abs(targetX - x) + Math.abs(targetY - y));
}
// 对角线距离
public static int f2(int x, int y, int targetX, int targetY) {
return Math.max(Math.abs(targetX - x), Math.abs(targetY - y));
}
// 欧式距离
public static double f3(int x, int y, int targetX, int targetY) {
return Math.sqrt(Math.pow(targetX - x, 2) + Math.pow(targetY - y, 2));
}
// 为了测试
public static int[][] randomGrid(int n) {
int[][] grid = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (Math.random() < 0.3) {
// 每个格子有30%概率是0
grid[i][j] = 0;
} else {
// 每个格子有70%概率是1
grid[i][j] = 1;
}
}
}
return grid;
}
// 为了测试
public static void main(String[] args) {
int len = 100;
int testTime = 10000;
System.out.println("功能测试开始");
for (int i = 0; i < testTime; i++) {
int n = (int) (Math.random() * len) + 2;
int[][] grid = randomGrid(n);
int startX = (int) (Math.random() * n);
int startY = (int) (Math.random() * n);
int targetX = (int) (Math.random() * n);
int targetY = (int) (Math.random() * n);
int ans1 = minDistance1(grid, startX, startY, targetX, targetY);
int ans2 = minDistance2(grid, startX, startY, targetX, targetY);
if (ans1 != ans2) {
System.out.println("出错了!");
}
}
System.out.println("功能测试结束");
System.out.println("性能测试开始");
int[][] grid = randomGrid(4000);
int startX = 0;
int startY = 0;
int targetX = 3900;
int targetY = 3900;
long start, end;
start = System.currentTimeMillis();
int ans1 = minDistance1(grid, startX, startY, targetX, targetY);
end = System.currentTimeMillis();
System.out.println("运行dijskra算法结果: " + ans1 + ", 运行时间(毫秒) : " + (end - start));
start = System.currentTimeMillis();
int ans2 = minDistance2(grid, startX, startY, targetX, targetY);
end = System.currentTimeMillis();
System.out.println("运行A*算法结果: " + ans2 + ", 运行时间(毫秒) : " + (end - start));
System.out.println("性能测试结束");
}
}
