🐧 👩🏽‍🔬 👨‍🏭 アルゴリズムAの実装* 🚝 👩‍🍳 ☺️

この記事は、A *アルゴリズムの紹介の続きです。その中で、幅優先検索、ダイクストラのアルゴリズム、最適な最初の一致を求める貪欲な検索、およびA *の実装方法を示しました。説明をできる限り簡素化しようとしました。

グラフ検索は、類似のアルゴリズムのファミリーです。アルゴリズムとその実装には多くのバリエーションがあります。この記事のコードは、アルゴリズムの最終バージョンではなく、すべての状況に適した開始点として扱います。

1. Pythonの実装

以下では、ほとんどのコードについて説明します。 implementation.pyファイルは少し広くなっています。コードはPython 3を使用するため、Python 2を使用する場合は、呼び出しをsuper()

に変更し、 print

関数をPython 2の類似物に変更する必要があります。

1.1ワイド検索

Pythonで幅優先検索を実装しましょう。最初の記事では、検索アルゴリズムのPythonコードを示していますが、使用するグラフを決定する必要もあります。私が使用するいくつかの抽象化を以下に示します。

グラフ ：各ポイントの近傍をレポートできるデータ構造（このチュートリアルを参照）

ポイント（場所） ：グラフ内のポイントをマークする単純な値（int、string、tupleなど）

検索：グラフ、開始点、および（オプションで）一部またはすべての点の有用な情報（訪問、親要素へのポインター、距離）を計算する終了点を受け取るアルゴリズム

キュー ：検索アルゴリズムがポイントの処理順序を選択するために使用するデータ構造。

最初の記事では、私は主に検索について見てきました。この記事では、完全に機能するプログラムを作成するために必要な他のすべてを説明します。 グラフから始めましょう：

 class SimpleGraph: def __init__(self): self.edges = {} def neighbors(self, id): return self.edges[id]

はい、必要なのはそれだけです！あなたは尋ねることができます：ノードオブジェクト（ノード）はどこですか？回答：ノードオブジェクトはほとんど使用しません。整数、文字列、またはタプルをポイントとして使用し、配列またはハッシュテーブルを使用してポイントをインデックスとして使用する方が簡単なようです。

エッジには方向があることに注意してください：AからBのエッジを使用できますが、BからAのエッジは使用できません。ゲームカードでは、エッジは主に双方向ですが、場合によっては一方向のドアまたは棚からのジャンプがあり、これは有向エッジとして指定されます。 ポイントが文字AEで示されるグラフの例を作成してみましょう。

各ポイントについて、それが導くポイントのリストが必要です。

 example_graph = SimpleGraph() example_graph.edges = { 'A': ['B'], 'B': ['A', 'C', 'D'], 'C': ['A'], 'D': ['E', 'A'], 'E': ['B'] }

検索アルゴリズムを使用する前に、 キューを設定する必要があります。

 import collections class Queue: def __init__(self): self.elements = collections.deque() def empty(self): return len(self.elements) == 0 def put(self, x): self.elements.append(x) def get(self): return self.elements.popleft()

このキュークラスは、組み込みのcollections.deque

クラスの単なるラッパーです。コードでdeque

直接使用できます。

このキューと前の記事の幅優先の検索コードでグラフの例を使用してみましょう。

 from implementation import * def breadth_first_search_1(graph, start): #  ,    frontier = Queue() frontier.put(start) visited = {} visited[start] = True while not frontier.empty(): current = frontier.get() print("Visiting %r" % current) for next in graph.neighbors(current): if next not in visited: frontier.put(next) visited[next] = True breadth_first_search_1(example_graph, 'A')

Visiting 'A' 
      

        
        
        
      

     Visiting 'B' 
      

        
        
        
      

     Visiting 'C' 
      

        
        
        
      

     Visiting 'D' 
      

        
        
        
      

     Visiting 'E'

グリッドはグラフとして表現することもできます。次に、タプルの（int、int） ポイントを使用して、新しいSquareGrid

グラフを定義します。エッジを明示的に保存する代わりに、 neighbors

関数でエッジを計算します。

 class SquareGrid: def __init__(self, width, height): self.width = width self.height = height self.walls = [] def in_bounds(self, id): (x, y) = id return 0 <= x < self.width and 0 <= y < self.height def passable(self, id): return id not in self.walls def neighbors(self, id): (x, y) = id results = [(x+1, y), (x, y-1), (x-1, y), (x, y+1)] if (x + y) % 2 == 0: results.reverse() #   results = filter(self.in_bounds, results) results = filter(self.passable, results) return results

前の記事の最初のグリッドでテストしてみましょう。

 from implementation import * g = SquareGrid(30, 15) g.walls = DIAGRAM1_WALLS #  long, [(21, 0), (21, 2), ...] draw_grid(g)

. . . . . . . . . . . . . . . . . . . . . ####. . . . . . . 
      

        
        
        
      

     . . . . . . . . . . . . . . . . . . . . . ####. . . . . . . 
      

        
        
        
      

     . . . . . . . . . . . . . . . . . . . . . ####. . . . . . . 
      

        
        
        
      

     . . . ####. . . . . . . . . . . . . . . . ####. . . . . . . 
      

        
        
        
      

     . . . ####. . . . . . . . ####. . . . . . ####. . . . . . . 
      

        
        
        
      

     . . . ####. . . . . . . . ####. . . . . . ##########. . . . 
      

        
        
        
      

     . . . ####. . . . . . . . ####. . . . . . ##########. . . . 
      

        
        
        
      

     . . . ####. . . . . . . . ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . . . ####. . . . . . . . ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . . . ####. . . . . . . . ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . . . ####. . . . . . . . ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . . . ####. . . . . . . . ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . . . . . . . . . . . . . ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . . . . . . . . . . . . . ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . . . . . . . . . . . . . ####. . . . . . . . . . . . . . .

パスを再作成するには、元のポイントを保存する必要があるため、 visited

（True / False）をcame_from

（point）に変更しました。

 from implementation import * def breadth_first_search_2(graph, start): #  "came_from" frontier = Queue() frontier.put(start) came_from = {} came_from[start] = None while not frontier.empty(): current = frontier.get() for next in graph.neighbors(current): if next not in came_from: frontier.put(next) came_from[next] = current return came_from g = SquareGrid(30, 15) g.walls = DIAGRAM1_WALLS parents = breadth_first_search_2(g, (8, 7)) draw_grid(g, width=2, point_to=parents, start=(8, 7))

→ → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ####↓ ↓ ↓ ↓ ↓ ↓ ↓ 
      

        
        
        
      

     → → → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ← ####↓ ↓ ↓ ↓ ↓ ↓ ↓ 
      

        
        
        
      

     → → → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ← ← ####→ ↓ ↓ ↓ ↓ ↓ ↓ 
      

        
        
        
      

     → → ↑ ####↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ← ← ← ####→ → ↓ ↓ ↓ ↓ ↓ 
      

        
        
        
      

     → ↑ ↑ ####→ ↓ ↓ ↓ ↓ ↓ ↓ ← ####↑ ← ← ← ← ← ####→ → → ↓ ↓ ↓ ↓ 
      

        
        
        
      

     ↑ ↑ ↑ ####→ → ↓ ↓ ↓ ↓ ← ← ####↑ ↑ ← ← ← ← ##########↓ ↓ ↓ ← 
      

        
        
        
      

     ↑ ↑ ↑ ####→ → → ↓ ↓ ← ← ← ####↑ ↑ ↑ ← ← ← ##########↓ ↓ ← ← 
      

        
        
        
      

     ↑ ↑ ↑ ####→ → → A ← ← ← ← ####↑ ↑ ↑ ↑ ← ← ← ← ← ← ← ← ← ← ← 
      

        
        
        
      

     ↓ ↓ ↓ ####→ → ↑ ↑ ↑ ← ← ← ####↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ← ← ← ← ← 
      

        
        
        
      

     ↓ ↓ ↓ ####→ ↑ ↑ ↑ ↑ ↑ ← ← ####↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ← ← ← ← 
      

        
        
        
      

     ↓ ↓ ↓ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ← ← ← 
      

        
        
        
      

     → ↓ ↓ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ← ← 
      

        
        
        
      

     → → → → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ← 
      

        
        
        
      

     → → → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ← 
      

        
        
        
      

     → → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ←

