数据结构与算法 - 寻路算法

用户11147438

发布于 2024-08-09 11:07:05

1470

发布于 2024-08-09 11:07:05

文章被收录于专栏：Linux系列

引言

寻路算法是计算机科学中一个重要的主题，用于在图中寻找从起点到终点的最短路径。这类算法广泛应用于游戏开发、地图导航、网络路由等领域。本文将深入探讨几种常见的寻路算法，包括 Dijkstra 算法和 A* 算法，并通过具体的 Java 代码详细说明它们的实现步骤。

一、寻路算法概述

寻路算法通常基于图论，其中图由节点（顶点）和边组成。节点代表地图中的位置，而边则表示节点间的连接。寻路算法的目标是从起点到终点找到一条路径，这条路径通常是成本最低的（例如距离最短或代价最小）。

二、Dijkstra 算法

Dijkstra 算法是一种用于解决单源最短路径问题的贪心算法。它保证找到从一个特定的起点到图中所有其他节点的最短路径。

1. Dijkstra 算法步骤

初始化：设置起点的距离为 0，其余节点的距离为无穷大。
选择未访问的最近节点：从未访问的节点中选择距离最短的节点。
更新邻居：更新所选节点的邻居的距离，如果通过当前节点到达邻居的距离更短，则更新邻居的距离。
标记已访问：将所选节点标记为已访问。
重复步骤 2 至 4，直到所有节点都被访问过或找到了目标节点。

2. Java 实现

首先，定义图节点和边的类：

import java.util.*;

class GraphNode {
    int id;
    String label;
    Map<GraphNode, Integer> neighbors;

    public GraphNode(int id, String label) {
        this.id = id;
        this.label = label;
        this.neighbors = new HashMap<>();
    }

    public void addNeighbor(GraphNode neighbor, int weight) {
        neighbors.put(neighbor, weight);
    }

    public void removeNeighbor(GraphNode neighbor) {
        neighbors.remove(neighbor);
    }
}

class Graph {
    private Map<Integer, GraphNode> nodes;

    public Graph() {
        nodes = new HashMap<>();
    }

    public void addNode(GraphNode node) {
        nodes.put(node.id, node);
    }

    public void removeNode(GraphNode node) {
        nodes.remove(node.id);
        // Remove references to this node from its neighbors
        for (GraphNode neighbor : node.neighbors.keySet()) {
            neighbor.removeNeighbor(node);
        }
    }

    public void addEdge(GraphNode node1, GraphNode node2, int weight) {
        node1.addNeighbor(node2, weight);
        node2.addNeighbor(node1, weight);  // For undirected graph
    }

    public void removeEdge(GraphNode node1, GraphNode node2) {
        node1.removeNeighbor(node2);
        node2.removeNeighbor(node1);  // For undirected graph
    }

    public void dijkstra(GraphNode start) {
        PriorityQueue<GraphNode> queue = new PriorityQueue<>(Comparator.comparingInt(n -> n.distance));
        Map<GraphNode, Integer> distances = new HashMap<>();
        Map<GraphNode, GraphNode> previous = new HashMap<>();

        for (GraphNode node : nodes.values()) {
            if (node == start) {
                distances.put(node, 0);
            } else {
                distances.put(node, Integer.MAX_VALUE);
            }
            queue.offer(node);
        }

        while (!queue.isEmpty()) {
            GraphNode current = queue.poll();

            for (Map.Entry<GraphNode, Integer> entry : current.neighbors.entrySet()) {
                GraphNode neighbor = entry.getKey();
                int weight = entry.getValue();
                int distanceThroughCurrent = distances.get(current) + weight;

                if (distanceThroughCurrent < distances.get(neighbor)) {
                    distances.put(neighbor, distanceThroughCurrent);
                    previous.put(neighbor, current);
                    queue.remove(neighbor);
                    queue.offer(neighbor);
                }
            }
        }

        printPath(previous, start, nodes.get(3));  // Example: Print path to node with ID 3
    }

    private void printPath(Map<GraphNode, GraphNode> previous, GraphNode start, GraphNode end) {
        List<GraphNode> path = new ArrayList<>();
        for (GraphNode node = end; node != null; node = previous.get(node)) {
            path.add(node);
        }
        Collections.reverse(path);

        System.out.print("Shortest path from " + start.label + " to " + end.label + ": ");
        for (GraphNode node : path) {
            System.out.print(node.label + " ");
        }
        System.out.println();
    }
}

3. Java 示例代码

