Landmarks

When adding a node n to your frontier, you want to find two values from each landmark: L-n and L-goal. Your heuristic is the difference of those two values.

An example:

Using the two blue nodes as landmarks (there are obviously better ones, but for the sake of example...), going from Arad to Bucharest.

You already have pre-computed shortest paths lengths for all Cx and Ox paths. For example, CB would be 138+101 = 239, and OB would be 151+80+97+101 = 429.

So, first, you look at the neighbors of Arad, finding Zerind, Timisoara, and Sibiu.

Zerind's weight is 75 + max(|CB - CZ|, |OB - OZ|). CZ is 441, OZ is 71, so Zerind's weight is 433.

Timisoara's weight is 118 + max(|CB - CT|, |OB - OT|). CT is 376. OT is 264, so Timisoara's weight is 283.

Sibiu's weight is 140 + max(|CB - CS|, |OB - OS|). CS is 226, OS is 151. So Sibiu's weight is 418.

So .. unexpected, but in this case, you'd explore Timisoara next. You'd check Lugoj ...

Lugoj's weight is 118 + 111 + max(|CB - CL|, |OB - OL|). CL is 265, OL is 375. So Lugoj's weight is ... still 283.

Mehadia's weight is 118 + 111 + 70 + max(|CB - CM|, |OB - OM|). CM is 195, OM is 445. So Mehadia's weight is 343.

Drobeta's weight is 118+111+70+75 + max(|CB - CD|, |OB - OD|). CD is 120, OD is 565. So Drobeta's weight is 510.

Finally, Sibiu is the shortest estimated path. Next we would explore Fagaras and Rimnicu Vilcea, and be on our way toward Bucharest. (I'm not going to write out all the analysis for the rest of the nodes)

Note how Sibiu's estimation is actually the length of the real shortest path -- 418. This is because the shortest path from Sibiu to Bucharest was part of the shortest path from Oradea to Bucharest, so OB-OS was exactly equal to SB.

Hopefully this helps. It also wound up being an unintentionally cautionary tale about why you should select good landmarks :P

(If the second landmark were Eforie, for example, the search would've gone straight from Arad to Bucharest, with no unnecessary node exploration)

-Jonathan Skeate