一部の実装では、Nodeオブジェクトを作成することにより、グラフ内の各ノードのcame_from

およびその他の値を格納するために内部ストレージが使用されます。代わりに、 外部ストレージを使用して、グラフ内のすべてのノードからcame_from

を格納する単一のハッシュテーブルを作成することにしました。マップ上のポイントに整数インデックスがあることがわかっている場合は、別のオプションがあります-配列を使用してcame_from

を格納しcame_from

。

1.2早期退出

前の記事のコードを繰り返して、メインループにifコンストラクトを追加するだけです。このチェックは幅優先検索とダイクストラのアルゴリズムではオプションですが、最適な最初の一致とA *の貪欲な検索では必須です。

 from implementation import * def breadth_first_search_3(graph, start, goal): frontier = Queue() frontier.put(start) came_from = {} came_from[start] = None while not frontier.empty(): current = frontier.get() if current == goal: break for next in graph.neighbors(current): if next not in came_from: frontier.put(next) came_from[next] = current return came_from g = SquareGrid(30, 15) g.walls = DIAGRAM1_WALLS parents = breadth_first_search_3(g, (8, 7), (17, 2)) draw_grid(g, width=2, point_to=parents, start=(8, 7), goal=(17, 2))

. → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← . . . . ####. . . . . . . 
      

        
        
        
      

     → → → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← . . . ####. . . . . . . 
      

        
        
        
      

     → → → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← Z . . . ####. . . . . . . 
      

        
        
        
      

     → → ↑ ####↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ← . . ####. . . . . . . 
      

        
        
        
      

     . ↑ ↑ ####→ ↓ ↓ ↓ ↓ ↓ ↓ ← ####↑ ← ← . . . ####. . . . . . . 
      

        
        
        
      

     . . ↑ ####→ → ↓ ↓ ↓ ↓ ← ← ####↑ ↑ . . . . ##########. . . . 
      

        
        
        
      

     . . . ####→ → → ↓ ↓ ← ← ← ####↑ . . . . . ##########. . . . 
      

        
        
        
      

     . . . ####→ → → A ← ← ← ← ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . . . ####→ → ↑ ↑ ↑ ← ← ← ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . . ↓ ####→ ↑ ↑ ↑ ↑ ↑ ← ← ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . ↓ ↓ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     → ↓ ↓ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     → → → → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     → → → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####. . . . . . . . . . . . . . .

ご覧のとおり、アルゴリズムはターゲットZ

見つけると停止しZ

1.3ダイクストラのアルゴリズム

これはアルゴリズムの複雑さを増します。「先着順」だけでなく、改善された順序でポイントの処理を開始するからです。どの原則を使用しますか？

カウントは移動のコストを知る必要があります。
キューはノードを異なる順序で返す必要があります。
検索はグラフでこの値を追跡し、キューに渡す必要があります。

1.3.1重み付きカウント

ポイントfrom_node

から隣接するto_node

に移動するコストを伝える関数cost(from_node, to_node)

を追加します。このフォレストマップでは、移動はto_node

のみに依存することを決定しましたが、両方のノードを使用する他のタイプの移動があります。実装の代替方法は、 neighbors

関数にマージすることです。

 class GridWithWeights(SquareGrid): def __init__(self, width, height): super().__init__(width, height) self.weights = {} def cost(self, from_node, to_node): return self.weights.get(to_node, 1)

1.3.2優先度キュー

優先度キューは、各要素に「優先度」と呼ばれる番号を関連付けます。アイテムが返されると、最も小さい番号のアイテムが選択されます。

insert ：アイテムをキューに追加します

remove ：最小の番号を持つ要素を削除します

reprioritize ：（オプション）既存のアイテムの優先度を低い数値に変更します。

これは、 バイナリヒープを使用しますが、reprioritizeではサポートされない、かなり高速な優先度キューです。正しい順序を取得するには、タプル（優先順位、要素）を使用します。すでにキューにあるアイテムを挿入すると、重複します。最適化セクションでこれが私たちに適している理由を説明します。

 import heapq class PriorityQueue: def __init__(self): self.elements = [] def empty(self): return len(self.elements) == 0 def put(self, item, priority): heapq.heappush(self.elements, (priority, item)) def get(self): return heapq.heappop(self.elements)[1]

1.3.3検索

ここには実装のトリッキーな瞬間があります。移動のコスト、つまり、より良いcost_so_far

を持つポイントへの繰り返し訪問の確率を追加するからcost_so_far

。これはif next not in came_from

にないif next not in came_from

が機能しないことを意味します。代わりに、最後の訪問以降にコストが減少したかどうかを確認する必要があります。（記事の元のバージョンではこれをチェックしませんでしたが、コードはとにかく機能しました。このエラーに関するメモを書きました。）

この森林地図は前の記事から取られました。

 def dijkstra_search(graph, start, goal): frontier = PriorityQueue() frontier.put(start, 0) came_from = {} cost_so_far = {} came_from[start] = None cost_so_far[start] = 0 while not frontier.empty(): current = frontier.get() if current == goal: break for next in graph.neighbors(current): new_cost = cost_so_far[current] + graph.cost(current, next) if next not in cost_so_far or new_cost < cost_so_far[next]: cost_so_far[next] = new_cost priority = new_cost frontier.put(next, priority) came_from[next] = current return came_from, cost_so_far

検索後、パスを作成する必要があります。

 def reconstruct_path(came_from, start, goal): current = goal path = [current] while current != start: current = came_from[current] path.append(current) path.append(start) #  path.reverse() #  return path

パスはエッジのシーケンスとして最もよく理解されますが、ノードのシーケンスとして保存する方が便利です。パスを作成するには、最後から始めて、前のノードを指すcame_from

マップに従います。最初に到達すると、仕事は完了です。これが戻りパスです。したがって、 reconstruct_path

の最後で、直接シーケンスで格納する必要がある場合は、 reverse()

を呼び出します。実際、パスを逆に保存する方が便利な場合があります。さらに、開始ノードをリストに保存すると便利な場合があります。

試してみましょう：

 from implementation import * came_from, cost_so_far = dijkstra_search(diagram4, (1, 4), (7, 8)) draw_grid(diagram4, width=3, point_to=came_from, start=(1, 4), goal=(7, 8)) print() draw_grid(diagram4, width=3, number=cost_so_far, start=(1, 4), goal=(7, 8)) print() draw_grid(diagram4, width=3, path=reconstruct_path(came_from, start=(1, 4), goal=(7, 8)))

