オフィスビル内の最短経路

現在のオフィスでは、エントランスからどの通路を通るのが最も近いのか、未だに話題になることがある。エントランスからオフィスにつながるエレベータまでの道が二通りあり、どちらも似たような距離なので同じオフィスに行く人達なのにそこで別々になってしまうこともしばしば。左の図が問題のフロアなんだけど、エントランスから青丸で示したエレベータまで行く必要がある。だったらコンピュータに解かせてしまえばいいじゃない、ということでプログラムを作って最短経路と正確な距離を調べてみた。定規で測ったほうが早いという意見は聞こえません。

以前、Python: 画像で与えられた迷路に対し2点間の最短経路を求めるというブログ記事で、画像から直接最短距離を求めるプログラムを書いたことがあるので、まずはそれを使って調べてみた。図面の邪魔な文字だけ消して、あとはスタート地点とゴール地点の座標を引数で指定するだけだから簡単なんだけど、これだと問題があることに気がついた。というのはCCL (connected component labeling; 連結成分ラベリング)で移動できる領域を調べて、それをA*で解いているのだけど、隣接するノード(ピクセル)を上下左右斜めの8方向のみで調べているから正しい距離を出すことができないのだ。実際に作成した図は以下のようにギザギザになってしまい最短ルートを通らない。なので通り道の分岐や方向が変化する箇所をノードにしてそれをA*で求めることにした。


全部で10個のノード(画像のピクセル座標で指定)を作って調べたところ、以下のような結果になった。左側を通る通路の距離が324.53、右側を通る通路の距離が322.51となり僅かに右側の通路のほうが近かった。ただし、右側の方は途中でフロア案内と少し重なるし、6つあるエレベータのどれを使うかによっても結果が変わってしまうぐらいなので、実質的には同じ距離といってしまっても差し支えないと思う。



結局、それぞれの距離にはほとんど差がないので、結論としては「好きな方を使え」ということになるだろう。自分は広い通路の方が好みなので右側の通路を利用している。最後にソースコードとその使い方を示しておく。

nodes.datに、一行を"ピクセルX座標 ピクセルY座標 隣接ノード番号リスト"としてノード数の分だけ記述する。ノード番号は0から始まり、先頭行と最終行のノードはそれぞれスタート地点、ゴール地点を表している。また、フロアの図面画像をinput.pngとして渡すと、最短距離のルートが書きこまれた画像をoutput.pngとして出力する。

% ./route_solver.py nodes.dat input.png output.png

nodes.dat

27 273 1 3 6 21 128 0 2 125 23 1 9 117 221 0 4 5 6 141 178 3 7 167 178 3 7 195 178 0 3 7 192 110 4 5 6 8 193 91 7 9 151 41 2 8

route_solver.py

#!/usr/bin/env python # -*- coding: utf-8 -*- import sys, os, math, heapq, Image, ImageDraw class Node: def __init__(self): self.pos = (0, 0) self.neighbors = [] self.dist = float("inf") self.path = [] # A* Search Algorithm class AStar: def __init__(self, start, goal): self.start, self.goal = start, goal self.start.dist = 0.0 self.start.path = [self.start] def distance(self, node1, node2): return math.sqrt((node1.pos[0] - node2.pos[0])**2 + (node1.pos[1] - node2.pos[1])**2) def heuristic(self, node): return self.distance(node, self.goal) def search(self): queue = [] heapq.heappush(queue, (self.heuristic(self.start), self.start)) while queue: score, last = heapq.heappop(queue) if last == self.goal: return last.path, last.dist for nb in last.neighbors: newdist = last.dist + self.distance(last, nb) if nb.dist < newdist: continue nb.dist = newdist nb.path = last.path + [nb] heapq.heappush(queue, (nb.dist + self.heuristic(nb), nb)) return [], 0.0 def draw_path(in_image, out_image, path): im = Image.open(in_image) im = im.convert("RGB") draw = ImageDraw.Draw(im) draw.line([(int(p.pos[0]), int(p.pos[1])) for p in path], fill=255, width=2) im.save(out_image) def main(args): if len(args) < 4: print >>sys.stderr, "Usage: %s datafile in_image out_image" % os.path.basename(args[0]) sys.exit(1) datafile, in_image, out_image = args[1:4]; print "Reading nodes data..." data = [map(int, l.strip().split()) for l in file(datafile).readlines()] nodes = [Node() for i in range(len(data))] for i, node in enumerate(nodes): node.pos = tuple(data[i][:2]) for j in data[i][2:]: node.neighbors.append(nodes[j]) print " Number of nodes: %d" % len(nodes) print "A* searching phase..." start, goal = nodes[0], nodes[-1] print " Start: (%d, %d), Goal: (%d, %d)" % (start.pos + goal.pos) astar = AStar(start, goal) path, dist = astar.search() if path: print " Found route:" for p in path: print " (%d, %d)" % p.pos print " Distance: %f" % dist else: print " No route." print "Drawing path on the imagefile..." draw_path(in_image, out_image, path) if __name__ == "__main__": main(sys.argv)

追記 (2011/10/17): ソースコードが間違っていたので修正。今回の結果には影響なし。