cost going from state to a goal state.Is is expected that the heuristic is admissible, it means its is an
optimistic estimation and never an over-estimate, thus is cannot be
higher than the lowest possible remaining cost.
See SearchSolver::do_revisit for details.
Default: 0.
# An heuristic of the estimated `cost` going from `state` to a goal state.
#
# Is is expected that the heuristic is *admissible*, it means its is an
# optimistic estimation and never an over-estimate, thus is cannot be
# higher than the lowest possible remaining cost.
# See `SearchSolver::do_revisit` for details.
#
# Default: `0`.
fun heuristic(state: S): Float do return 0.0
lib/ai/search.nit:99,2--107,45
# The sum of the Manhattan distances of each tile to its goal
# Not the best heuristic but the simplest to implement among the good ones.
redef fun heuristic(state)
do
var p = 0
var i = -1
for t in state do
i += 1
# The hole does not count
if t == hole then continue
var dx = (i % width - t.goal_idx % width).abs
var dy = (i / width - t.goal_idx / width).abs
# Add Manhattan distance
p += dx + dy
end
return p.to_f
end
lib/ai/examples/puzzle.nit:148,2--167,4