↓ ↓ ← ← ← ← ← ← ← ← 
      

        
        
        
      

     ↓ ↓ ← ← ← ↑ ↑ ← ← ← 
      

        
        
        
      

     ↓ ↓ ← ← ← ← ↑ ↑ ← ← 
      

        
        
        
      

     ↓ ↓ ← ← ← ← ← ↑ ↑ . 
      

        
        
        
      

     → A ← ← ← ← . . . . 
      

        
        
        
      

     ↑ ↑ ← ← ← ← . . . . 
      

        
        
        
      

     ↑ ↑ ← ← ← ← ← . . . 
      

        
        
        
      

     ↑ #########↑ ← ↓ . . . 
      

        
        
        
      

     ↑ #########↓ ↓ ↓ Z . . 
      

        
        
        
      

     ↑ ← ← ← ← ← ← ← ← . 
      

        
        
        
      

     
      

        
        
        
      

     5 4 5 6 7 8 9 10 11 12 
      

        
        
        
      

     4 3 4 5 10 13 10 11 12 13 
      

        
        
        
      

     3 2 3 4 9 14 15 12 13 14 
      

        
        
        
      

     2 1 2 3 8 13 18 17 14 . 
      

        
        
        
      

     1 A 1 6 11 16 . . . . 
      

        
        
        
      

     2 1 2 7 12 17 . . . . 
      

        
        
        
      

     3 2 3 4 9 14 19 . . . 
      

        
        
        
      

     4 #########14 19 18 . . . 
      

        
        
        
      

     5 #########15 16 13 Z . . 
      

        
        
        
      

     6 7 8 9 10 11 12 13 14 . 
      

        
        
        
      

     
      

        
        
        
      

     . . . . . . . . . . 
      

        
        
        
      

     . . . . . . . . . . 
      

        
        
        
      

     . . . . . . . . . . 
      

        
        
        
      

     . . . . . . . . . . 
      

        
        
        
      

     @ @ . . . . . . . . 
      

        
        
        
      

     @ . . . . . . . . . 
      

        
        
        
      

     @ . . . . . . . . . 
      

        
        
        
      

     @ #########. . . . . . 
      

        
        
        
      

     @ #########. . @ @ . . 
      

        
        
        
      

     @ @ @ @ @ @ @ . . .

if next not in cost_so_far or new_cost < cost_so_far[next]

の行if next not in cost_so_far or new_cost < cost_so_far[next]

if new_cost < cost_so_far.get(next, Infinity)

に簡略化できますが、前回の記事でget()

Pythonを説明したくなかったので、そのままにしました。また、 collections.defaultdict

をデフォルトの無限値で使用することもできます。

1.4検索A *

最適な最初の一致の貪欲な検索とA *の両方で、ヒューリスティック関数が使用されます。唯一の違いは、A *がヒューリスティックとダイクストラのアルゴリズムの順序の両方を使用することです。ここでA *を表示します。

 def heuristic(a, b): (x1, y1) = a (x2, y2) = b return abs(x1 - x2) + abs(y1 - y2) def a_star_search(graph, start, goal): frontier = PriorityQueue() frontier.put(start, 0) came_from = {} cost_so_far = {} came_from[start] = None cost_so_far[start] = 0 while not frontier.empty(): current = frontier.get() if current == goal: break for next in graph.neighbors(current): new_cost = cost_so_far[current] + graph.cost(current, next) if next not in cost_so_far or new_cost < cost_so_far[next]: cost_so_far[next] = new_cost priority = new_cost + heuristic(goal, next) frontier.put(next, priority) came_from[next] = current return came_from, cost_so_far

試してみましょう：

 from implementation import * came_from, cost_so_far = a_star_search(diagram4, (1, 4), (7, 8)) draw_grid(diagram4, width=3, point_to=came_from, start=(1, 4), goal=(7, 8)) print() draw_grid(diagram4, width=3, number=cost_so_far, start=(1, 4), goal=(7, 8))

. . . . . . . . . . 
      

        
        
        
      

     . ↓ ↓ ↓ . . . . . . 
      

        
        
        
      

     ↓ ↓ ↓ ↓ ← . . . . . 
      

        
        
        
      

     ↓ ↓ ↓ ← ← . . . . . 
      

        
        
        
      

     → A ← ← ← . . . . . 
      

        
        
        
      

     → ↑ ← ← ← . . . . . 
      

        
        
        
      

     → ↑ ← ← ← ← . . . . 
      

        
        
        
      

     ↑ #########↑ . ↓ . . . 
      

        
        
        
      

     ↑ #########↓ ↓ ↓ Z . . 
      

        
        
        
      

     ↑ ← ← ← ← ← ← ← . . 
      

        
        
        
      

     
      

        
        
        
      

     . . . . . . . . . . 
      

        
        
        
      

     . 3 4 5 . . . . . . 
      

        
        
        
      

     3 2 3 4 9 . . . . . 
      

        
        
        
      

     2 1 2 3 8 . . . . . 
      

        
        
        
      

     1 A 1 6 11 . . . . . 
      

        
        
        
      

     2 1 2 7 12 . . . . . 
      

        
        
        
      

     3 2 3 4 9 14 . . . . 
      

        
        
        
      

     4 #########14 . 18 . . . 
      

        
        
        
      

     5 #########15 16 13 Z . . 
      

        
        
        
      

     6 7 8 9 10 11 12 13 . .

1.4.1直線パス

独自のプロジェクトにこのコードを実装すると、一部のパスが希望どおりの「直接」ではないことがわかります。 これは正常です。 グリッド 、特に各ステップの移動コストが同じグリッドを使用する場合、 同等のオプションが得られます。多くのパスのコストはまったく同じです。 *は多くのショートカットの1つを選択しますが、非常にきれいに見えないことが非常に多くあります 。同等のオプションを排除するクイックハックを適用できますが、常に完全に適切であるとは限りません。マップの表現を変更すると、 A *が大幅に加速され、より直接的で快適なパスが作成されます。ただし、これは、各ステップに1つの移動コストがある静的カードに適しています。私のページのデモでは、簡単なハックを使用していますが、優先度の低いキューでのみ機能します。より高速な優先度キューに切り替える場合は、別のクイックハックが必要です。

2 C ++実装

注：サンプルコードの一部を実行するには、 redblobgames / pathfinding / a-star / implementation.cppを追加します。このコードにはC ++ 11を使用しているため、古いバージョンのC ++標準を使用している場合は、部分的に変更する必要があります。

2.1ワイド検索

最初にPythonセクションを確認してください。このセクションにはコードがありますが、同じ説明はありません。まず、一般的なグラフクラスを追加します。

 template<typename L> struct SimpleGraph { typedef L Location; typedef typename vector<Location>::iterator iterator; unordered_map<Location, vector<Location> > edges; inline const vector<Location> neighbors(Location id) { return edges[id]; } };

char

を使用してポイントをマークするPythonコードの同じグラフの例：

 SimpleGraph<char> example_graph {{ {'A', {'B'}}, {'B', {'A', 'C', 'D'}}, {'C', {'A'}}, {'D', {'E', 'A'}}, {'E', {'B'}} }};

キュークラスを定義する代わりに、C ++標準ライブラリのクラスを使用します。これで、幅優先の検索を試みることができます。

 #include "redblobgames/pathfinding/a-star/implementation.cpp" template<typename Graph> void breadth_first_search(Graph graph, typename Graph::Location start) { typedef typename Graph::Location Location; queue<Location> frontier; frontier.push(start); unordered_set<Location> visited; visited.insert(start); while (!frontier.empty()) { auto current = frontier.front(); frontier.pop(); std::cout << "Visiting " << current << std::endl; for (auto& next : graph.neighbors(current)) { if (!visited.count(next)) { frontier.push(next); visited.insert(next); } } } } int main() { breadth_first_search(example_graph, 'A'); }

