Swift モバイル ゲーム開発に適用される幅優先探索アルゴリズム

[51CTO.com クイック翻訳] Swift Algorithm Club (https://github.com/raywenderlich/swift-algorithm-club) は、Swift 言語を使用していくつかの一般的に使用されるアルゴリズムとデータ構造を実装することを目的としたオープンソース プロジェクトです。

SAC チームは毎月、www.raywenderlich.com の Web サイトでチュートリアルの形式で優れたデータ構造またはアルゴリズムを公開します。したがって、Swift 言語で実装されたアルゴリズムとデータ構造について詳しく知りたい場合は、いつでもこの Web サイトをチェックしてください。

このチュートリアルでは、古典的な検索および経路探索アルゴリズムである幅優先探索アルゴリズムについて学習します。

幅優先探索アルゴリズムは、もともと Chris Pilcher (https://github.com/chris-pilcher) によって実装されました。このチュートリアルでは、必要に応じて実装形式を少しリファクタリングします。

このチュートリアルでは、Swift 言語に基づくグラフ理論における隣接リスト アルゴリズム (https://www.raywenderlich.com/152046/swift-algorithm-club-graphs-adjacency-list) とキュー アルゴリズム (https://www.raywenderlich.com/148141/swift-algorithm-club-swift-queue-data-structure) を既に知っているか、同様の基本知識があることを前提としています。

なお、Swift Algorithm Club に興味があり、初めて参加する場合は、このアドレス https://www.raywenderlich.com/135533/join-swift-algorithm-club にアクセスしてください。

はじめる

Swift グラフ隣接リスト アルゴリズム (https://www.raywenderlich.com/152046/swift-algorithm-club-graphs-adjacency-list) では、グラフ内のオブジェクトとそれらの間の関係を記述する方法を提案しました。グラフでは、各オブジェクトは頂点として表され、各関係はエッジとして表されます。

たとえば、迷路はグラフを使用して記述できます。迷路内の各ジャンクションは頂点で記述でき、ジャンクション間の各通路はエッジを使用して記述できます。

幅優先探索は 1950 年に EF ムーアによって発見されました。このアルゴリズムは迷路を通る経路を見つけるだけでなく、迷路を通る最短経路を見つけるためのものです。この幅優先探索アルゴリズムの背後にある考え方は非常にシンプルです。

• ソース ポイントの周りの一連の移動に対応するすべての位置を検索します。
• 次に、目的地が見つかるまで、この数値を段階的に変更します。

次に、具体的な例を分析してみましょう。

例

迷路の入り口にいると仮定して、下の図を参照してください。

幅優先探索アルゴリズムは次のように動作します。

1. 現在地を検索します。これが目的地であれば、検索を中止してください。

2. 現在地の近隣の場所を検索します。いずれかが目的地である場合、検索は停止します。

3. これらの場所の近隣の場所をすべて検索します。いずれかが目的地である場合、検索は停止します。

4.***、目的地までの経路がある場合、経路が見つかり、出発地からの最小ステップ数で経路が保存されます。探索する場所が尽きてしまったら、目的地に到達する方法はありません。

[注] 幅優先探索アルゴリズムの場合、最短経路とは、ある場所から次の場所に到達するために必要な最小のステップ数を指します。

私たちが示した迷路の例では、幅優先探索アルゴリズムは迷路内の部屋間の通路はすべて同じ長さであると想定していましたが、もちろん実際にはそうではないかもしれません。迷路の最短ルートは、最短距離ではなく、最短方向のリストと考えることができます。

今後のチュートリアルでは、最短距離経路検索アルゴリズムについて説明します。

Swift 幅優先探索アルゴリズム

ここからは、Swift 言語で実装された幅優先探索アルゴリズムを分析していきます。

これを行うには、まずこのチュートリアルの元のソース コード (https://koenig-media.raywenderlich.com/uploads/2017/03/BreadthFirstSearch-Start.playground.zip) をダウンロードしてください。このソース コードには、Swift 言語で実装された隣接リストとキューのデータ構造が提供されています。

[注] Swift で実装されている隣接リストとキューのデータ構造がどのように機能するかを理解したい場合は、コマンド View\Navigators\ Show Project Navigator を使用して関連するコードを分析できます。また、Swift 言語を使用してこれらの隣接リストとキューのチュートリアルを構築する方法を具体的に学習することもできます。

まず、Graphable と呼ばれるプロトコルを定義します。すべてのグラフ データ構造はこのプロトコルに準拠する必要があります。次に、すべてのグラフ タイプに幅優先探索を適用できるようにプロトコルを拡張します。

Graphable プロトコルは次のようになります。

パブリックプロトコルGraphable {
  関連タイプ要素: ハッシュ可能
  var の説明: CustomStringConvertible { get } 
  
  func createVertex(data: Element) -> Vertex<Element>
  func add (_ type: EdgeType、ソース: Vertex<Element>、宛先: Vertex<Element>、重み: Double ?)
  func weight(ソース: Vertex<Element>、宛先: Vertex<Element>) -> Double ?
  func edge(ソース: Vertex<Element>) -> [Edge<Element>]?
 }

上記でダウンロードした初期サンプル プロジェクトの先頭 (import XCPlayground ステートメントの後) に拡張機能を作成します。

拡張子 Graphable {
 public func broadthFirstSearch(ソース: Vertex<Element>、宛先: Vertex<Element>)
  -> [エッジ<要素>]? { 
  
  }
 }

この関数シグネチャを要約してみましょう。

• 2 つの頂点パラメータを受け取る関数が宣言されています。1 つ目はソース ポイント (開始点)、2 つ目は宛先ポイント (宛先) です。この関数は、Edge オブジェクトの形式でルート (ソース ポイントからターゲット位置まで) を返します。
• ルートが存在する場合、そのルートもソートされた形式で保存されることが期待されます。ルートの最初のエッジはソース頂点から始まり、ルートの最後のエッジは宛先頂点で終わります。ルート内の隣接するエッジの各ペアでは、最初のエッジの宛先が 2 番目のエッジのソースと同じ頂点になります。
• 出発地と目的地が同じ場合、ルートは空の配列になります。
• ルートが存在しない場合は、関数は nil を返す必要があります。

幅優先探索は、正しい順序で頂点を訪問することに依存します。最初に訪問する頂点は常にソース頂点に対応します。その後、ソース ポイントの近傍を分析します。頂点を訪れるたびに、そのノードをキューの後ろに追加します。

キューについてはすでに知っているので、ここでそれを使用できます。

したがって、上記の関数を次のように更新できます。

 public func broadthFirstSearch(ソース: Vertex<Element>、宛先: Vertex<Element>)
 -> [エッジ<要素>]? { 
  
 var キュー = キュー<頂点<要素>>()
  queue.enqueue(ソース) // 1 
  
  訪問した頂点をqueue.dequeue()とすると、2
    訪問頂点 == 目的地の場合 // 3
戻る[]
    }
    // やるべきこと...
  }
 nilを返す// 4 
  
 }

次に、上記のコードを段階的に分析してみましょう。

1. まず、頂点キューを作成し、ソース ポイントをキューに追加します。

2. キューから頂点をデキューし (キューが空でない限り)、それを訪問済み頂点と呼びます。

3. 最初の反復では、訪問した頂点がソース頂点になり、キューはすぐに空になります。ただし、ソース ノードにアクセスしてさらにノードが追加された場合は、検索は続行されます。

4. 訪問した頂点がターゲット頂点であるかどうかを確認します。そうであれば、検索は直ちに終了します。現在のケースでは、空のリストが返されます。これは、ターゲット ノードが見つかったときと同じです。その後、より詳細なラインが構築されます。

5. キューが空の場合は nil を返します。これは、ターゲット ノードが見つからなかったことを意味します。ターゲット ノードへのパスが存在しない可能性があります。

次に、訪問したノードのすべての隣接ノードをキューに追加する必要があります。これを行うには、次のコードを使用できます。

 neighborEdges = edges( from : visitsVertex) とします。?? [] // 1
隣接エッジ内のエッジの場合{
  キュー.エンキュー(エッジ.宛先)
 } // 2

詳細な分析をしてみましょう。

1. ここでは、Graphable プロトコルの edges(from:) 関数を使用して、訪問したノードのエッジ配列を取得します。 edge(from:) 関数はオプションのエッジの配列を返すことに注意してください。つまり、配列が空または nil の場合、このノードから始まるエッジは存在しません。

(検索の目的では) 空のリストは nil と同じ意味 (キューに入れる隣接要素がない) なので、空のリストを使用してオプション配列を nil 集約し、オプション機能を削除します。

2. これで、for ループを使用してエッジ リストを安全に反復処理し、各エッジのターゲット ノードをキューに追加できるようになりました。

現時点では、私たちの使命はまだ完全には達成されていません。実は、この検索アルゴリズムには微妙な危険があります。この例で検索アルゴリズムを実行すると、どのような問題が発生するでしょうか。ここでは、宝物室がグラフに接続されていないという事実は無視できます。

頂点を訪れるたびに何が起こるかを手動で把握したほうがよいでしょう。

この例で検索アルゴリズムを実行すると、どのような問題が発生するでしょうか? 答えは次のとおりです。

1. 幅優先探索アルゴリズムはキューを作成し、入口の部屋をキューに入れます。

2. while ループに初めて入ると、エントリ ルームをキューから削除して訪問します。玄関の部屋には宝物がないので、玄関の部屋の隣の部屋をすべて探索することができます。玄関の隣の部屋には「スパイダールーム」という部屋があります。そこで、それをキューに入れました。

3. while ループに 2 回目に入るときに、スパイダー ルームをキューから外して訪問します。蜘蛛の部屋には宝物がないので、蜘蛛の部屋の隣の部屋を全てさらに探索します。スパイダールームには隣の部屋であるエントランスルームがあるので、それをキューに入れました。

4. while ループに 3 回目に入ると、エントランス ルームをキューから外します...

問題は、私たちが以前にもこの状況に陥ったことがあるということです。

これを修正するには、どの頂点にアクセスしたかを記録して、同じ頂点に再度アクセスしないようにする必要があります。

この問題を解決する方法はいくつかあります。次のようにコードを更新できます。

 public func broadthFirstSearch(ソース: Vertex<Element>、宛先: Vertex<Element>) -> [Edge<Element>]? {
  var キュー = キュー<頂点<要素>>()
  queue.enqueue(ソース)
  var enqueuedVertices = Set <Vertex<Element>>() // 1 
  
  訪問した頂点をqueue.dequeue()で指定します。
    訪問頂点 == 目的地の場合 {
戻る[]
    }
   隣接エッジをエッジ(訪問した頂点から)とします。?? []
隣接エッジ内のエッジの場合{
      if !enqueuedVertices.contains ( edge.destination ) { // 2
        enqueuedVertices.insert (訪問した頂点) // 3
        キュー.エンキュー(エッジ.宛先)
      }
    }
  }
ゼロを返す
}

何が変わったのか確認してみましょう:

1. 上記のコードは、これまでに遭遇した頂点のリストを記述する頂点配列を作成します。 Vertex タイプは Hashable なので、頂点セットを構築するためにこれ以上の作業を行う必要はありません。

2. 隣接する頂点をチェックするときは、まずそのノードが以前に検出されたことがあるかどうかを確認します。

3. 以前にノードに遭遇したことがない場合は、処理する頂点のリスト (キュー構造) と遭遇した頂点のリスト (enqueuedVertices) の 2 つのキューに追加します。

これは、上記の検索アルゴリズムが非常に安全であることを意味します。ただし、グラフ内の開始した頂点よりも多くの頂点をまだ訪問することはできないため、検索は最終的に終了する必要があります。

発見ループ

アルゴリズムはほぼ完成しました!

ここまでで、宛先が見つからない場合は nil 値を返すことが既にわかりました。しかし、目的地を見つけたら、戻る道を見つける必要があります。残念ながら、訪問した部屋はすべてすでにキューから外れているため、目的地を見つける方法が記録されません。

検索情報を記録するには、検索した頂点のセットを、検索した頂点に関するすべての情報と、その頂点に到達した方法を含む辞書構造に置き換える必要があります。これを迷路を探検するようなものと考えてください。探検したすべての部屋を指す矢印が付いたチョーク マーカーを使用します。こうすることで、入り口にたどり着くために必要なすべての情報を思い出すことができます。

すべての矢印を追跡しておけば、訪問したどの部屋でも、そこに到達するためにたどった端を見つけることができます。こちら側は先ほど訪れた部屋に戻ります。もちろん、そこに到達するためにたどったエッジを見つけることもできます。これを繰り返して、開始エッジに到達するまで続けます。

このアイデアを試してみましょう。次の Visit 列挙型を作成します。 Swift 3 はネストされたジェネリック型をサポートしていないため、この型は Graphable 拡張機能の外部で作成する必要があることに注意してください。

 enum Visit<要素: ハッシュ可能> {
ケースソース
ケースエッジ(Edge<要素>)
 }

ルックアップ テーブルでは、最初の列のすべての項目が頂点ですが、2 番目の列のすべての項目がエッジであるわけではありません。頂点は常にソース頂点です。そうでない場合、何かひどい問題が発生し、グラフから抜け出すことができなくなります。

次に、メソッドを次のように変更します。

 public func broadthFirstSearch(ソース: Vertex<Element>、宛先: Vertex<Element>) -> [Edge<Element>]? {
  var キュー = キュー<頂点<要素>>()
  queue.enqueue(ソース)
  var visits : [Vertex<Element> : Visit<Element>] = [source: .source] // 1 
  
  訪問した頂点をqueue.dequeue()で指定します。
    // TODO: これを置き換えます...
    訪問頂点 == 目的地の場合 {
戻る[]
    }
    隣接エッジをエッジ(訪問した頂点から)とします。?? []
隣接エッジ内のエッジの場合{
      visits[edge.destination] == nilの場合 // 2
        キュー.エンキュー(エッジ.宛先)
        訪問[edge.destination] = .edge(edge) // 3
      }
    }
  }
 nilを返す
}

