最短経路探索アルゴリズムを考えて

とある問題を解いたのだが、そこで今までに考えたこともない事を考えたのでまとめておく。

その問題は規約の都合上出典を明かすことが出来ないのだが、簡単に言えば「転職サイト」。その転職サイトではプログラマ向けの問題が出されており、その問題を解くコードを提出することで自分のプログラマレベルが評価されるというもの。ただ提出するのではなく、実際に提出したコードに対して転職サイト側が自動テストを行い、そのテストの通り具合や提出までの時間で最大100点の評価点数が与えられる。

その評価点数から見込み年収と、そのレベルにあった転職先が紹介されるというもの。

すばらしい。こんな転職サイトを待っていたよ。いや、転職じゃなくて就職サイトを待っていた。誰か仕事を下さい。

アルゴリズムが世界を支配する (角川ＥＰＵＢ選書)

作者: クリストファー・スタイナー
出版社/メーカー: KADOKAWA / 角川書店
発売日: 2013/10/10
メディア: Kindle版
この商品を含むブログ (7件) を見る

そして実際にいくつか解いていくのだが、なかなか難しい物もある。レベルは低い問題となっているのだが、数学がちんぷんかんぷんな私にとっては非常に難しい。

そしてその数学的な問題の中で最も実践的で、最も興味を持ったのがこの「最短経路探索」の問題になる。これは現在出題されている中では最高ランクの問題となっている。他の問題のほうが難しそうなのだが、最高ランクということはコーディングスキルよりも最短経路を探し出すアルゴリズムの効率化が重要なのかもしれない。

他の問題でも多々あるのだが、「大規模データ」のテストで失敗することが多いため(処理時間とメモリのリミットがある)、そこそこ効率のいいコードを書かなければ大規模データテストをパスするのは難しい。レベルの低いで問題でも大規模データに引っかかることが多いため、レベルが低いからと言ってワンパスで考えたコードでは100点を取るのは難しい。

私は今までに幾らかのコードを書いてきたのだがWeb系や単なるバッチ処理的なプログラムが多い。このような経路探索等の数学的な考え方を持つコードを正直な所書いたことがない。

ということでこの問題を考えてみた。他の問題もいくつかあったのだが、それらは直感的にわかりづらく、この経路探索が最も身近であるためにわかりやすかった。

f:id:mon0:20140521013400p:plain

ルールとしては、スタート地点からゴール地点までの最短移動数を考えるというもの。マップは単純な方眼で、その中にスタート地点とゴール地点が設置されており、マップ内には壁があり通過することは出来ない。方眼のマスは全て移動コストは「1」のため、最短移動数というのは最短距離を求めるのと同義になる。移動は上下左右の四近傍に限定される。

上図の解を考えてみると、「4」になる(右、下、下、下)。スタート地点から左に出ると「6」となる通路が最短になるが、右に出る通路が「4」になるため「4」が最短となる。他にも右図のように遠回りをする方法や、壁にぶち当たると引き返す通路があるが、同じ道を通るということは結局的にそこをスキップすればいいということなので最短にはならない(ルール上は同じルートを通ってはいけないという決まりはない、あくまでも最短移動「数」を求める問題になる)。

そしていくつかの方法を考えたのだが、なかなかどうもうまくいかない。

まず一番最初に思いついたのが、「不要な経路を全て削除する」と言う方法。

f:id:mon0:20140521013606p:plain

単純にはこの2パターンは削除できる。

移動が四近傍ということは、自分のマス目の上下左右の中から合計三箇所が壁であればそこは行き止まりであるということがわかる。行き止まりは経路としてスキャンしても無駄なため、最初からそれをマップの壁として変換する。他にも下図のような場合は、右図のように削除できる。これは経路の移動コストが全て同等なため、純粋に2x2の四マスの移動コストが同じになり、そうなると、壁に囲まれている角は通る必要が無い為になる。

これを複合的に使うと、空白の列や行を詰めることが出来たりとそこそこ範囲を狭めることが出来る。

他にもいくつか削除できるパターンを考えたのだが(壁の八近傍が空白等)、それはコードに起こすまで考えられなかったのでとりあえず無視してコードを書いた。が、動かなかったのでこの方法はとりあえず放置。

結局の所、どれだけ通路を削除したとしても通路を検索する処理は必要になるためそちらを調べる方法を考えた。

f:id:mon0:20140521013739p:plain

が、これは単純に全スキャンする方法しか思い浮かばない。とにかく人海戦術のようにスタート地点から1歩づつ動いて調べていく方法しか考えられない。

まず、スタート地点から右下左上に一方動く(壁があれば進まない)、そして、その一歩進んだところから右下左上に移動する。スタート地点から右に一歩進んだ場合は二歩目を左に行くとスタート地点に戻るため、一度通過した箇所はマークをつけておきスキップすることにする。そして、1歩目を進んだ箇所全箇所で二歩目を動かす。例えば、スタートから右への一歩目の二歩目の下マスと、スタートから下へ進んだ一歩目の二歩目の右マスは重複するため、それもスキップする。そのために、右下左上と移動順序を決めておくと考えやすい(実際はランダムかゴールに近い方を先にしてもいいが、机上で考えるときは順序付けたほうがわかりやすかったため)。

