一百行Ruby写个A*（2010-06-29）
2019-08-06 本文已影响0人
Pope怯懦懦地
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码：
#^.^~****^*~~.~^~..~~~^~.^~.*~**.^^*^*^~..*^^..~^.
*#*~*.~^^^~~.*~*.**.~~^*^**.^~*^^.*^...^..^.**.~^*
^^#**~.*^*^..^**.~~~.~*.~^^~^~^.^~^*~**.~*^.^**.*.
*~~#~^.~*~^~^^*^**.~.*^^*~~^^*~.^.*^^*^.^.~~^^^*~.
*.^~#^.~^.^.^^*~^~~*^..^~^~~^.*^^..**.**~.~~^~*~**
^.^^~#.*~**.*~*^*~^*~~^.^.~.~^**~.^^^^*.~.~~~^^.^.
*~~.*.#~~~^*.^*~~~*^.^**^*^.^.^~~***^^*^.~^^.^^.~.
.~.*~~^#.**.~^^~**^.^.^~~~^.~.^~~^^.~^^.^^~.~.~.*^
.^^^~~*~#^.~.*~.~~..~*~^.~**~..^****~.*~^~~*~**^~^
^^^*^^**.##*.^^*^^^.*~*~^^~*~~.~****~~~~***.^^~~^~
..*^^^^^.^~#^~.^.^^~*~^*~**^*^.~~~*^.^^~**~*~.....
**.^~~~^~*~#***.**^~.^.*^^^~.^...~.**^^^^~^.~^~.~*
^*~.*.~*^.~.#^^^^*~.**~^.*^*.~~..^~~~*~*^.~~^*^*^^
~*^.^..**~**^#^~***^~~*^*.*~..~^^***^.*~.^*^^^^.~.
*~^~^**^^*^^~^#~^^*~~~*^*~~~~*~^^^*~..~~~~~.*~^~*.
^.*.^*^**^^^~**#*.~^~~~^..~~~*~~^*~..^^.^~*.^~^~**
.***^..*^~~~~^~#*^~~.*.~^.^^*.***^~^.*....~.^.*~^^
^^~~~~.**.*.^^*.#~~^....*~*^~*^^.^~~~^*.~^^^~**^~~
^~~*^*.~.*^^^*^.*#.~*...~**^.^^~.^^.^..^.^**.^^..*
~^***~^.~.~^^^*~~~#*..^~^^.~^.~.**...~^~**~^~~**^~
~~~^~.^*.^*.~*.*~~^#.~*^^~~**.*.*.~^^^..^.~^.*.^~~
^^~...^.*~.^^**~^~*.#^~^~*....^.^^**~.*.^^*..~*~.*
^..^...~.~.*.~***~*~~#..~*~^^~~^~**^~~^*^^~*.~*^*^
*^.**^~*****.~~~..~^~#*.^*~^.^^*^..*~^.^.^*.^.~^^*
~...~*^....*^.*^^*...^#~~..^.*~.*~.*^.^*^*^.****^~
^..~***^.*^~~.****.~*^#~.^~*.~^*^~^.****~..~*..*^~
.~^~**~^^..~~~^..*~*.^*#~..^^*.~.*..*~~*~.^~.~*~~.
.***~..~**^.~.~.~*.~~**.#^.^~..~*~~~~*.**~~^..^.^^
~.*.~^*^*~^.~*..*~^~~.*.*##*.*..^~.*~^^*.~^.^~^**^
.*^~^^*.^*.~*...*~~~*.**.~.##*.*^.^*.^*~*.^~^**^*.
.~..*....~..~.***~..~^..~~^*^#^~^^~~**^.*~**^**^^*
^.*.~.^.**^*^.~^^*.~..*^~*^***#~**..^.~~*..^*^~*.~
^~~^~~*.~^^~~^**.^.^^^*^.*^^~~#^##~^*^^..**..**..^
^.^*.*^..*.~~.^^***^.*~..~.**^*#~^####^~*.~^~^..~~
~^^.^..*^^.**.~~^*~*^~*~^~~.~*.^~.~*^~#.*..^.^^*^*
^^.~*^~~*.~~*~.^..~*.^.~**.^*^.^~.**.~*#~...~~..*.
.~..^.~.~.^*.~^*~.~.*^*~~*.^.******~*~~#^~~~^.~~*~
~.*..^^*^~*.~~.~.^~..~.~^^^.*~*.**~^*~*^#^^~..^~^^
*.^*^**^*.^^*....**..~^^~.^*^.*~*^**^^..*##^*^^^.~
^*^~^^*.~*~^*~^~~.*.^*^~*^^~.*~.*~.**.*~^~~#~*^~~*
~~**~*.^.*~..~~^^^~^^^.~***^*.^*~^*~^~*~**.#.~..~.
*~**^~~.^.*.~^**~*^^.*^*.^~~*~~~*^.*..~~^*^#*^.^.*
.*^~..*~.*^^^^^~~^^*.~*.~~~.***~^.*..~~*****#~~^*.
.^^..^.^*^~^.~*...**~~~.**^*~~~*^***~^*^~^~~^#^*.*
**.**~.**~.*.*^~~.~^.*^.~~*.^*.~.***~*^^..~*.~#^*^
~..^.****^.****~^~***..^^^^*^.~*^^*.~~.^**^*~^*#~~
^*~^.~*...^^.^~.^^..~^...**...^****^*~*~*^..~^*~#~
...^~^.~^^~~~~.*^~.^~***~~^^^.*^^.~.^*~*~**^***^~#
.~~~~~^^.~~*^.~^^^**~^~.^~^~*..^*~^^*..*~^~**.*.^#
~^**.~**..*^~^^^.^*^~^~*^.~*~.^.**.^.^^.~**^~~^~^#
