Let h(x)
be your heuristic for node x
and h*(x)
the perfect heuristic (where you know the EXACT distance to your goal from x
), if 0 < h(x) <= h*(x)
for every node of the graph then the heuristic is admissible.
- If
h(x) = 0
you have no information and A* degenerates into
Dijkstra's algorithm.
- If
h(x) = h*(x)
you do know the answer
and therefore there is no problem to solve.
- The closer
h(x)
is to h*(x)
, the shorter A* will take to find the shortest path.
- If
h(x) > h*(x)
then your solution is not guaranteed to be optimal (i.e. found path might not be the least cost path.)
Some well known heuristics that meet this criteria are Euclidean distance and Manhattan distance.
If h(x) <= d(x,y) + h(y)
for every edge x, y
of the graph, where d(x,y)
is the actual distance between the nodes, the heuristic is said to be monotone (or consistent) and no nodes need to be processed more than once.
Said that, any heuristic that doesn't overestimate the distance will do fine. It doesn't matter if your nodes have different weights, that's part of d(x)
(the actual distance of your walked path), not h(x)
which is just a roughly estimate to favor some paths before others. As long as h(x)
(remember, it's just an estimate) is < h*(x)
you'll get the optimal route.
In an ordinary case, I would just use the same way I got to goal to go back, but since one of the streets could have been a one-way, that may not be possible.
It doesn't really matter if you have one-way streets. Your graph can be directed and you just don't let your algorithm generate that route. You don't need to go back while executing A*, because it would become a longer route that if you didn't take that path in the first place. If you want to go back from GOAL
to NODE
that's just a new search in your search space, not a single problem.
Regarding MSalters' notice, I don't think you can derive a heuristic in a graph with just weights. You need a problem that meets some kind of criteria that offers extra information to guess from. If you only have weights, then you can't to it better than Dijkstra's because you lack any more information. It depends entirely on the problem domain, so a broad answer that fits any graph can't be given.
- it's ice, you will move unless you hit a rock.
- the only way to change direction is to hit a rock.
- if you hit a rock you have to change directions.
- cycles are good, for obvious reasons.
- there can be multiple starts, and multiple ends.
more advanced properties:
- the cells without adjacent rocks are not reachable (some can be traversed)
- walls are rocks too, if you remove them, you can decide to wrap around.
- you can use sub-grids as patterns ("tiling" 3x3, 3x4, 5x5, ...etc)
- you can overlay a puzzle MxN tile on top of non-traversable MxN area and add a rock to redirect in/out of it.
- rotation or symmetry of a tile can be interesting
- you can expand a tile by inserting icy rows / columns
example:
S=start, E=end, o=rock, .=ice
3 . 2 o 3 . . 2 o . . . . . o o
4 . . E ~= 4 . . . E ~= . . . . . 2 E
o . . . o . . . . . . . . . . .
S . 1 o S . . 1 o S . . . . 1 o
example of combining tiles:
3 . . 2 o o 2 . . 3 3 . . 2 o 7 . . 6
4 . . . E + E . . . 4 = 4 . . . . . . . 5
o . . . . . . . . o o . . . . . . . o
S . . 1 o o 1 . . S S . . 1 o 8 . . E
you might like the game Tsuro, it uses tiles to generate a random board.
Best Answer
I've found the following picture a good key for the difference between different measures (although undirected graphs are depicted, some apply to directed as well). Degree centrality [D] is straightforward: who has most in/out links. Eigenvector-centrality [C] captures the notion of indirect influence better. See Centrality on wikipedia for the definitions and details.