コードはPythonよりも少し長くなりますが、これは非常に正常です。

正方形グリッドはどうですか？別のクラスのグラフを定義します。グラフの前のクラスとは関係がないことに注意してください。継承ではなくテンプレートを使用します。グラフは、typedef Location

とneighbors

関数のみを提供する必要があります。

 struct SquareGrid { typedef tuple<int,int> Location; static array<Location, 4> DIRS; int width, height; unordered_set<Location> walls; SquareGrid(int width_, int height_) : width(width_), height(height_) {} inline bool in_bounds(Location id) const { int x, y; tie (x, y) = id; return 0 <= x && x < width && 0 <= y && y < height; } inline bool passable(Location id) const { return !walls.count(id); } vector<Location> neighbors(Location id) const { int x, y, dx, dy; tie (x, y) = id; vector<Location> results; for (auto dir : DIRS) { tie (dx, dy) = dir; Location next(x + dx, y + dy); if (in_bounds(next) && passable(next)) { results.push_back(next); } } if ((x + y) % 2 == 0) { //      std::reverse(results.begin(), results.end()); } return results; } }; array<SquareGrid::Location, 4> SquareGrid::DIRS {Location{1, 0}, Location{0, -1}, Location{-1, 0}, Location{0, 1}};

ヘルパーファイルimplementation.cpp

グリッドをレンダリングするための関数を定義しました。

 #include "redblobgames/pathfinding/a-star/implementation.cpp" int main() { SquareGrid grid = make_diagram1(); draw_grid(grid, 2); }

. . . . . . . . . . . . . . . . . . . . . ####. . . . . . . 
      

        
        
        
      

     . . . . . . . . . . . . . . . . . . . . . ####. . . . . . . 
      

        
        
        
      

     . . . . . . . . . . . . . . . . . . . . . ####. . . . . . . 
      

        
        
        
      

     . . . ####. . . . . . . . . . . . . . . . ####. . . . . . . 
      

        
        
        
      

     . . . ####. . . . . . . . ####. . . . . . ####. . . . . . . 
      

        
        
        
      

     . . . ####. . . . . . . . ####. . . . . . ##########. . . . 
      

        
        
        
      

     . . . ####. . . . . . . . ####. . . . . . ##########. . . . 
      

        
        
        
      

     . . . ####. . . . . . . . ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . . . ####. . . . . . . . ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . . . ####. . . . . . . . ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . . . ####. . . . . . . . ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . . . ####. . . . . . . . ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . . . . . . . . . . . . . ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . . . . . . . . . . . . . ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . . . . . . . . . . . . . ####. . . . . . . . . . . . . . .

came_from

追跡して、幅優先の検索を行いましょう。

 #include "redblobgames/pathfinding/a-star/implementation.cpp" template<typename Graph> unordered_map<typename Graph::Location, typename Graph::Location> breadth_first_search(Graph graph, typename Graph::Location start) { typedef typename Graph::Location Location; queue<Location> frontier; frontier.push(start); unordered_map<Location, Location> came_from; came_from[start] = start; while (!frontier.empty()) { auto current = frontier.front(); frontier.pop(); for (auto& next : graph.neighbors(current)) { if (!came_from.count(next)) { frontier.push(next); came_from[next] = current; } } } return came_from; } int main() { SquareGrid grid = make_diagram1(); auto parents = breadth_first_search(grid, std::make_tuple(7, 8)); draw_grid(grid, 2, nullptr, &parents); }

→ → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ####↓ ↓ ↓ ↓ ↓ ↓ ↓ 
      

        
        
        
      

     → → → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ← ####↓ ↓ ↓ ↓ ↓ ↓ ↓ 
      

        
        
        
      

     → → → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ← ← ####→ ↓ ↓ ↓ ↓ ↓ ↓ 
      

        
        
        
      

     → → ↑ ####↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ← ← ← ####→ → ↓ ↓ ↓ ↓ ↓ 
      

        
        
        
      

     → ↑ ↑ ####↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ####↑ ← ← ← ← ← ####→ → → ↓ ↓ ↓ ↓ 
      

        
        
        
      

     ↑ ↑ ↑ ####↓ ↓ ↓ ↓ ↓ ↓ ← ← ####↑ ↑ ← ← ← ← ##########↓ ↓ ↓ ← 
      

        
        
        
      

     ↑ ↑ ↑ ####→ ↓ ↓ ↓ ↓ ← ← ← ####↑ ↑ ↑ ← ← ← ##########↓ ↓ ← ← 
      

        
        
        
      

     ↓ ↓ ↓ ####→ → ↓ ↓ ← ← ← ← ####↑ ↑ ↑ ↑ ← ← ← ← ← ← ← ← ← ← ← 
      

        
        
        
      

     ↓ ↓ ↓ ####→ → * ← ← ← ← ← ####↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ← ← ← ← ← 
      

        
        
        
      

     ↓ ↓ ↓ ####→ ↑ ↑ ↑ ← ← ← ← ####↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ← ← ← ← 
      

        
        
        
      

     ↓ ↓ ↓ ####↑ ↑ ↑ ↑ ↑ ← ← ← ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ← ← ← 
      

        
        
        
      

     → ↓ ↓ ####↑ ↑ ↑ ↑ ↑ ↑ ← ← ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ← ← 
      

        
        
        
      

     → → → → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ← 
      

        
        
        
      

     → → → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ← 
      

        
        
        
      

     → → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ←

実装によっては、 内部ストレージを使用してNodeオブジェクトを作成し、 came_from

およびグラフ内の各ノードのその他の値を保存します。 外部ストレージを使用して、単一のstd::unordered_map

を作成して、グラフのすべてのノードのcame_from

を保存することをcame_from

ました。マップ上のポイントに整数インデックスがあることがわかっている場合は、別のオプションがあります。1次元または2次元の配列/ベクトルを使用してcame_from

およびその他の値を格納します。

2.1.1 TODO：構造体ポイント

このコードでは、Pythonコードでタプルを使用したため、 std::tuple

C ++を使用します。ただし、タプルはほとんどのC ++プログラマには馴染みがありません。コンストラクター、コピーコンストラクター、代入演算子、およびハッシュ関数との等価比較を定義する必要があるため、{x、y}を使用して構造体を定義するのはもう少し長くなりますが、このコードはほとんどのC ++プログラマーによく知られています。変更する必要があります。

もう1つのオプション（コードで使用）は、{x、y}をint

としてエンコードすることです。 T A *コードに、任意のLocation

タイプではなく、常に整数値の密なセットがある場合、これにより追加の最適化を使用できます。ハッシュテーブルではなく、異なるセットに配列を使用できます。それらのほとんどを初期化せずに残すことができます。毎回再初期化する必要がある配列の場合、A *呼び出しで定数にし（おそらくローカルスレッドストアを使用）、前の呼び出しで使用された配列の部分のみを再初期化できます。これは、エントリーレベルのチュートリアルでは使用したくない、より複雑な手法です。

2.2早期退出

Pythonのバージョンと同様に、関数にパラメーターを追加してメインループを確認するだけです。

 #include "redblobgames/pathfinding/a-star/implementation.cpp" template<typename Graph> unordered_map<typename Graph::Location, typename Graph::Location> breadth_first_search(const Graph& graph, typename Graph::Location start, typename Graph::Location goal) { typedef typename Graph::Location Location; queue<Location> frontier; frontier.push(start); unordered_map<Location, Location> came_from; came_from[start] = start; while (!frontier.empty()) { auto current = frontier.front(); frontier.pop(); if (current == goal) { break; } for (auto& next : graph.neighbors(current)) { if (!came_from.count(next)) { frontier.push(next); came_from[next] = current; } } } return came_from; } int main() { SquareGrid grid = make_diagram1(); auto parents = breadth_first_search(grid, SquareGrid::Location{8, 7}, SquareGrid::Location{17, 2}); draw_grid(grid, 2, nullptr, &parents); }

. → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← . . . . ####. . . . . . . 
      

        
        
        
      

     → → → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← . . . ####. . . . . . . 
      

        
        
        
      

     → → → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← . . . ####. . . . . . . 
      

        
        
        
      

     → → ↑ ####↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ← . . ####. . . . . . . 
      

        
        
        
      

     . ↑ ↑ ####→ ↓ ↓ ↓ ↓ ↓ ↓ ← ####↑ ← ← . . . ####. . . . . . . 
      

        
        
        
      

     . . ↑ ####→ → ↓ ↓ ↓ ↓ ← ← ####↑ ↑ . . . . ##########. . . . 
      

        
        
        
      

     . . . ####→ → → ↓ ↓ ← ← ← ####↑ . . . . . ##########. . . . 
      

        
        
        
      

     . . . ####→ → → * ← ← ← ← ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . . . ####→ → ↑ ↑ ↑ ← ← ← ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . . ↓ ####→ ↑ ↑ ↑ ↑ ↑ ← ← ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . ↓ ↓ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     → ↓ ↓ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     → → → → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     → → → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####. . . . . . . . . . . . . . . 
      

        
        
        
      

     . → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####. . . . . . . . . . . . . . .

2.3ダイクストラのアルゴリズム

2.3.1重み付きカウント

移動のコストが5であるフォレストタイルのリストを持つグリッドがあります。このフォレストマップでは、 to_node

のみにto_node

移動を実行することにしto_node

、両方のノードを使用する他のタイプの移動があります。

 struct GridWithWeights: SquareGrid { unordered_set<Location> forests; GridWithWeights(int w, int h): SquareGrid(w, h) {} double cost(Location from_node, Location to_node) const { return forests.count(to_node) ? 5 : 1; } };

2.3.2優先度キュー

優先キューが必要です。 C ++には、バイナリヒープを使用するpriority_queue

クラスがありますが、優先度の変更操作はありません。キュー要素に正しい順序を取得するためにペア（優先度、要素）を使用しています。デフォルトでは、C ++優先度キューは最初にstd::less

コンパレーターを使用して最大要素を返します。最小限の要素が必要なので、 std::greater

コンパレーターを使用します。

 template<typename T, typename priority_t> struct PriorityQueue { typedef pair<priority_t, T> PQElement; priority_queue<PQElement, vector<PQElement>, std::greater<PQElement>> elements; inline bool empty() const { return elements.empty(); } inline void put(T item, priority_t priority) { elements.emplace(priority, item); } inline T get() { T best_item = elements.top().second; elements.pop(); return best_item; } };

このサンプルコードでは、C ++ std::priority_queue

をラップしていますが、このクラスをラッパーなしで使用するのが賢明だと思います。

2.3.3検索

前の記事の森の地図をご覧ください。

 template<typename Graph> void dijkstra_search (const Graph& graph, typename Graph::Location start, typename Graph::Location goal, unordered_map<typename Graph::Location, typename Graph::Location>& came_from, unordered_map<typename Graph::Location, double>& cost_so_far) { typedef typename Graph::Location Location; PriorityQueue<Location, double> frontier; frontier.put(start, 0); came_from[start] = start; cost_so_far[start] = 0; while (!frontier.empty()) { auto current = frontier.get(); if (current == goal) { break; } for (auto& next : graph.neighbors(current)) { double new_cost = cost_so_far[current] + graph.cost(current, next); if (!cost_so_far.count(next) || new_cost < cost_so_far[next]) { cost_so_far[next] = new_cost; came_from[next] = current; frontier.put(next, new_cost); } } } }

cost

変数のタイプは、グラフで使用されるタイプと一致する必要があります。 int

を使用する場合、優先度キューの可変コストと優先度にint

を使用できます。 double

を使用する場合は、それらにもdouble

を使用する必要があります。このコードではdouble

を使用しましたが、 int

を使用でき、コードは同じように機能します。ただし、グラフのエッジのコストがdoubleで格納されている場合、またはdoubleがヒューリスティックで使用されている場合、ここでdoubleを使用する必要があります。

最後に、検索後、パスを作成する必要があります。

 template<typename Location> vector<Location> reconstruct_path( Location start, Location goal, unordered_map<Location, Location>& came_from ) { vector<Location> path; Location current = goal; path.push_back(current); while (current != start) { current = came_from[current]; path.push_back(current); } path.push_back(start); //  std::reverse(path.begin(), path.end()); return path; }

パスはエッジのシーケンスとして最もよく理解されますが、ノードのシーケンスとして保存すると便利です。パスを作成するには、最後から始めてcame_from

マップに従い、前のノードをcame_from

ます。プロセスは最初に到達すると終了します。これは戻りパスなので、直接保存する場合は、 reconstruct_path

の最後にreverse()

を呼び出す必要があります。パスを逆に保存する方が便利な場合があります。また、開始ノードをリストに保存すると便利な場合があります。

試してみましょう：

 #include "redblobgames/pathfinding/a-star/implementation.cpp" int main() { GridWithWeights grid = make_diagram4(); SquareGrid::Location start{1, 4}; SquareGrid::Location goal{8, 5}; unordered_map<SquareGrid::Location, SquareGrid::Location> came_from; unordered_map<SquareGrid::Location, double> cost_so_far; dijkstra_search(grid, start, goal, came_from, cost_so_far); draw_grid(grid, 2, nullptr, &came_from); std::cout << std::endl; draw_grid(grid, 3, &cost_so_far, nullptr); std::cout << std::endl; vector<SquareGrid::Location> path = reconstruct_path(start, goal, came_from); draw_grid(grid, 3, nullptr, nullptr, &path); }

↓ ↓ ← ← ← ← ← ← ← ← 
      

        
        
        
      

     ↓ ↓ ← ← ← ↑ ↑ ← ← ← 
      

        
        
        
      

     ↓ ↓ ← ← ← ← ↑ ↑ ← ← 
      

        
        
        
      

     ↓ ↓ ← ← ← ← ← ↑ ↑ ← 
      

        
        
        
      

     → * ← ← ← ← ← → ↑ ← 
      

        
        
        
      

     ↑ ↑ ← ← ← ← . ↓ ↑ . 
      

        
        
        
      

     ↑ ↑ ← ← ← ← ← ↓ ← . 
      

        
        
        
      

     ↑ ######↑ ← ↓ ↓ ← . 
      

        
        
        
      

     ↑ ######↓ ↓ ↓ ← ← ← 
      

        
        
        
      

     ↑ ← ← ← ← ← ← ← ← ← 
      

        
        
        
      

     
      

        
        
        
      

     5 4 5 6 7 8 9 10 11 12 
      

        
        
        
      

     4 3 4 5 10 13 10 11 12 13 
      

        
        
        
      

     3 2 3 4 9 14 15 12 13 14 
      

        
        
        
      

     2 1 2 3 8 13 18 17 14 15 
      

        
        
        
      

     1 0 1 6 11 16 21 20 15 16 
      

        
        
        
      

     2 1 2 7 12 17 . 21 16 . 
      

        
        
        
      

     3 2 3 4 9 14 19 16 17 . 
      

        
        
        
      

     4 #########14 19 18 15 16 . 
      

        
        
        
      

     5 #########15 16 13 14 15 16 
      

        
        
        
      

     6 7 8 9 10 11 12 13 14 15 
      

        
        
        
      

     
      

        
        
        
      

     . @ @ @ @ @ @ . . . 
      

        
        
        
      

     . @ . . . . @ @ . . 
      

        
        
        
      

     . @ . . . . . @ @ . 
      

        
        
        
      

     . @ . . . . . . @ . 
      

        
        
        
      

     . @ . . . . . . @ . 
      

        
        
        
      

     . . . . . . . . @ . 
      

        
        
        
      

     . . . . . . . . . . 
      

        
        
        
      

     . #########. . . . . . 
      

        
        
        
      

     . #########. . . . . . 
      

        
        
        
      

     . . . . . . . . . .

優先キューでは組み込みのハッシュテーブルを使用し、ハッシュテーブルの反復順序が一定ではないため、結果はPythonバージョンの結果と完全には一致しません。

2.4検索A *

*は、追加されたヒューリスティック検索を除き、ダイクストラのアルゴリズムをほぼ完全に繰り返します。アルゴリズムコードはグリッドだけでなく使用できることに注意してください。グリッドの知識は、グラフクラス（この場合はSquareGrids

）とheuristic

関数にあります。それらを置き換える場合、アルゴリズムコードA *を他のグラフ構造で使用できます。

 inline double heuristic(SquareGrid::Location a, SquareGrid::Location b) { int x1, y1, x2, y2; tie (x1, y1) = a; tie (x2, y2) = b; return abs(x1 - x2) + abs(y1 - y2); } template<typename Graph> void a_star_search (const Graph& graph, typename Graph::Location start, typename Graph::Location goal, unordered_map<typename Graph::Location, typename Graph::Location>& came_from, unordered_map<typename Graph::Location, double>& cost_so_far) { typedef typename Graph::Location Location; PriorityQueue<Location, double> frontier; frontier.put(start, 0); came_from[start] = start; cost_so_far[start] = 0; while (!frontier.empty()) { auto current = frontier.get(); if (current == goal) { break; } for (auto& next : graph.neighbors(current)) { double new_cost = cost_so_far[current] + graph.cost(current, next); if (!cost_so_far.count(next) || new_cost < cost_so_far[next]) { cost_so_far[next] = new_cost; double priority = new_cost + heuristic(next, goal); frontier.put(next, priority); came_from[next] = current; } } } }

priority

優先度キューに使用されるタイプを含む値のタイプは、グラフのコスト（cost_t

）とヒューリスティック値の両方を含めるのに十分な大きさである必要があります。たとえば、グラフの値がintに格納されており、ヒューリスティックがdoubleを返す場合、優先度キューがdoubleを受信できることが必要です。このコード例では、double

3つの値（値、ヒューリスティック、および優先順位）すべてに使用していますがint

、値とヒューリスティックには整数値があるため、andを使用できます。

簡単なメモ：それは書き込みに良いだろうfrontier.put(start, heuristic(start, goal))

、とではありませんfrontier.put(start, 0)

、ただし、開始ノードの優先順位は重要ではないため、ここでは重要ではありません。これは優先度キューの唯一のノードであり、そこに何かが書き込まれる前に選択および削除されます。

 #include "redblobgames/pathfinding/a-star/implementation.cpp" int main() { GridWithWeights grid = make_diagram4(); SquareGrid::Location start{1, 4}; SquareGrid::Location goal{8, 5}; unordered_map<SquareGrid::Location, SquareGrid::Location> came_from; unordered_map<SquareGrid::Location, double> cost_so_far; a_star_search(grid, start, goal, came_from, cost_so_far); draw_grid(grid, 2, nullptr, &came_from); std::cout << std::endl; draw_grid(grid, 3, &cost_so_far, nullptr); std::cout << std::endl; vector<SquareGrid::Location> path = reconstruct_path(start, goal, came_from); draw_grid(grid, 3, nullptr, nullptr, &path); }

↓ ↓ ↓ ↓ ← ← ← ← ← ← 
      

        
        
        
      

     ↓ ↓ ↓ ↓ ← ↑ ↑ ← ← ← 
      

        
        
        
      

     ↓ ↓ ↓ ↓ ← ← ↑ ↑ ← ← 
      

        
        
        
      

     ↓ ↓ ↓ ← ← ← . ↑ ↑ ← 
      

        
        
        
      

     → * ← ← ← ← . → ↑ ← 
      

        
        
        
      

     → ↑ ← ← ← ← . . ↑ . 
      

        
        
        
      

     ↑ ↑ ↑ ← ← ← . . . . 
      

        
        
        
      

     ↑ ######↑ . . . . . 
      

        
        
        
      

     ↑ ######. . . . . . 
      

        
        
        
      

     ↑ . . . . . . . . . 
      

        
        
        
      

     
      

        
        
        
      

     5 4 5 6 7 8 9 10 11 12 
      

        
        
        
      

     4 3 4 5 10 13 10 11 12 13 
      

        
        
        
      

     3 2 3 4 9 14 15 12 13 14 
      

        
        
        
      

     2 1 2 3 8 13 . 17 14 15 
      

        
        
        
      

     1 0 1 6 11 16 . 20 15 16 
      

        
        
        
      

     2 1 2 7 12 17 . . 16 . 
      

        
        
        
      

     3 2 3 4 9 14 . . . . 
      

        
        
        
      

     4 #########14 . . . . . 
      

        
        
        
      

     5 #########. . . . . . 
      

        
        
        
      

     6 . . . . . . . . . 
      

        
        
        
      

     
      

        
        
        
      

     . . . @ @ @ @ . . . 
      

        
        
        
      

     . . . @ . . @ @ . . 
      

        
        
        
      

     . . . @ . . . @ @ . 
      

        
        
        
      

     . . @ @ . . . . @ . 
      

        
        
        
      

     . @ @ . . . . . @ . 
      

        
        
        
      

     . . . . . . . . @ . 
      

        
        
        
      

     . . . . . . . . . . 
      

        
        
        
      

     . #########. . . . . . 
      

        
        
        
      

     . #########. . . . . . 
      

        
        
        
      

     . . . . . . . . . .

2.4.1直線化

このコードをプロジェクトに実装すると、一部のパスが希望どおりに「直接」ではないことに気付くかもしれません。これは大丈夫です。グリッド、特に各ステップの移動コストが同じグリッドを使用する場合、結果は同等のオプションになります。多くのパスのコストは同じです。*は多くの最短パスの1つを選択しますが、非常にきれいに見えないことが非常に多くあります。同等のオプションは簡単なハックで排除できますが、完全に適切というわけではありません。マップビューを変更することをお勧めします、A *を大幅に加速し、より直接的で美しいパスを作成します。ただし、これは各ステップの移動コストが同じ静的カードでのみ機能します。私のページのデモでは、クイックハックを使用しましたが、優先度の低いキューでのみ機能します。より高速な優先キューに移動する場合は、別の高速ハックが必要です。

2.4.2 TODO：ベクトルネイバー（）を渡す必要があります

隣人の新しいベクトルを毎回強調表示して返す代わりに、A *コードは1つのベクトルを選択し、毎回それを隣人関数に渡す必要があります。私のテストでは、これによりコードがはるかに高速になりました。

2.4.3 TODO：テンプレートのパラメーター化を排除

このページの目的は、理解しやすいコードを作成することです。テンプレートをパラメーター化すると、テンプレートの読み取りが複雑になりすぎると思います。代わりに、いくつかのtypedefを使用します。

2.4.4 TODO：要件の追加

グラフには2つのタイプ（重み付きおよび重みなし）があり、グラフ検索コードでは、どのタイプがどこで必要かはわかりません。

3 Cでの実装＃

これらは私の最初のC＃プログラムであるため、この言語では特徴的でないか、スタイルが正しくない可能性があります。これらの例は、PythonおよびC ++セクションの例ほど完全ではありませんが、役に立つことを願っています。以下に、単純なグラフと幅優先検索の実装を示します。

 using System; using System.Collections.Generic; public class Graph<Location> { //        string, //      NameValueCollection public Dictionary<Location, Location[]> edges = new Dictionary<Location, Location[]>(); public Location[] Neighbors(Location id) { return edges[id]; } }; class BreadthFirstSearch { static void Search(Graph<string> graph, string start) { var frontier = new Queue<string>(); frontier.Enqueue(start); var visited = new HashSet<string>(); visited.Add(start); while (frontier.Count > 0) { var current = frontier.Dequeue(); Console.WriteLine("Visiting {0}", current); foreach (var next in graph.Neighbors(current)) { if (!visited.Contains(next)) { frontier.Enqueue(next); visited.Add(next); } } } } static void Main() { Graph<string> g = new Graph<string>(); g.edges = new Dictionary<string, string[]> { { "A", new [] { "B" } }, { "B", new [] { "A", "C", "D" } }, { "C", new [] { "A" } }, { "D", new [] { "E", "A" } }, { "E", new [] { "B" } } }; Search(g, "A"); } }

これは、重み付きのエッジを持つグリッドを表すグラフです（前の記事の森と壁の例）：

 using System; using System.Collections.Generic; //  A*   WeightedGraph    L,   ** //   .       . public interface WeightedGraph<L> { double Cost(Location a, Location b); IEnumerable<Location> Neighbors(Location id); } public struct Location { //   :   Equals  , //     . ,     //  Equals  GetHashCode. public readonly int x, y; public Location(int x, int y) { this.x = x; this.y = y; } } public class SquareGrid : WeightedGraph<Location> { //   :      , //    , ,    //     . public static readonly Location[] DIRS = new [] { new Location(1, 0), new Location(0, -1), new Location(-1, 0), new Location(0, 1) }; public int width, height; public HashSet<Location> walls = new HashSet<Location>(); public HashSet<Location> forests = new HashSet<Location>(); public SquareGrid(int width, int height) { this.width = width; this.height = height; } public bool InBounds(Location id) { return 0 <= id.x && id.x < width && 0 <= id.y && id.y < height; } public bool Passable(Location id) { return !walls.Contains(id); } public double Cost(Location a, Location b) { return forests.Contains(b) ? 5 : 1; } public IEnumerable<Location> Neighbors(Location id) { foreach (var dir in DIRS) { Location next = new Location(id.x + dir.x, id.y + dir.y); if (InBounds(next) && Passable(next)) { yield return next; } } } } public class PriorityQueue<T> { //       ,    //     .      //      C#: https://github.com/dotnet/corefx/issues/574 // //     ,     : // * https://github.com/BlueRaja/High-Speed-Priority-Queue-for-C-Sharp // * http://visualstudiomagazine.com/articles/2012/11/01/priority-queues-with-c.aspx // * http://xfleury.github.io/graphsearch.html // * http://stackoverflow.com/questions/102398/priority-queue-in-net private List<Tuple<T, double>> elements = new List<Tuple<T, double>>(); public int Count { get { return elements.Count; } } public void Enqueue(T item, double priority) { elements.Add(Tuple.Create(item, priority)); } public T Dequeue() { int bestIndex = 0; for (int i = 0; i < elements.Count; i++) { if (elements[i].Item2 < elements[bestIndex].Item2) { bestIndex = i; } } T bestItem = elements[bestIndex].Item1; elements.RemoveAt(bestIndex); return bestItem; } } /*   :      Python   *  ,     .   C++ *     typedef,     int, double  *  .     C#    ,  *   double.   int,   ,   *    ,    ,  ,  *    . */ public class AStarSearch { public Dictionary<Location, Location> cameFrom = new Dictionary<Location, Location>(); public Dictionary<Location, double> costSoFar = new Dictionary<Location, double>(); // :   A*   Location //  Heuristic static public double Heuristic(Location a, Location b) { return Math.Abs(ax - bx) + Math.Abs(ay - by); } public AStarSearch(WeightedGraph<Location> graph, Location start, Location goal) { var frontier = new PriorityQueue<Location>(); frontier.Enqueue(start, 0); cameFrom[start] = start; costSoFar[start] = 0; while (frontier.Count > 0) { var current = frontier.Dequeue(); if (current.Equals(goal)) { break; } foreach (var next in graph.Neighbors(current)) { double newCost = costSoFar[current] + graph.Cost(current, next); if (!costSoFar.ContainsKey(next) || newCost < costSoFar[next]) { costSoFar[next] = newCost; double priority = newCost + Heuristic(next, goal); frontier.Enqueue(next, priority); cameFrom[next] = current; } } } } } public class Test { static void DrawGrid(SquareGrid grid, AStarSearch astar) { //   cameFrom for (var y = 0; y < 10; y++) { for (var x = 0; x < 10; x++) { Location id = new Location(x, y); Location ptr = id; if (!astar.cameFrom.TryGetValue(id, out ptr)) { ptr = id; } if (grid.walls.Contains(id)) { Console.Write("##"); } else if (ptr.x == x+1) { Console.Write("\u2192 "); } else if (ptr.x == x-1) { Console.Write("\u2190 "); } else if (ptr.y == y+1) { Console.Write("\u2193 "); } else if (ptr.y == y-1) { Console.Write("\u2191 "); } else { Console.Write("* "); } } Console.WriteLine(); } } static void Main() { //  " 4"    var grid = new SquareGrid(10, 10); for (var x = 1; x < 4; x++) { for (var y = 7; y < 9; y++) { grid.walls.Add(new Location(x, y)); } } grid.forests = new HashSet<Location> { new Location(3, 4), new Location(3, 5), new Location(4, 1), new Location(4, 2), new Location(4, 3), new Location(4, 4), new Location(4, 5), new Location(4, 6), new Location(4, 7), new Location(4, 8), new Location(5, 1), new Location(5, 2), new Location(5, 3), new Location(5, 4), new Location(5, 5), new Location(5, 6), new Location(5, 7), new Location(5, 8), new Location(6, 2), new Location(6, 3), new Location(6, 4), new Location(6, 5), new Location(6, 6), new Location(6, 7), new Location(7, 3), new Location(7, 4), new Location(7, 5) }; //  A* var astar = new AStarSearch(grid, new Location(1, 4), new Location(8, 5)); DrawGrid(grid, astar); } }

4最適化

記事のコードを作成するとき、パフォーマンスよりも単純さと適用性に注目しました。最初にコードを機能させてから、速度を最適化します。私が実際のプロジェクトで使用した多くの最適化はプロジェクトに固有のものであるため、最適なコードを示す代わりに、独自のプロジェクトに実装できるいくつかのアイデアを提供します。

4.1カウント

可能な最大の最適化は、ノードの数を減らすことです。推奨事項1：グリッドのマップを使用する場合、グリッドに基づいていないパス検索グラフを適用してください。これは常に可能というわけではありませんが、このオプションは検討する価値があります。

グラフが単純な構造（グリッドなど）である場合、関数の近傍を計算します。より複雑な構造（グリッドなし、または迷路のように多数の壁があるグリッド）がある場合は、データ構造に近傍を保存します。

近隣の配列を再利用することにより、コピー操作を保存することもできます。毎回リターンを実行する代わりに、検索コードで一度選択して、グラフのネイバーメソッドに渡します。

4.2キュー

幅優先検索では、他のアルゴリズムで使用される優先度キューではなく、通常のキューが使用されます。キューは、優先キューよりも高速で簡単です。他のアルゴリズムは、より少ないノードを調べます。ほとんどのゲームカードでは、調査するノードの数を減らすことは、他のアルゴリズムを遅くする価値があります。ただし、あまり節約できないカードもあるため、幅の検索を使用することをお勧めします。

キューの場合は、代わりにdeque配列を使用してください。 dequeは、どちらの側からでもすばやく挿入および削除できる機能を提供しますが、配列は一方の端からのみ高速です。 Pythonでは、collections.dequeを使用する必要があります。 C ++では、dequeコンテナを検討してください。ただし、幅優先検索ではキューも必要ありません。2つのベクターを使用して、一方が空のときにそれらを切り替えることができます。

優先度キューの場合、配列またはソートされた配列ではなく、バイナリヒープを使用します。バイナリヒープは、挿入と削除をすばやく行う機能を提供しますが、配列は1つの点で高速です。 Pythonでは、heapqの使用をお勧めします。 C ++では、priority_queueコンテナを試してください。

Pythonでは、上で示したQueueおよびPriorityQueueクラスは非常に単純なので、検索アルゴリズムにメソッドを埋め込むことができます。これでたくさん勝てるかどうかはわかりませんが、テストする価値はあります。 C ++バージョンが埋め込まれます。

ダイクストラのアルゴリズムでは、優先度キューの優先度が2回保存されます。1回は優先度キューに、2番目は2番目に保存されるcost_so_far

ため、どこからでも優先度を受け取る優先度キューを作成できます。価値があるかどうかはわかりません。

標準のダイクストラアルゴリズムの実装では、優先度キューの優先度の変更を使用します。ただし、優先度を変更しないとどうなりますか？その結果、そこに重複した要素が表示されます。ただし、アルゴリズムは引き続き機能します。彼は必要以上にいくつかのポイントを再訪します。優先度キューには必要以上の要素が含まれるため、速度が低下しますが、優先度の変更をサポートするデータ構造も、要素が多いために速度が低下します。Chen、Chaudhery、Ramachandran、Lan Roche、Tongaによる「Priority Queues and Dijkstra's Algorithm」の研究を参照してください。この研究では、ヒープとその他のデータ構造のペアリングを考慮することも推奨しています。

バイナリヒープの代わりに何かを使用することを考えている場合は、最初に境界のサイズと優先順位が変更される頻度を測定します。コードのプロファイルを作成し、優先度キューがボトルネックになっているかどうかを確認します。

有望な方向性はデータのグループ化。キーが整数値である場合、ブロックソートとビット単位ソートがクイックソートの便利な代替手段であるように、ダイクストラとA *アルゴリズムの場合、状況はさらに良くなります。ダイクストラのアルゴリズムの優先順位は非常に低いです。キュー内の最小要素が優先される場合はf

、次に一番上の要素が優先有しf+e

、e

エッジの最大重量- 。森の例では、フィン1と5キュー内のすべての優先順位の間になると、この手段の重量持つf

としますf+5

。それらはすべて整数であるため、6つの異なる優先順位があります。。6つのブロックを使用することも、何もソートしないこともできます！*はより幅広い優先順位を作成しますが、それでもこの方法は検討する価値があります。また、より広範な状況に対処できるグループ化へのより興味深いアプローチがあります。

優先キューのデータ構造に関する別の記事があります。

4.3検索

ヒューリスティックにより、CPUの複雑さと時間が消費されます。ただし、ここでの目標は、より少ないノードを調査することです。一部のマップ（迷路など）では、ヒューリスティックは多くの情報を追加しない場合があり、ヒューリスティックを使用しない単純なアルゴリズムを使用する方が適切な場合があります。

整数値を使用してのポイントとしてあなたのグラフは、その後、使用の可能性を検討した場合はcost_so_far

、visited

、came_from

などハッシュテーブルではなく、単純な配列。これvisited

はブール配列であるため、ビットベクトルを使用できます。すべての識別子のビットベクトルを初期化しますがcost_so_far

、came_from

初期化されないままにします（言語で許可されている場合）。その後、最初の訪問時にのみ初期化します。

一度に1つの検索のみを実行する場合、次の呼び出しで静的にデータ構造を抽出して再利用できます。入力で初期化する代わりに、出力でリセットします。配列を使用して、変更するポイントを追跡し、変更するだけです。たとえばvisited[]

、1000ノード用に初期化された配列を使用しているが、ほとんどの検索プロセスが100ノード未満を訪問する場合、関数を入力するときに1000ノードすべてを再初期化する代わりに、インデックス配列を変更し、関数を終了するときにこれらの100ノードのみを変更できます。無効な

*を使用する人もいます（過大評価）ヒューリスティック。それは理にかなっているようです。ただし、これらの実装については慎重に検討しませんでした。既に訪問した一部の要素は、既に国境から削除されている場合でも、再度訪問する必要があると思います（確かではありません）。

実装によっては、新しいノードが既に開いているセットに既に挿入されている場合でも、常に挿入されます。これにより、ノードが既にオープンセットにあるかどうかを確認するコストのかかる可能性のあるステップを回避できます。ただし、同時に、開いているセットが大きく/遅くなり、その結果、必要以上のノードを評価する必要があります。オープンセットのチェックにコストがかかる場合は、おそらくこのアプローチを使用する必要があります。ただし、提示したコードでは、チェックを安くし、このアプローチは使用しません。

いくつかの実装では新しいノードがオープンセット内の既存のノードよりも優れているかどうかはチェックされません。これにより、潜在的にコストのかかる検証が回避されます。ただし、これによりエラーが発生する場合があります。一部の種類のカードでは、このチェックをスキップすると最短経路が見つかりません。提示したコードでは、このチェックを実行します（new_cost < cost_so_far

）。私がcost_so_far

安い検索をしたので、このチェックは安いです。

5トラブルシューティング

5.1間違ったパス

最短パスを取得できない場合は、次のチェックを試してください。

優先キューは正しく機能しますか？検索を停止して、キューからすべてのアイテムを削除してください。彼らは順番に行く必要があります。
? priority

, ( , ).
, . , , . , , , .

5.2

ほとんどの場合、グリッドでA *を実行するときに、彼らは私に質問をします：なぜパスはまっすぐに見えないのですか？グリッドに沿ったすべての動きのコストが等しいことをA *に伝えると、同じ長さの多くの最短経路が得られ、アルゴリズムはそれらの1つをランダムに選択します。パスは短いですが、見栄えがよくありません。

1つの解決策は、「ストリングプル」アルゴリズムを使用して、アルゴリズムの後にパスをまっすぐにすることです。
別の解決策は、ヒューリスティックを調整することにより、正しい方向に道を導くことです。すべての状況で機能しない安価なトリックがいくつかあります。ここで、これについて詳しく読むことができます。
— . A* , , . .
— , . (: , , , ), «» ( (x+y) % 2 == 1). .

6

. . :
- cost
  
  w or d l length
- cost_so_far
  
  g d distance
- heuristic
  
  h
- priority
  
  A* f , f = g + h
- came_from
  
  π parent previous prev
- frontier
  
  OPEN
- visited
  
  — OPEN CLOSED
- , , current
  
  next
  
  u , v
:
- ()
- A*

アルゴリズムAの実装*