The shortest Knight's path の続き

アルゴリズムの本で、ワーシャル・フロイドのアルゴリズムというのが載っていて、他のアルゴリズムと比べるとコードが短くて簡単そうだったので、試してみた。

Wikipediaの日本語版ではワーシャル－フロイド、英語版ではフロイド－ワーシャル (Floyd–Warshall)なのが少し気になるが、まあそれはいいとして。

ワーシャル－フロイド法

簡単に言うと、すべての点と点の距離を最初に全部計算してしまう、という方法である。

3回ループまわすだけで、すべての点と点の距離を計算できてしまう。どうしてそうなるかは、まだあまり理解できていないが、とりあえず書いてみた（汗）

MAX_SIZE = 2147483647  # sys.maxsize

def make_distance_dict():

    def all_cells():
        # すべての点を列挙
        for y in range(8):
            for x in range(8):
                yield x, y

    def can_move(p1, p2):
        # ナイトが移動可能かどうか
        dx = abs(p1[0] - p2[0])
        dy = abs(p1[1] - p2[1])
        return (dx == 1 and dy == 2) or (dx == 2 and dy == 1)

    result = dict()

    # 初期化（一手で移動可能な点と点の距離を設定）
    for i in all_cells():
        for j in all_cells():
            # 移動可能なら1、不可ならMAX_SIZE
            result[(i, j)] = 1 if can_move(i, j) else MAX_SIZE

    # 3重ループで、すべての点と点の最短距離が計算できる
    for k in all_cells():
        for i in all_cells():
            for j in all_cells():
                # 点i→jの距離と、点i→k→jの距離の短い方を採用
                result[(i, j)] = min(result[(i, j)], result[(i, k)] + result[(k, j)])

    return result

まず、点と点の距離を記録するために辞書(dict)を作成する。Keyが2つの点、Valueが2点間の最短距離となる。

次に、辞書を初期化する。ナイトが一手で移動できるなら距離=1、移動不可なら無限大と設定する。今回は、無限大の代わりに非常に大きな数字（sys.maxsize）を使う。と思ったら、checkioでは、import sys ができなかったので、MAX_SIZEを定義しておいた。

最後に、3重ループで最短距離を求めていく。
i から j に移動するとき、k を経由する方が短くなるなら、そちらを最短距離として辞書を更新する。これをすべての点について行うだけで、すべての点と点の最短距離が計算できている、という仕組み。わかるような、わからないような話だ。

上のコードでは、すべての点(64マス)×すべての点(64マス)の全組み合わせを計算しているが、点A→Bの距離と、点B→Aの距離は同じなので、もっと工夫すれば無駄は減らせると思う。

辞書を作成したら、スタートとゴールの2点をKeyにしてValueを取り出すだけ。

distances = make_distance_dict()

def checkio(move):
    def parse(s):
        x = 'abcdefgh'
        y = '12345678'
        return (x.index(s[0]), y.index(s[1])), (x.index(s[3]), y.index(s[4]))

    start, goal = parse(move)
    return distances[(start, goal)]

こちらもCheckiOで公開しておいた。

追記：修正版

公開してから気付いたが、初期化の部分で、i と j が同じ点なら距離を0にすべきだった。でないと、同じ点の距離、例えば(1,1)から(1,1)への距離が2となってしまう。これが距離 0になるように修正した。（テスト結果には違いはない。）

また、一手で移動可能かどうかを調べる can_move()関数も、setを使ってもっとシンプルに書けた。

return {abs(p1[0] - p2[0]), abs(p1[1] - p2[1])} == {1, 2}

すべての点を列挙するall_cells()もジェネレータ式にしておいた。
itertools.product(range(8), repeat=2) でもいいかな。

Pythonでの無限大

もう一つ、気になったのが、距離＝無限大の代わりに、sys.maxsize（MAX_SIZE) を使ったが、これは適切なんだろうか？
Pythonでは、float('inf') とすれば正の無限大を作成できるらしい。ちょっとテストしてみた。

>>> f = float('inf')
>>> f
inf

>>> f * 2
inf

>>> f - 10
inf

>>> -f
-inf

>>> f - f
nan

>>> min(f, 10)
10

>>> max(f, 10)
inf

なんか面白い。MAX_SIZEではなく float('inf') にしておこう。

修正後のコードはこちら。get_distance() が追加した部分になる。

def make_distance_dict2():

    def all_cells():
        return ((x, y) for y in range(8) for x in range(8))

    def get_distance(p1, p2):
        if p1 == p2:
            return 0
        elif {abs(p1[0] - p2[0]), abs(p1[1] - p2[1])} == {1, 2}:
            return 1
        else:
            return float('inf')

    result = dict()

    for i in all_cells():
        for j in all_cells():
            result[(i, j)] = get_distance(i, j)

    for k in all_cells():
        for i in all_cells():
            for j in all_cells():
                result[(i, j)] = min(result[(i, j)], result[(i, k)] + result[(k, j)])

    return result

だいぶすっきりした。

この修正版をCheckiOで公開すれば良かった・・・。
公開した後に、ちょっと手直ししたくなることって何度もあるけど、CheckiOでは、一度公開したものは削除したり編集できない。何度も似たようなのを公開するのは気が引けるしなぁ。

他の人の答え

この解答が面白かった。キモの部分だけ紹介する。
startが開始地点、finishがゴール地点、available_moves()が次に進めるマスを取得する関数。

visited = set([start])
while finish not in visited:
    visited = set.union(*[available_moves(v) for v in visited])

http://www.checkio.org/mission/shortest-knight-path/publications/Marigold/python-27/first/

set.union()で、1手後に進める場所、2手後に進める場所、、、をどんどんvisitedに追加する。
visitedにゴール地点が入れば終了。
エレガントだ。