package net.mooctest; import java.util.*; public class astar extends searchalgorithm { public astar(graph graph, node startnode, node endnode, vehicle vehicle, trafficcondition trafficcondition, weathercondition weathercondition, int currenttime) { super(graph, startnode, endnode, vehicle, trafficcondition, weathercondition, currenttime); } public double heuristic(node node) { double distancetoend = math.abs(node.getnodeid() - endnode.getnodeid())

+ Math.abs(node.getY() - endnode.getY()); double distancefromstart = graph.getDistance(startnode, node); return distancetoend + distancefromstart; } public List<node> search() { Queue<node> queue = new PriorityQueue<>(Comparator.comparingDouble(this::heuristic)); queue.add(startnode); Map<node, Double> gscore = new HashMap<>(); gscore.put(startnode, 0.0); Map<node, node> cameFrom = new HashMap<>(); while (!queue.isEmpty()) { node current = queue.poll(); if (current.equals(endnode)) { return reconstructPath(cameFrom, current); } for (edge edge : graph.getOutgoingEdges(current)) { node neighbor = edge.getDestinationNode(); double tentativeGscore = gscore.get(current) + edge.getLength(); if (!gscore.containsKey(neighbor) || tentativeGscore < gscore.get(neighbor)) { gscore.put(neighbor, tentativeGscore); double fscore = tentativeGscore + heuristic(neighbor); queue.remove(neighbor); queue.add(neighbor); cameFrom.put(neighbor, current); } } } return null; } private List<node> reconstructPath(Map<node, node> cameFrom, node current) { List<node> path = new ArrayList<>(); path.add(current); while (cameFrom.containsKey(current)) { current = cameFrom.get(current); path.add(current); } Collections.reverse(path); return path; } } [2024-10-27 10:09:56 | AI写代码神器 | 1121点数解答]