"Paolo Negri" <hungrylist / gmail.com> writes:

> Here's my solution, first submission to ruby quiz, I hope is not 100%
> rubbish. I use a * 2 calculating the distance to avoid some noisy
> movements when approaching the ending point (so when the simple cost
> of terrain is about the same dimension of the distance).
> You can try the small map of the quiz without the *2 to see this
> behaviour. When the distance from the end point is >> than the terrain
> costs the *1 and *2 version act more or less the same way
> whell, here's the code.
>
> http://pastie.caboo.se/17815

Unfortunately, the A* algorithm depends on the fact that the estimate
of cost being added to each point (in this case, distance to goal) is
always less than or equal to the actual cost of getting to the goal
from that point.

By doubling the distance you violate this constraint, and so your
solution computes the wrong path given this map:

@..*...
...~...
...~~~*
.....^X

Your solution with the *2 in it does this:

####...
...~##.
...~~~#
.....^X

For a total cost of 10 (counting both the start and goal, and going
over two forests)

Your solution with the *2 bit removed gets closer to the correct path,
but there's still something off:

###*...
..#~...
..#~~~*
...###X

Looking over your solution, I think you've fallen victim to the fact
that the quiz author failed to explain A* clearly.  The excellent
online tutorials and wikipedia article already cited here on the list
are a better introduction.

On the plus side, yours is the only solution besides mine posted so
far that manages to get this path right:

@.*..
..~..
..^.X

That's because you wisely didn't use the manhattan distance quoted in
the puzzle statement.

-- 
s=%q(  Daniel Martin -- martin / snowplow.org
       puts "s=%q(#{s})",s.map{|i|i}[1]       )
       puts "s=%q(#{s})",s.map{|i|i}[1]