From: Daniel Martin <martin@...>
Date: 2006-10-16T23:05:29+09:00
Subject: Re: [QUIZ] A* (#98)

"Glen F. Pankow" <Glen.F.Pankow@noaa.gov> writes:

> #! /usr/bin/env ruby
> #
> # quiz-98  --  demonstrate the A* search algorithm on a simple map.
> #
> # Glen Pankow       10/15/06        1.1     Original version.
> #
> # Licensed under the Ruby License.
> #

As with most other solutions posted so far, this solution fails on
this simple map: (which is covered in my test scenario)

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

It goes over the mountain.  The culprit is the manhattan distance,
which overestimates the distance to the goal (since diagonal moves are
allowed).  A* only works with an underestimate.

-- 
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]