我正在制定一种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;
}
旁注:该代码已翻译成英文,因此,如果没有任何变量,请告诉我,我会进行编辑。