Effective way of calculating manhattan distance?

[Michael Lesniak]

Hello,

I'm playing a bit with informed search algorithm, esp. A* and sliding
puzzles. For the heuristic I chose the manhattan distance, at the
moment implemented like

def manhattan
sum = 0
size = @puzzle.size
size.times do |y|
size.times do |x|
num = @puzzle.get x, y
l, m = @goal.number num
sum += (x - l).abs + (y - m).abs
end
end
sum
end

@puzzle simulates a Sliding puzzle, e.g. shuffling, generating possible
children, etc...
@puzzle.get x, y
returns the tile at position x, y

@goal.number num
returns the position of the tile in the desired state

Is there any better -- "faster" -- way of doing this?


Thanks for the help
Michael

 

[Martin DeMello]

I'm playing a bit with informed search algorithm, esp. A* and sliding
puzzles. For the heuristic I chose the manhattan distance, at the
moment implemented like

def manhattan
sum = 0
size = @puzzle.size
size.times do |y|
size.times do |x|
num = @puzzle.get x, y
l, m = @goal.number num
sum += (x - l).abs + (y - m).abs
end
end
sum
end .....

Is there any better -- "faster" -- way of doing this?

You could pass the metric of the parent state in as a parameter, and
only calculate the differential metric. e.g.

def search_solution_space(node, metric)
child_states.each {|state|
dm = 0
moved_pieces.each {|piece| dm += manhattan(piece)}
search_solution_space(node, metric+dm)
}
end

martin

 

[Michael Lesniak]

Hello Martin,

You could pass the metric of the parent state in as a parameter, and
only calculate the differential metric. e.g.

Sounds like a good idea,

Thanks
Michael