On 16/10/06, Daniel Martin <martin / snowplow.org> wrote:
> "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]
>
>

The problem of my *1 version is how the choice among tiles with the
same price is done. The *2 is really rubbish and was just based on a
specific map, sorry.

to have a better view of what happens is interesting to print out all
the costs of the points on the map, here's a diff to avoid the *2 and
print the final result with cost.

59c59
<     (point1.zip(point2).map {|c| (c[0] - c[1]).abs}).max
---
>     (point1.zip(point2).map {|c| (c[0] - c[1]).abs}).max*2
103d102
<         (0..(line.size - 1)).each {|n| out << cost([n, line_n]).to_s}

If I'll have the time to work on it I'll submit some improvements.

Thanks

Paolo