Ruby勉強 -- 追記：統計的なアプローチ（のつもり）

最適解？何それ美味しいの？なコード
解を見つけたり見つけなかったりします。
探索を繰り返して良さそうな経路の評価を高くし、悪そうな経路の評価を低くしていきます。
探索は前回までの評価を元に行いますが、乱数によるフラつきをいれています。
評価、乱数パラメータのバランスで挙動が変わります。また局所解にトラップされると最短経路を見つけることができません。
いろんな代償を払いますがより一般的な問題へ適用可能なはず。（うっかりマヌケな解を出すのが人間ぽくていい）

# http://okajima.air-nifty.com/b/2010/01/post-abc6.html
class Maze
  @@directions  = [{'x'=>-1,'y'=>0},{'x'=>1,'y'=>0},{'x'=>0,'y'=>-1},{'x'=>0,'y'=>1}]
  @@trial_count = 1000
  @@swinging    = 1.0
  @@positive    = 1.05
  @@negative    = 0.99
  @@base        = 100.0
  def run
    load_map
    @@trial_count.times {|i|
      route = Array.new
      solve_map(@s['y'],@s['x'], 0, route)
    }
    if select_route(@g['y'],@g['x']) then @map.each{|line| print line.to_s + "\n" } else print "fail!\n" end
  end
  def load_map
    data = DATA.read 
    @map = []
    data.each_line {|line| @map.push line.chomp.split(//) }
    @cmap = []
    @map.each{|m| @cmap.push Array.new(m.size, @@base)}
    @map.each_with_index{|line,i| line.each_with_index{|c,j|
        @s = {'x'=>j, 'y'=>i} if c == 'S' 
        @g = {'x'=>j, 'y'=>i} if c == 'G' 
    }}
  end
  def solve_map(y,x,c,route)
    node = {'x'=>x,'y'=>y}
    # check goal
    if @map[y][x] == 'G'
      route.each_with_index{|node,i|
        @map[node['y']][node['x']] = ' '
        @cmap[node['y']][node['x']] *= @@positive*(1.0+1.0/(c*c))
      }
      return 
    end
    # new node
    if @map[y][x] == ' '
      @map[y][x] = '-' 
      route.push node
    end
    # check route
    walkable = false
    @@directions.each{|d| walkable |= @map[y+d['y']][x+d['x']] == ' '}
    if walkable then
      max_c = -10000.0
      ny=-1
      nx=-1
      @@directions.each{|d|
        rc = (rand(10000)/5000.0-1.0)*@@swinging
        if @cmap[y+d['y']][x+d['x']]+rc > max_c && (@map[y+d['y']][x+d['x']] == ' ' || @map[y+d['y']][x+d['x']] == 'G')
          max_c = @cmap[y+d['y']][x+d['x']]+rc 
          ny = y+d['y']
          nx = x+d['x']
        end
      }
      return solve_map(ny,nx,c+1,route) if nx != -1 && ny != -1
    else
      # abort
      route.each_with_index{|node,i|
        @map[node['y']][node['x']] = ' '
        @cmap[node['y']][node['x']] *= @@negative
      }
      return
    end
  end
  def select_route(y,x)
    @map[y][x] = '$' if @map[y][x] == ' '
    @@directions.each{|d| return true if @map[y+d['y']][x+d['x']] == 'S'}
    max_c = -10000.0;
    ny=-1
    nx=-1
    @@directions.each{|d|
      if (@cmap[y+d['y']][x+d['x']] > max_c && @map[y+d['y']][x+d['x']] == ' ')
         max_c = @cmap[y+d['y']][x+d['x']]
         ny = y+d['y']
         nx = x+d['x']
      end
    }
    return select_route(ny,nx)  if nx != -1 && ny != -1
    return false
  end
end
maze = Maze.new
maze.run
__END__
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************