一百行Ruby写个A*（2010-06-29）

Ruby quiz 的第98题让写一个 A* 寻路程序。Daniel Martin 提供了一个不到两百行的解答。如果简化一下，完全可以在一百行以内实现。

require 'enumerator'
# I suppose someone would think I should use a heap here.
# I've found that the built-in sort method is much faster
# than any heap implementation in ruby.  As a plus, the logic
# is easier to follow.

class PriorityQueue
  def initialize
    @list = 「」
  end
  def add(priority, item)
    # Add @list.length so that sort is always using Fixnum comparisons,
    # which should be fast, rather than whatever is comparison on `item'
    @list << [priority, @list.length, item]
    @list.sort!
    self
  end
  def <<(pritem)
    add(*pritem)
  end
  def next
    @list.shift[2]
  end
  def empty?
    @list.empty?
  end
end

require 'pp'

class Astar
  def do_quiz_solution(puzzle, instr)
    @terrain = puzzle
    @start, @goal = [0, 0], [2, 4]
    if do_find_path
      outarr = instr.split(「」n/)
      @path.each{|row,col| outarr[row][col]='#'}
      return outarr.join("/n")
    else
      return nil
    end
  end
  def do_find_path
    been_there = {}
    pqueue = PriorityQueue.new
    pqueue << [1,[@start,[],1]]
    while !pqueue.empty?
      spot,path_so_far,cost_so_far = pqueue.next
      next if been_there[spot]
      newpath = [path_so_far, spot]
      if (spot == @goal)
        @path = 「」
        newpath.flatten.each_slice(2) {|i,j| @path << [i,j]}
        return @path
      end
      been_there[spot] = true
      spotsfrom(spot).each {|newspot|
        next if been_there[newspot]
        tcost = @terrain[newspot[0]][newspot[1]]
        newcost = cost_so_far + tcost
        pqueue << [newcost + estimate(newspot), [newspot,newpath,newcost]]
      }
    end
    return nil
  end
  def estimate(spot)
    # quiz statement version
    # (spot[0] - @goal[0]).abs + (spot[1] - @goal[1]).abs
    # my version
    [(spot[0] - @goal[0]).abs, (spot[1] - @goal[1]).abs].max
  end
  def spotsfrom(spot)
    retval = 「」
    vertadds = [0,1]
    horizadds = [0,1]
    if (spot[0] > 0) then vertadds << -1; end
    if (spot[1] > 0) then horizadds << -1; end
    vertadds.each{|v| horizadds.each{|h|
        if (v != 0 or h != 0) then
          ns = [spot[0]+v,spot[1]+h]
          if (@terrain[ns[0]] and @terrain[ns[0]][ns[1]]) then
            retval << ns
          end
        end
      }}
    retval
  end
end
solution = Astar.new.do_quiz_solution([ [1, 1, 2, 1, 1], 
                            [1, 1, nil, 1, 1],
                            [1, 1, 3, 1, 1] ], 
                            "@.*../n..~../n..^.X")
