[quiz] a* (#98)

quiz-98 (7.54 KB)

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