V
 the graph vertex typeE
 the graph edge typepublic class ALTAdmissibleHeuristic<V,E> extends Object implements AStarAdmissibleHeuristic<V>
The heuristic requires a set of input nodes from the graph, which are used as landmarks. During a preprocessing phase, which requires two shortest path computations per landmark using Dijkstra's algorithm, all distances to and from these landmark nodes are computed and stored. Afterwards, the heuristic estimates the distance from a vertex to another vertex using the already computed distances to and from the landmarks and the fact that shortest path distances obey the triangleinequality. The heuristic's space requirement is $O(n)$ per landmark where n is the number of vertices of the graph. In case of undirected graphs only one Dijkstra's algorithm execution is performed per landmark.
The method generally abbreviated as ALT (from A*, Landmarks and Triangle inequality) is described in detail in the following paper which also contains a discussion on landmark selection strategies.
Note that using this heuristic does not require the edge weights to satisfy the triangleinequality. The method depends on the triangle inequality with respect to the shortest path distances in the graph, not an embedding in Euclidean space or some other metric, which need not be present.
In general more landmarks will speed up A* but will need more space. Given an A* query with vertices source and target, a good landmark appears "before" source or "after" target where before and after are relative to the "direction" from source to target.
Constructor and Description 

ALTAdmissibleHeuristic(Graph<V,E> graph,
Set<V> landmarks)
Constructs a new
AStarAdmissibleHeuristic using a set of landmarks. 
Modifier and Type  Method and Description 

double 
getCostEstimate(V u,
V t)
An admissible heuristic estimate from a source vertex to a target vertex.

<ET> boolean 
isConsistent(Graph<V,ET> graph)
Returns true if the heuristic is a consistent or monotone heuristic
wrt the provided
graph . 
public ALTAdmissibleHeuristic(Graph<V,E> graph, Set<V> landmarks)
AStarAdmissibleHeuristic
using a set of landmarks.graph
 the graphlandmarks
 a set of vertices of the graph which will be used as landmarksIllegalArgumentException
 if no landmarks are providedIllegalArgumentException
 if the graph contains edges with negative weightspublic double getCostEstimate(V u, V t)
getCostEstimate
in interface AStarAdmissibleHeuristic<V>
u
 the source vertext
 the target vertexpublic <ET> boolean isConsistent(Graph<V,ET> graph)
graph
. A heuristic is monotonic if its estimate is always
less than or equal to the estimated distance from any neighboring vertex to the goal,
plus the step cost of reaching that neighbor. For details, refer to https://en.wikipedia.org/wiki/Consistent_heuristic.
In short, a heuristic is consistent iff h(u)≤ d(u,v)+h(v)
, for every edge
$(u,v)$, where $d(u,v)$ is the weight of edge $(u,v)$ and $h(u)$ is the estimated cost to
reach the target node from vertex u. Most natural admissible heuristics, such as Manhattan or
Euclidean distance, are consistent heuristics.isConsistent
in interface AStarAdmissibleHeuristic<V>
ET
 graph edges typegraph
 graph to test heuristic ongraph
, false otherwiseCopyright © 2019. All rights reserved.