solution.split(//n/).each {|s| puts s}
#=> ###..
#=> ..~#.
#=> ..^.#

在Daniel的程序里，do_quiz_solution() 是个外壳，它做三件事：找到起止点的坐标（@start 和 @goal），把 puzzle 解析成数值矩阵（存在 @terrain 中），把 puzzle 转换成没有空格的规范形式存进 instr 以便后面利用它把路径打印出来。

核心的部分是 do_find_path() 。这里需要用到优先队列 PriorityQueue 。优先队列的元素也是一个复合结构：[优先级, [当前考察的点, 到达该点的最佳路径, 目前花费的代价]] 。

do_find_path()
    been_there是个散列，用来保存已经访问过的节点。
    pqueue是一个优先队列，把[1, [起始点, 空路径, 1]]存入pqueue
    只要pqueue不空
        取出pqueue中优先级最小的元素（怎么取的你不用管，交给pqueue），这个元素包含了这些信息：考虑扩展的节点spot, 到达该点的最佳路径path_so_far, 目前花费的代价cost_so_far。
        如果造访过spot（pqueue为1或true），跳过本次循环。
        扩充路径：path_so_far → spot
        如果spot是终点，返回Bingo!
        否则，革命尚未成功，同志仍需努力！
        扩展spot，并把它的每个扩展点写进pqueue。

下面来看看如何实现优先队列：

优先队列可以看成一个半序的容器，它每次抛出优先级最低（或最高）的元素。优先队列一般是用堆（一种满足特定规则的完全二叉树）来实现的，但这里因为优先队列不是重点，Daniel 利用 Ruby 内置的 sort() 函数实现了一个简单，而且性能不咋地的优先队列。

@list 是个数组。每次在 add 新元素时，会把优先级信息也一并记录下来。另外，为了区分相同优先级的元素，add() 还会悄悄把该元素是第几个加入队列的元素也写进去，即：

@list << [priority, @list.length, item]

然后 sort! ，保证数组按优先级进行排列。

接着来看看估价函数，它用来评估当前所在的位置到目标点的尽可能大的下界（最好比实际代价小）。在这里，由于允许走斜线，只需考虑当前点与目标点横纵坐标差的最大值即可。

def estimate(spot)
  [(spot[0] - @goal[0]).abs, (spot[1] - @goal[1]).abs].max
end

还有一个辅助函数 spotfrom() ，用来生成当前点周围没访问过的邻居。

def spotsfrom(spot)
  retval = 「」
  vertadds = [0,1]
  horizadds = [0,1]
  if (spot[0] > 0) then vertadds << -1; end
  if (spot[1] > 0) then horizadds << -1; end
  vertadds.each{|v| horizadds.each{|h|
      if (v != 0 or h != 0) then
        ns = [spot[0]+v,spot[1]+h]
        if (@terrain[ns[0]] and @terrain[ns[0]][ns[1]]) then
          retval << ns
        end
      end
    }}
  retval
end

最后，我们来看看它是怎么把杂乱的字符串规整成标准形式的，以及又是如何依据规范字符地图生成二位数值矩阵的。

逐行分析输入的字符串：

• 遇到由纯空白符构成的行（/^/s*$/）就跳过；
• 替换掉所有非 .@~X*^ 符号；gsub!(/[^.@~X*^]/,'')
• 逐字分析：

scan(/[.@~X*^]/) {|terrain|
    # bla bla ...
}

根据题设在数值矩阵的相应位置写入相应的代价

case terrain
  when /[.@X]/; row << 1
  when /[*]/;   row << 2
  when //^/;    row << 3
  when /~/;     row << nil
end

题目里有个测试地图。我想把结果用图的形式显示出来，对 Ruby 这方面的库又不熟，只好用 Python 了（需要用到 matplotlib ）。

from matplotlib.pylab import *
#! python
import numpy as np
ary = 「」
for line in open('f:/large_map_solution.txt').readlines():
    for char in line:
        if char == '#':
            ary.append(20)
        elif char in set(['.', '@', 'X']):
            ary.append(1)
        elif char == '*':
            ary.append(2)
        elif char == '^':
            ary.append(3)
        elif char == '~':
            ary.append(10)
        else:
            pass
Z = np.array(ary).reshape(50,50)
matshow(Z)
colorbar()
show()

P.S. 果然不习惯 Python 的语法。

红色表示水塘，不能通过。 这是结果

好丑，还不如ASCII码：

#^.^~****^*~~.~^~..~~~^~.^~.*~**.^^*^*^~..*^^..~^.
*#*~*.~^^^~~.*~*.**.~~^*^**.^~*^^.*^...^..^.**.~^*
^^#**~.*^*^..^**.~~~.~*.~^^~^~^.^~^*~**.~*^.^**.*.
*~~#~^.~*~^~^^*^**.~.*^^*~~^^*~.^.*^^*^.^.~~^^^*~.
*.^~#^.~^.^.^^*~^~~*^..^~^~~^.*^^..**.**~.~~^~*~**
^.^^~#.*~**.*~*^*~^*~~^.^.~.~^**~.^^^^*.~.~~~^^.^.
*~~.*.#~~~^*.^*~~~*^.^**^*^.^.^~~***^^*^.~^^.^^.~.
.~.*~~^#.**.~^^~**^.^.^~~~^.~.^~~^^.~^^.^^~.~.~.*^
.^^^~~*~#^.~.*~.~~..~*~^.~**~..^****~.*~^~~*~**^~^
^^^*^^**.##*.^^*^^^.*~*~^^~*~~.~****~~~~***.^^~~^~
..*^^^^^.^~#^~.^.^^~*~^*~**^*^.~~~*^.^^~**~*~.....
**.^~~~^~*~#***.**^~.^.*^^^~.^...~.**^^^^~^.~^~.~*
^*~.*.~*^.~.#^^^^*~.**~^.*^*.~~..^~~~*~*^.~~^*^*^^
~*^.^..**~**^#^~***^~~*^*.*~..~^^***^.*~.^*^^^^.~.
*~^~^**^^*^^~^#~^^*~~~*^*~~~~*~^^^*~..~~~~~.*~^~*.
^.*.^*^**^^^~**#*.~^~~~^..~~~*~~^*~..^^.^~*.^~^~**
.***^..*^~~~~^~#*^~~.*.~^.^^*.***^~^.*....~.^.*~^^
^^~~~~.**.*.^^*.#~~^....*~*^~*^^.^~~~^*.~^^^~**^~~
^~~*^*.~.*^^^*^.*#.~*...~**^.^^~.^^.^..^.^**.^^..*
~^***~^.~.~^^^*~~~#*..^~^^.~^.~.**...~^~**~^~~**^~
~~~^~.^*.^*.~*.*~~^#.~*^^~~**.*.*.~^^^..^.~^.*.^~~
^^~...^.*~.^^**~^~*.#^~^~*....^.^^**~.*.^^*..~*~.*
^..^...~.~.*.~***~*~~#..~*~^^~~^~**^~~^*^^~*.~*^*^
*^.**^~*****.~~~..~^~#*.^*~^.^^*^..*~^.^.^*.^.~^^*
~...~*^....*^.*^^*...^#~~..^.*~.*~.*^.^*^*^.****^~
^..~***^.*^~~.****.~*^#~.^~*.~^*^~^.****~..~*..*^~
.~^~**~^^..~~~^..*~*.^*#~..^^*.~.*..*~~*~.^~.~*~~.
.***~..~**^.~.~.~*.~~**.#^.^~..~*~~~~*.**~~^..^.^^
~.*.~^*^*~^.~*..*~^~~.*.*##*.*..^~.*~^^*.~^.^~^**^
.*^~^^*.^*.~*...*~~~*.**.~.##*.*^.^*.^*~*.^~^**^*.
.~..*....~..~.***~..~^..~~^*^#^~^^~~**^.*~**^**^^*
^.*.~.^.**^*^.~^^*.~..*^~*^***#~**..^.~~*..^*^~*.~
^~~^~~*.~^^~~^**.^.^^^*^.*^^~~#^##~^*^^..**..**..^
^.^*.*^..*.~~.^^***^.*~..~.**^*#~^####^~*.~^~^..~~
~^^.^..*^^.**.~~^*~*^~*~^~~.~*.^~.~*^~#.*..^.^^*^*
^^.~*^~~*.~~*~.^..~*.^.~**.^*^.^~.**.~*#~...~~..*.
.~..^.~.~.^*.~^*~.~.*^*~~*.^.******~*~~#^~~~^.~~*~
~.*..^^*^~*.~~.~.^~..~.~^^^.*~*.**~^*~*^#^^~..^~^^
*.^*^**^*.^^*....**..~^^~.^*^.*~*^**^^..*##^*^^^.~
^*^~^^*.~*~^*~^~~.*.^*^~*^^~.*~.*~.**.*~^~~#~*^~~*
~~**~*.^.*~..~~^^^~^^^.~***^*.^*~^*~^~*~**.#.~..~.
*~**^~~.^.*.~^**~*^^.*^*.^~~*~~~*^.*..~~^*^#*^.^.*
.*^~..*~.*^^^^^~~^^*.~*.~~~.***~^.*..~~*****#~~^*.
.^^..^.^*^~^.~*...**~~~.**^*~~~*^***~^*^~^~~^#^*.*
**.**~.**~.*.*^~~.~^.*^.~~*.^*.~.***~*^^..~*.~#^*^
~..^.****^.****~^~***..^^^^*^.~*^^*.~~.^**^*~^*#~~
^*~^.~*...^^.^~.^^..~^...**...^****^*~*~*^..~^*~#~
...^~^.~^^~~~~.*^~.^~***~~^^^.*^^.~.^*~*~**^***^~#
.~~~~~^^.~~*^.~^^^**~^~.^~^~*..^*~^^*..*~^~**.*.^#
~^**.~**..*^~^^^.^*^~^~*^.~*~.^.**.^.^^.~**^~~^~^#