Skip to main content
Get your brand new Wikispaces Classroom now
and do "back to school" in style.
Pages and Files
N - Puzzle
Travelling salesman problem
is the distance between two points measured along axes at right angles. The name alludes to the grid layout of the streets of Manhattan, which causes the shortest path a car could take between two points in the city.
if xi(s) and yi(s) are the x and y coordinates of tile i in state s, and if upper-line(xi) and upper-line (yi) are the x and y coordinates of tile i in the goal state, the heuristic is:
In the following example the Manhattan Distance is 3+6=9 moves:
Random 15-puzzle instances were first solved optimally using IDA* with Manhattan distance heuristic (Korf, 1985). Optimal solution lengths average 53 moves, and on average 400 million nodes were generated.
The limitation of the Manhattan Distance heuristic is that it considers each tile independently, while in fact tiles interfere with each other. Higher accuracy can be achieved by combining other heuristics, such as the
Linear Conflict Heuristic
The Manhattan Distance heuristic is
help on how to format text
Turn off "Getting Started"