そして、歩数を広め自分の陣地を蟻地獄的に広げていったところでゴールに接触すればそれが最短経路になる。一度通った道と、後からきた道が接触する場合もあるが、最初に通った際のほうが歩数が少ないので後から通る方は行き止まりとして処理できる。

だが、これをどのようにコードを書けばいいかわからない。ほんとプログラマは業界別に全然技術が違うと実感できた。ここでも本気で考えればある程度思い浮かんだかもしれないが、今回は勉強のためのコードなので少しヒントを貰うために検索してみた。

そうすると、A*(エースター)という最短経路探索アルゴリズムがあるとのこと。Wikipediaの説明を読む限りでは全く理解できないが、「このページ」が参考になった。

構造体のコード例もあったためにコードの書き方はすんなり理解できたが、A*の意味はちょっとわからない。ヒューリスティックをゴールまでの仮想距離とし、その仮想距離が短い方に進み続けていくということはわかったが、それをどうコードに起こそうか。

ということで、A*の事はとりあえず忘れて私が考えた上のコードをA*のコード風に書いてみた(実際にクラス名などがAStarとなっているが、AStarアルゴリズムとは全く関係ありません)。

こちらもワンパスで書いて後はデバッグしたままのためテーブルとマス目の処理を分けていたりとめちゃくちゃだが、上の説明をそのままコードには起こせていると思う。

最短経路探索 - YouTube

実際に動かすとこのように経路を探索している様子が出力されるようにしています(Sleepで処理を遅らせています)。「B」は壁で、「2」が既に調査した位地、「1」は次に調査する立地になる。これを見るとかなり無駄な経路も進んでいることがわかる(マップは「PythonでA*(A-Star)アルゴリズム」より拝借。まだ読んでませんが、こちらはAStarを実装されているようです)。

上の不要なマスを取り除く処理と合わせればもう少し効率が良くなるかもしれないが、疲れたのでまた気が向いた時に。

#!/usr/bin/python3.4

import math

table = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ,
    [1, 8, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] ,
    [1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 9, 1] ,
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1] ,
    [1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1] ,
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] ,
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1] ,
    [1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1] ,
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1] ,
    [1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1] ,
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1] ,
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ,
]

def print_map(astars):
    for row in range(len(table)):
        for row_line in range(len(table[0])):
            if table[row][row_line] == 1:
                print("B", end="")
            elif astars[line(row,row_line)].status == None:
                print(" ", end="")
            elif astars[line(row,row_line)].status == True:
                print("1", end="")
            elif astars[line(row,row_line)].status == False:
                print("2", end="")

        print()
    print()


class AStar:
    parent = None
    status = None
    cost = 0

    def __str__(self):
        return str(self.cost)

    def __repr__(self):
        return str(self.cost)

    def open(self):
        self.status = True

    def close(self):
        self.status = False

    def getStatus(self):
        return self.status

    def setCost(self, cost):
        self.cost = cost

    def getCost(self):
        return self.cost

    def setParent(self, parent):
        self.parent = parent

    def getParent(self):
        return self.parent

astars = [AStar() for column in range(len(table)*len(table[0]))]

start = None
goal = None
for row in range(len(table)):
    for line in range(len(table[0])):
        if table[row][line] == 8:
            start = (row, line)
        elif table[row][line] == 9:
            goal = (row, line)

print("START:", start)
print("GOAL:", goal)

def line(y,x):
    return y*len(table[0])+x

def yon(current):
    position = []
    for i in [[-1, 0], [0, 1], [1, 0], [0, -1]]:
        (y, x) = (current[0]+i[0], current[1]+i[1])
        if 0 <= y < len(table) and 0 <= x < len(table[0]):
            if is_none([y, x]):
                position.append([y, x])
    return position

def astar_open(current, parent, start=False):
    astars[line(current[0], current[1])].open()
    if start:
        astars[line(current[0], current[1])].setCost(0)
    astars[line(current[0], current[1])].setParent(parent)

def astar_close(current):
    parent = astars[line(current[0], current[1])].getParent()
#    print("PARENT: ", parent)
    if parent:
        cost = astars[line(parent[0], parent[1])].getCost()
        astars[line(current[0], current[1])].setCost(cost+1)
    astars[line(current[0], current[1])].close()


def is_none(current):
    if astars[line(current[0], current[1])].status == None:
        return True
    return False

def is_open(current):
    if astars[line(current[0], current[1])].getStatus() is True:
        return True
    return False

def is_close(current):
    if astars[line(current[0], current[1])].getStatus() is False:
        return True
    return False

cost = 0
current = start

stack = [list(start)]#yon(current)
while(stack):
    current = stack.pop(0)
    if is_close(current):
        continue

    import time
    time.sleep(0.2)

    print_map(astars)
#    print("STACK: ", stack)
#    print("ASTARS: ", astars)

#    print("CURRENT: ", current)
    nexts = yon(current)
#    print("NEXTS: ", nexts)
    for next in nexts:
        if table[next[0]][next[1]] == 0:
            astar_open(next, current)
        elif table[next[0]][next[1]] == 1:
            astar_close(next)

    astar_close(current)
    stack.extend(nexts)

    if list(goal) in nexts:
        break

#    print("---")
else:
    print("False")


max = 0
for astar in astars:
    if max < astar.cost:
        max = astar.cost
print(max+1)

# for i in range(len(astars)):
#     if i != 0 and i % (len(table[0])) == 0:
#         print()
#     print("%3d" % (astars[i].cost), end="")
# print()