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]