上記のコードで何が変更されたかを確認してみましょう。

1. これは、頂点のキーと訪問の値を持つ辞書を作成し、「ソースポイント」からの訪問としてソース頂点で初期化します。

2. 辞書内に頂点に対応するエントリがない場合、その頂点はキューに追加されていないことを意味します。

3. 頂点をキューに追加するたびに、頂点を頂点のセットに追加するだけでなく、その頂点に到達するエッジも記録します。

*** ターゲットからエントリ ポイントまでバックトラックできます。そして、TODO コメントの実際のコードで if ステートメントを更新します。

訪問頂点 == 目的地の場合 {
  var vertex = destination // 1
  var ルート: [Edge<Element>] = [] // 2 
  
  visit = visits[頂点]とすると、
 case .edge(let edge) = visit { // 3 
  
    ルート = [エッジ] + ルート
    頂点 = edge.source // 4 
  
  }
復路// 5
 }

上記のコードを分析してみましょう。

1. まず、ルートの一部である各頂点を格納するための新しい変数を作成します。

2.ルートを保存する変数も作成します。

3. while ループを作成します。アクセス ディクショナリに頂点エントリがあり、このエントリがエッジである限り、ループは継続されます。エントリがソースの場合、while ループは終了します。

4. ルートの先頭にエッジを追加し、頂点をエッジのソースとして設定します。これで、始まりに一歩近づきました。

