java - A *算法很慢

我正在制作一种A *算法来查找地图上的最短路径。 到目前为止,我已经设法取得了正确的结果,但是即使对于一个小国来说,找到位置之间的最短路径也需要花费很长时间。 我的实现/我可以做的任何优化有什么问题吗?

以下是我的A *算法。 我还添加了一些相关的方法。

AStar.java

import java.util.List;
import java.util.PriorityQueue;
public class AStar {
    private Graph graph;
    private List<Edge> edges;
    private PriorityQueue<Node> unSearched;

    public AStar(Graph graph) {
        this.graph = graph;
        this.edges = graph.getEdges();
    }

    /*
     * Finds and prints shortest path from start to end using A* search
     */
    public void run(Node start, Node end) {
        // Initialize empty set and empty PriorityQueue
        unSearched = new PriorityQueue<Node>();

        // Set the current node to @param start
        Node current = start;
        // Set start node's heuristic values (g(x) and h(x))
        start.setDistanceToStart(0);
        start.setDistanceToEnd(slutt);
        // Add @param start to the queue
        unSearched.add(start);

        while (!unSearched.isEmpty()) {
            // Pop the PriorityQueue and set current to the top element;
            current = unSearched.poll();
            // If the current node is our target, print the path and end
            // System.out.println(current);
            if (current.equals(end)) {
                Node.printPath(end, edges);
                return;
            }
            // Move current node to the searched list.
            current.setSearched(true);
            updateNeighbor(current, end);
        }
        // We did not find the shortest path.
        System.out.println("Shortest path between " + start + " and " + slutt + " was not found.");
    }

    /*
     * @param curr node whose neighbors are to be checked/updated.
     * 
     * @param destination node which heuristics will be calculated from (AKA
     * distance from @param destination)
     */
    public void updateNeighbor(Node current, Node destination) {
        List<Node> neighbors = Graf.getNeighbors(edges, current);
        // distance is the current node's distance to start
        int distance = current.getDistanceToStart();
        for (Node neighbor : neighbors) {
            // temp is the distance from current node to a neighbor
            int temp = Graph.getDistanceToNeighbor(edges, current, neighbor);
            // If neighbor, no need to double check. Continue in
            // loop.
            if (!neighbor.getSearched()) {
                if (distance + temp < neighbor.getDistanceToStart()) {
                    // Shorter path has been found. Update neighboring node.
                    neighbor.setPrevNode(current);
                    neighbor.setDistanceToStart(distance + temp);
                    neighbor.setDistanceToSluttNode(destinasjon);
                    // Allow neighbor to be searched through by adding it to the unsearched queue
                    unSearched.add(neighbor);
                }
            }
        }
    }
}

相关方法

// Haversine formula for calculating distance to end node - given that one drive at 130 km/h
public void setDistanceToEnd(Node end) {
        double sin_bredde = Math.sin((this.getBreddeRadian() - end.getBreddeRadian()) / 2.0);
        double sin_lengde = Math.sin((this.getLengdeRadian() - end.getLengdeRadian()) / 2.0);
        this.distanceToEnd = (int) (35285538.46153846153846153846 * Math.asin(Math.sqrt(sin_bredde * sin_bredde
                + this.getCosBreddegrad() * end.getCosBreddegrad() * sin_lengde * sin_lengde)));
    } 

// Code that PriorityQueue uses to compare Nodes
@Override
    public int compareTo(Node node) {
        return Double.compare(this.getDistanceToEnd() + this.getDistanceToStart(),
                node.getDistanceToEnd() + node.getDistanceToStart());
    }
// Fetches adjacent(neighbor nodes) nodes for a given node
public static List<Node> getNeighbors(List<Kant> edges, Node n) {
        List<Node> neighbors = new ArrayList<Node>();
        for (Edge edge : edges) {
            if (edge.getStart().equals(n)) {
                neighbors.add(edge.getEnd());
            }
        }
        return neighbors;
    }

// gets distance between two nodes
public static Integer getDistanceToNeighbor(List<Edge> edges, Node start, Node end) {
        for (Edge edge : edges) {
            if (edge.getStart().equals(start) && edge.getEnd().equals(end)) {
                return edge.getDistance();
            }
        }
        return null;
    }

旁注:该代码已翻译成英文,因此,如果没有任何变量,请告诉我,我将进行编辑。

转载请注明来自askonline.tech,本文标题:java - A *算法很慢


 Top