ガチホコシミュレータ

グラフノードの記述#

空間の大きさを $N×M$ だとすると、格子点は全部で最大 $NM$ 存在する。グラフ理論的には頂点数が $NM$ あるので、それぞれの頂点を結ぶ辺は最大 $(NM)^2$ 存在することになる。

つまり、空間を表現するのに頂点数 $NM+(NM)^2$ だけのメモリを消費することになる。合計すると $NM×(NM+1)$ になるが、定数倍は無視することが多いので単に $(NM)^2$ で良い。

これは N と M が小さいうちはいいが、ある程度大きくなってくると途端にメモリの消費量が増えることを意味する。頂点があるかどうか、辺があるかどうかは Boolean を使えば 1 ビットで表現できるものの、N = 100、M = 300 くらいになってくると $(NM)^2=900000000$ bit にも達する。

するとこれだけで 100MB 以上もメモリを消費する計算になる。第一、こんな巨大な配列をいちいち初期化していたら時間がかかってしょうがないだろう。

最適化を考える#

とはいえ、よく考えればこんなに巨大なメモリ空間は必要にならないことがわかる。

格子点状のグラフを考えるのであれば、隣接するグラフは高々四つしかないからだ。つまり、頂点数 + 頂点数 × 4 程度のメモリがあれば良いことになる。

するとわずか 18.75KB になる。この程度であれば（それでもかなり大きいメモリ空間にはなるが）まあまあ許容できるだろう。

距離を計算する#

では、格子点の情報が読み込めたとする。

ここでは地点 $P(x1, y1)$ から $Q(x2, y2)$ への距離を求めたいとする。もしも格子点が完全グラフであれば $Abs(x1-x2)+Abs(y1-y2)$ で一発で計算できるのだが、実際には連結していない頂点があるためこの方法では計算できない。

なので以前紹介したダイクストラ法で距離を計算したいと思います。

アルゴリズム#

ダイクストラ法を使うためには頂点、辺、コストの三つの情報が必要です。コストは辺の情報の一つといえるので、実際には意識する必要はありません。

グラフ理論ではグラフは頂点と辺で構成されると定義されることが多い（ $G=(V,E)$ などと表される）のでここでもそれを利用しましょう。

public class Graph {
    public var vertex: [Vertex]

    public init(vertex: [Vertex], edge: [Edge]) {
        self.vertex = vertex
    }
}

public class Edge {
    public var vertices: (Vertex, Vertex)
    public var length: Int

    public init(vertices: (Vertex, Vertex), length: Int) {
        self.vertices = vertices
        self.length = length
    }
}

public class Vertex {
    public var point: CGPoint

    public init(x: Int, y: Int) {
        self.point = CGPoint(x: x, y: y)
    }

    public init(point: CGPoint) {
        self.point = point
    }
}

本来はE -> V × VなのでいちいちEdgeはVertexの情報を持つ必要がないのですが、格子グラフはエッジが一つの頂点あたり高々 4 つしかないので Sparse Graph と考えて良いです。

そのため、バカ正直にE -> V × Vと考えるよりもEdge自体にどことどこの頂点を繋いでいるものかという情報を持たせたほうが楽です。

あとはこれらのクラスに対してダイクストラ法を適用します。