5.while ループが終了するので、ルートも完了する必要があります。

[[185897]]

これまでのところ、すべての問題は解決しました。サンプル プロジェクト ファイルの最後に次のコードを追加してテストすることができます。

エッジを dungeon.breadthFirstSearch( from : enteringRoom, to : treasureRoom) とすると、
エッジ内のエッジの場合{
    print( "\(edge.source) -> \(edge.destination)" )
  }
 }

したがって、コンソールに次の出力が表示されるはずです。

入り口 -> ネズミ
 
ネズミ -> 宝物

まとめ

Swift での幅優先探索に関するこのチュートリアルを楽しんでいただければ幸いです。

このチュートリアルでは、すべての Graphable データ型の動作を拡張して、任意の頂点から他の任意の頂点へのルートを検索できるようにしました。さらに良いことに、最も少ないステップでルートを取得できます。

上記のすべてのコードを含む改良されたサンプル プロジェクトのソース コードは、https://koenig-media.raywenderlich.com/uploads/2017/03/BreadthFirstSearch-Final.playground.zip からダウンロードできます。オリジナルの幅優先探索アルゴリズムのオリジナルの実装は、Swift Algorithm Club リポジトリで見つけることができ、さらに議論に参加することもできます。

実際、このアルゴリズムは Swift Algorithm Club リポジトリのほんの一部にすぎません。興味のある読者は、これらのコード ライブラリ (https://github.com/raywenderlich/swift-algorithm-club) をさらに参照できます。

[51CTOによる翻訳。パートナーサイトに転載する場合は、元の翻訳者と出典を51CTO.comとして明記してください]