最短経路探索問題

スタートからの距離がdであることが決定している点集合P(d) = [p1, p2, ... , pn]に隣接し、かつ距離が決定していない点集合をP(d+1)として決定する…というのを再帰的にやると、距離のマップが出るよね。このとき、壁は初期状態から距離∞（無限大）を持つとする。

で、経路は、ゴールから逆に、決定した距離が-1になる隣接点を辿れば、大丈夫なんかな。

アルゴリズムをググったら負けだと思っている。

コードは汚い。whileは負けだていうか再帰じゃないし。テストコードもない。あげくの果てにスタートまで塗りつぶしているがもう終わり。

多分…3時間は超えたなぁ。

Point = Origin mimic

Point Start = Point mimic
Point Start start? = true
Point Start dist = 0

Point Wall = Point mimic
Point Wall dist = Number ∞

Point Goal = Point mimic
Point Goal goal? = true

Point dist = nil
Point start? = false
Point goal? = false

Point asText = " "
Point Start asText = "S"
Point Goal asText = "G"
Point Wall asText = "*"

Point parse = method(c,
  if(c == "S", Point Start mimic,
    if(c == "G", Point Goal mimic,
      if(c == "*", Point Wall mimic, Point mimic)
    )
  )
)
"Point Object is loaded..." println

m = FileSystem readLines("input.txt") map(chars map(c, Point parse(c)))
"m is loaded..." println

m each(x, line, line each(y, p, p x = x. p y = y))
m neighborOf = method(p, set([p x - 1][p y], [p x + 1][p y], [p x][p y - 1], [p x][p y + 1]))
m goal = m flatten find(goal?)
"m goal is #{m goal cellSummary}" println

d = 0
while(m goal dist == nil,
  "dist #{d} to #{d+1}" println
  m flatten select(dist == d) each(p, m neighborOf(p) select(dist == nil) each(dist = d + 1))
  d = d + 1
)
"dist map is created..." println

findRoad = method(p, m neighborOf(p) find(dist == p dist - 1))
q = m goal
while(q start? ==false,
  q = findRoad(q)
  q asText = "$"
)

m each(map(asText) join println)

Point Object is loaded...
m is loaded...
m goal is  Point Goal_0xF30494:
  x                            = 8
  y                            = 22

dist 0 to 1
dist 1 to 2
dist 2 to 3
(中略)
dist 58 to 59
dist 59 to 60
dist map is created...
**************************
*$* * $$$                *
*$* *$$*$ *************  *
*$* $$* $  ************  *
*$$$$*  $$$$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$$ * $$$$$$$$$$$$$G  *
*  * $$$$$*********** *  *
*    *        ******* *  *
*       *                *
**************************