我目前正在实现一个带有不规则节点间距离的A*算法。包含节点的图是一个有向加权图。每个节点至少连接到另一个节点，也可能存在具有不同距离的对称连接。节点只是一个标签，不包含任何特殊信息。
我需要的是一种启发式的方法来确定从节点A到另一个节点B的最短路径尽可能准确。我尝试过使用一种启发式方法，返回节点最近邻的距离，但当然这并不如没有启发式方法（= Dijkstra）有效。
我的A*算法实现主要由两个类组成，一个用于算法本身（
我需要的是一种启发式的方法来确定从节点A到另一个节点B的最短路径尽可能准确。我尝试过使用一种启发式方法，返回节点最近邻的距离，但当然这并不如没有启发式方法（= Dijkstra）有效。
我的A*算法实现主要由两个类组成，一个用于算法本身（
AStar），另一个用于节点（Node）。代码主要基于维基百科上的伪代码。public class AStar {
private AStar() {}
private static Node[] reconstructPath(Map<Node, Node> paths, Node current) {
List<Node> path = new ArrayList<Node>();
path.add(0, current);
while (paths.containsKey(current)) {
current = paths.get(current);
path.add(0, current);
}
return path.toArray(new Node[0]);
}
public static Node[] calculate(Node start, Node target, IHeuristic heuristic) {
List<Node> closed = new ArrayList<Node>();
PriorityQueue<Node> open = new PriorityQueue<Node>();
Map<Node, Double> g_score = new HashMap<Node, Double>();
Map<Node, Double> f_score = new HashMap<Node, Double>();
Map<Node, Node> paths = new HashMap<Node, Node>();
g_score.put(start, 0d);
f_score.put(start, g_score.get(start) + heuristic.estimateDistance(start, target));
open.set(start, f_score.get(start));
while (!open.isEmpty()) {
Node current = null;
// find the node with lowest f_score value
double min_f_score = Double.POSITIVE_INFINITY;
for (Entry<Node, Double> entry : f_score.entrySet()) {
if (!closed.contains(entry.getKey()) && entry.getValue() < min_f_score) {
min_f_score = entry.getValue();
current = entry.getKey();
}
}
if (current.equals(target)) return reconstructPath(paths, target);
open.remove(current);
closed.add(current);
for (Node neighbor : current.getAdjacentNodes()) {
if (closed.contains(neighbor)) {
continue;
}
double tentative_g_score = g_score.get(current) + current.getDistance(neighbor);
if (!open.contains(neighbor) || tentative_g_score < g_score.get(neighbor)) {
paths.put(neighbor, current);
g_score.put(neighbor, tentative_g_score);
f_score.put(neighbor, g_score.get(neighbor) + heuristic.estimateDistance(neighbor, target));
if (!open.contains(neighbor)) {
open.set(neighbor, f_score.get(neighbor));
}
}
}
}
throw new RuntimeException("no path between " + start + " and " + target);
}
}
Node.java 的源代码
public class Node {
private Map<Node, Double> distances = new HashMap<Node, Double>();
public final String name;
public Node(String name) {
this.name = name;
}
public Set<Node> getAdjacentNodes() {
return Collections.unmodifiableSet(distances.keySet());
}
public double getDistance(Node node) {
return distances.get(node);
}
public void setDistance(Node node, double distance) {
distances.put(node, distance);
}
@Override
public String toString() {
return (name == null ? "Node@" + Integer.toHexString(hashCode()) : name);
}
}
PriorityQueue.java 的源代码
public class PriorityQueue<T> {
transient ArrayList<PriorityEntry<T>> elements = null;
private static final int DEFAULT_SIZE = 10;
public PriorityQueue() {
elements = new ArrayList<PriorityEntry<T>>(DEFAULT_SIZE);
}
public PriorityQueue(int initialCapacity) {
elements = new ArrayList<PriorityEntry<T>>(initialCapacity);
}
public boolean push(T element, double priority) {
PriorityEntry<T> entry = new PriorityEntry<T>(element, priority);
if (elements.contains(entry)) return false;
elements.add(entry);
elements.sort(null);
return true;
}
public void set(T element, double priority) {
PriorityEntry<T> entry = new PriorityEntry<T>(element, priority);
int index = elements.indexOf(entry);
if (index >= 0) {
elements.get(index).setPriority(priority);
} else {
elements.add(entry);
}
elements.sort(null);
}
public T peek() {
return size() <= 0 ? null : elements.get(0).getValue();
}
public T pop() {
return size() <= 0 ? null : elements.remove(0).getValue();
}
public boolean remove(T element) {
return elements.remove(new PriorityEntry<T>(element, 0));
}
public int size() {
return elements.size();
}
public boolean isEmpty() {
return elements.isEmpty();
}
public boolean contains(T element) {
return elements.contains(new PriorityEntry<T>(element, 0));
}
private class PriorityEntry<E> implements Comparable<PriorityEntry<? extends T>> {
private final E value;
private double priority = Double.MIN_VALUE;
public PriorityEntry(E value, double priority) {
this.value = value;
this.priority = priority;
}
public E getValue() {
return value;
}
public double getPriority() {
return priority;
}
public void setPriority(double priority) {
this.priority = priority;
}
@Override
@SuppressWarnings("unchecked")
public boolean equals(Object o) {
if (!(o instanceof PriorityEntry)) return false;
PriorityEntry<?> entry = (PriorityEntry<?>) o;
return value.equals(entry);
}
@Override
public int compareTo(PriorityEntry<? extends T> entry) {
return (int) (getPriority() - entry.getPriority());
}
}
}