[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Effective way of calculating manhattan distance?

michael.lesniak@gmail.com

6/23/2006 7:55:00 AM

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
3 Answers

Martin DeMello

6/23/2006 9:00:00 AM

0

Michael Lesniak <michael.lesniak@gmail.com> wrote:
>
> 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@gmail.com

6/23/2006 9:15:00 AM

0

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

flaviaR

1/14/2010 7:15:00 PM

0

Hey, P-Dub - didja notice how the moron said,
*outright*, "JEWS" instead of "Israel"?
And yet they want everyone to think their
"criticism" of Israel is "justified", and not
motivated by *anything* other than "concern
for the poor Palestinians [sic]."!!!

Susan



On 13-Jan-2010, P-Dub <pwolfe00@hotmail.com> wrote:

> Israel is most certainly prepared to strike against anyone who is stupid
> enough to attack. May God continue to give Israel strength to defend
> against all those who would attack His people.
>
> And may all the enemies of Israel burn for all eternity.
>
> P-Dub: Kiss my ass, sunray.
>
> sunray22b wrote:
> > Jews Preparing For Biological War -
> > http://www.jpost.com/servlet/Satellite?cid=1263147877141&pagename=JPost%2FJPArticle%...
> > in preparation for a non-conventional attack on Israel, the National
> > Emergency Authority (NEA) will hold the largest-ever exercise to train
> > security forces how to respond to a citywide biological attack. The
> > scenario
> > is a biological terror attack. The IDF Home Front Command will work to
> > clear
> > the infected area together with the Israel Police and Magen David Adom.
> > Defence officials said Tuesday that Israel needs to be prepared for a
> > biological attack.
> >
> > Defence training does not prove that they are about to attack us but it
> > is
> > suggestive. Any decent government should make sure that their nuclear
> > strike
> > list includes Tel Aviv, Haifa, Nes Ziona but maybe not Jerusalem.
> >
> >