创建图并执行 Dijkstra 算法：

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph();

        // 创建节点
        GraphNode nodeA = new GraphNode(1, "A");
        GraphNode nodeB = new GraphNode(2, "B");
        GraphNode nodeC = new GraphNode(3, "C");
        GraphNode nodeD = new GraphNode(4, "D");
        GraphNode nodeE = new GraphNode(5, "E");

        // 添加节点到图
        graph.addNode(nodeA);
        graph.addNode(nodeB);
        graph.addNode(nodeC);
        graph.addNode(nodeD);
        graph.addNode(nodeE);

        // 添加边
        graph.addEdge(nodeA, nodeB, 7);
        graph.addEdge(nodeA, nodeD, 5);
        graph.addEdge(nodeB, nodeC, 8);
        graph.addEdge(nodeB, nodeD, 9);
        graph.addEdge(nodeB, nodeE, 7);
        graph.addEdge(nodeC, nodeE, 5);
        graph.addEdge(nodeD, nodeE, 15);
        graph.addEdge(nodeD, nodeC, 15);
        graph.addEdge(nodeE, nodeC, 2);

        // 执行 Dijkstra 算法
        graph.dijkstra(nodeA);
    }
}

三、A* 算法

A* 算法是一种启发式搜索算法，它结合了 Dijkstra 算法和启发式函数的优势。A* 算法利用启发式函数来估计从当前节点到目标节点的近似成本，从而更快地找到最优路径。

1. A* 算法步骤

初始化：设置起点的 f 值（g 值 + h 值），其余节点的 f 值为无穷大。
选择未访问的最近节点：从未访问的节点中选择 f 值最小的节点。
更新邻居：更新所选节点的邻居的 g 值和 f 值，如果通过当前节点到达邻居的成本更低，则更新邻居的成本。
标记已访问：将所选节点标记为已访问。
重复步骤 2 至 4，直到所有节点都被访问过或找到了目标节点。

2. Java 实现

import java.util.*;

class AStarNode extends GraphNode {
    int g;  // Cost from start to this node
    int h;  // Estimated cost from this node to goal
    int f;  // Total estimated cost: g + h
    AStarNode previous;

    public AStarNode(int id, String label) {
        super(id, label);
        this.g = Integer.MAX_VALUE;
        this.h = 0;
        this.f = Integer.MAX_VALUE;
        this.previous = null;
    }

    public void setHeuristic(int heuristic) {
        this.h = heuristic;
        this.f = g + h;
    }
}

class AStarGraph extends Graph {
    public void aStar(AStarNode start, AStarNode goal) {
        PriorityQueue<AStarNode> openSet = new PriorityQueue<>(Comparator.comparingInt(n -> n.f));
        Set<AStarNode> closedSet = new HashSet<>();

        start.g = 0;
        start.setHeuristic(estimateCost(start, goal));
        openSet.add(start);

        while (!openSet.isEmpty()) {
            AStarNode current = openSet.poll();

            if (current.equals(goal)) {
                printPath(current);
                return;
            }

            closedSet.add(current);

            for (AStarNode neighbor : current.neighbors.keySet()) {
                if (closedSet.contains(neighbor)) {
                    continue;
                }

                int tentativeGScore = current.g + current.neighbors.get(neighbor);
                if (tentativeGScore < neighbor.g) {
                    neighbor.previous = current;
                    neighbor.g = tentativeGScore;
                    neighbor.setHeuristic(estimateCost(neighbor, goal));
                    if (!openSet.contains(neighbor)) {
                        openSet.add(neighbor);
                    }
                }
            }
        }
    }

    private void printPath(AStarNode node) {
        List<AStarNode> path = new ArrayList<>();
        while (node != null) {
            path.add(node);
            node = node.previous;
        }
        Collections.reverse(path);

        System.out.print("Shortest path found: ");
        for (AStarNode n : path) {
            System.out.print(n.label + " ");
        }
        System.out.println();
    }

    private int estimateCost(AStarNode start, AStarNode goal) {
        // Simple heuristic: Manhattan distance
        return Math.abs(start.id - goal.id);
    }
}

3. Java 示例代码

创建图并执行 A* 算法：

public class Main {
    public static void main(String[] args) {
        AStarGraph graph = new AStarGraph();

        // 创建节点
        AStarNode nodeA = new AStarNode(1, "A");
        AStarNode nodeB = new AStarNode(2, "B");
        AStarNode nodeC = new AStarNode(3, "C");
        AStarNode nodeD = new AStarNode(4, "D");
        AStarNode nodeE = new AStarNode(5, "E");

        // 添加节点到图
        graph.addNode(nodeA);
        graph.addNode(nodeB);
        graph.addNode(nodeC);
        graph.addNode(nodeD);
        graph.addNode(nodeE);

        // 添加边
        graph.addEdge(nodeA, nodeB, 7);
        graph.addEdge(nodeA, nodeD, 5);
        graph.addEdge(nodeB, nodeC, 8);
        graph.addEdge(nodeB, nodeD, 9);
        graph.addEdge(nodeB, nodeE, 7);
        graph.addEdge(nodeC, nodeE, 5);
        graph.addEdge(nodeD, nodeE, 15);
        graph.addEdge(nodeD, nodeC, 15);
        graph.addEdge(nodeE, nodeC, 2);

        // 执行 A* 算法
        graph.aStar(nodeA, nodeE);
    }
}