序文

「グラフ・最短距離アルゴリズムのまとめメモ（１）」に引き続き、Dijkstra、Bellman-ford、A*、そしてJPSから派生した最短距離アルゴリズムを書きたいと思います。日本語下手ですのでちょっと用語について指摘して頂けましたらありがとうございます。

参照

INTRODUCTIONS TO ALGORITHMS 3rd EDITION Chapter 22
INTRODUCTIONS TO ALGORITHMS 3rd EDITION Chapter 24
ダイクストラ法 - Wikipedia
ベルマン–フォード法 - Wikipedia
A* 보다 빠른 JPS 알고리즘 : 네이버 블로그

本文

0. 本格的に入る前に知っておきたかったもの。

Introduction to algorithm 3edのChapter24初頭から新たに知ったものと確実ししたのをメモしました。

最短経路問題では重みがある辺があるグラフ、 ${G = (V, E)}$ と各辺に実数の重みを計算する関数 ${w : E \rightarrow \mathbf{R}}$ が与えられる。（本では「方向がある辺」と書いているが、非負数の重みがある以上元のノードには戻らない。）そして任意の経路 ${p = \left\langle v_0, v_1, ..., v_k \right\rangle}$ の重みはその経路を構える辺の重みを乗算したものと一致する。

即ち ${w(p) = \sum_{i=1}^{k} w(v{i-1}, v{i})}$ である。

BFSは重みが全部1のグラフで最短経路を探すアルゴリズムである。
最短経路問題を解くアルゴリズムは普通２つのノードの間の最短経路がその中にある部分最短経路を含めるという特性を利用する。これを「最短経路の部分構造最適性」という。
最短経路の部分構造最適性があるということは、動的計画法（DP）または貪欲法（どんよくほう、Greedy Algorithm）が適用出来る可能性あるということを指す。
そして今からまとめる「ダイクストラ法」「ベルマン・フォード法」この記事ではないが「ワーシャル–フロイド法」はそれぞれ貪欲法、動的計画法を使用している。

整理24.1：最短経路の全ての部分最短経路は最短経路である。

もしグラフの中である辺の重みが負数であるかもしれない。あるとしても負数の辺によって最短経路を求める為循環（サイクル）しなければ影響はない。しかし負数の重みによって無限に循環するようになったらスターティングポイントの ${s}$ から到着点 ${v}$ までの最短経路は取れない。そしてsからvまでの重みは ${\delta(s, v) = -\infty}$ と定義できる。
最短経路は負数の辺を持つ循環経路にはならない。そして非負数の重みを持つ循環も含められない。
重みが0がある辺がある循環を持つ最短経路がある場合には、その循環を含まずにもできる最短経路が存在する。

最短経路の表現

最短経路問題を解く途中で構成されるPrecessor Subgraph ${G_{\pi} = (V\pi, E\pi)}$ に対し、 ${v.\pi}$ の値は最短経路の親ノードを指していないかもしれない。
ただし、最短経路問題のアルゴリズムで結果的に出す ${G_{\pi} = (V\pi, E\pi)}$ 部分グラフでは全ての ${v.\pi}$ は最短経路を構成するための親ノードを指していることがわかる。

緩和（Relaxation）

最短経路問題のアルゴリズムはRelaxationを使う。グラフの全てのノートvの距離 ${v.d}$ は最初に ${\infty}$ に初期化される。その過程に ${\Theta(V)}$ 時間が掛かる。
Relaxationの途中に最短経路の推定値である ${v.d}$ を減らし、そして ${v.\pi}$ を更新することも出来る。Relaxationが発動する条件は、今の距離dが辺の重みと親となるノードのd距離と乗算した値を超えていたら緩和が発動する。

1. ダイクストラ法（Dijkstra）

グラフ（方向を持つ辺があるグラフでも良い） ${G = (V, E)}$ にて全ての辺の重みが非負数ではない場合に最短経路を探せる。
効率的に実装すれば２．ベルマン・フォード法より速度は速い。
貪欲法を使う。

More deep inside

ダイクストラ法はスターティングポイント ${s}$ からの最短経路の重みの合が最終的に決められたノードの集合 ${S}$ を管理する。
現在最短経路の重みの合最も少ないノードから辺として繋がる隣接したノード ${u \in V - S}$ に対し緩和を行う。それを反復的に実行する。
重みの合が一番少ない、まだ ${S}$ に入っていないノードを探すには二分ヒープ（最小ヒープ）を使用する。
そして全てのノードが ${S}$ にあったらアルゴリズムは実行を終える。
while各ルーフの最初の時点で全てのノード ${v \in S}$ に対し ${v.d = \delta(s, v)}$ である。
ダイクストラ法の時間複雑度は、Queueをどう実装するかによって３つに分かれる。
1. 全てのノードを一列にリストに入れてQueueを維持すること。INSERTとDECREASE-KEYは ${O(1)}$ になるが、ルーフごとに重みが一番少ないノード（Sに入っていない）を選ばなきゃならないためEXTRACT-MINは ${O(V)}$ になる。そして最悪 ${O(V^{2} + E)}$ の時間複雑度を見せられる。
2. グラフの密度が低ければ二分ヒープの最小ヒープを使用して向上させられる。この場合にはINSERT DECREASE-KEY EXTRACT-MIN全部 ${O(V)}$ になる。したがって時間複雑度は ${O((V + E)\lg{V})}$ になる。
3. 一番難しい方法だが、フィボナッチヒープを使用して時間複雑度 ${O(V\lg{V} + E)}$ が得られる。

コード

実装したコードは時間複雑度が ${O((V + E)\lg{V})}$ を見せる２番目の方法だ。

// @brief Compare function of minHeap.
// if true, left is previous to right in heap container.
static auto MinHeapCmp = [](const SNode* left, const SNode* right) { 
  return left->dist_from_start < right->dist_from_start; 
}; 
using THType = SNode*;
using TMinHeap = std::priority_queue<THType, std::vector<THType>, decltype(MinHeapCmp)>;

// @brief Relaxation function. 
// compare distance from start and push neighbor to minHeap.
static auto Relax = [](const EDirection dir, const THType cursor, THType neighbor, 
                       TMinHeap& heap) {
  assert(neighbor != nullptr && cursor != nullptr);
  if (neighbor->dist_from_start > cursor->dist_from_start + 1) {
    // Update distance from start and parent node in subgraph.
    neighbor->dist_from_start = cursor->dist_from_start + 1;
    neighbor->parent          = cursor;
    // Set direction to parent node in predecessor subgraph.
    SetDirectionToParent(*neighbor, dir);
    if (neighbor->status == ENodeStatus::Idle) { heap.push(neighbor); }
  }
};

void Dijkstra(TMazeContainer& map) {
  map[0][0].dist_from_start = 0;      // (0) Initialize starting point.
  TMinHeap minHeap{MinHeapCmp};       // (1) Insert start node to min_heap
  minHeap.push(&map[0][0]);

  while (minHeap.empty() == false) {  // (2) Do dijkstra comparing distances.
    THType cursor   = minHeap.top(); minHeap.pop();     // Extract-Min
    cursor->status  = decltype(SNode::status)::Visited; // Move into `S` set.

    for (auto dir = 0; dir < 4; ++dir) {                // Relaxation procedure
      auto& neighbor = cursor->neighbors[dir];
      if (neighbor.node == nullptr) { continue; }
      Relax(static_cast<EDirection>(dir), cursor, neighbor.node, minHeap);
    }
  }
}

2. ベルマン–フォード法（Bellman-ford）

負数の重みがある時にも使われる。
負数の重みがある循環経路があるときには皮膚数を持つ循環経路があるかを返すようにする。
- 重みが皮膚数の循環があるならグラフでの最短経路 ${\delta(s, v)}$ は存在しない。

More deep inside

ダイクストラ法とは違って理論上「状態」を持たない。しかし、コードでは皮膚数による循環を防ぐために状態を持つようにする。
BFSとの違いはBFSは重みが無いか単位の重みである反面、ベルマン・フォード法は辺のそれぞれの重みがある。
時間複雑度は ${O(VE)}$ である。何故なら全てのノード ${|V| - 1}$ で全ての辺 ${\Theta(E)}$ を調査するからだ。

コード

コードでは簡単なQueueを使ってノードの順番を指定する。

using THType = SNode*;
using TQueue = std::queue<THType>;
// @brief Relaxation function. 
// compare distance from start and push neighbor to minHeap.
static auto Relax = [](const EDirection dir, const THType cursor, THType neighbor, TQueue& queue) {
  assert(neighbor != nullptr && cursor != nullptr);
  if (neighbor->dist_from_start > cursor->dist_from_start + 1) {
    // Update distance from start and parent node in subgraph.
    neighbor->dist_from_start = cursor->dist_from_start + 1;
    neighbor->parent          = cursor;
    // Set direction to parent node in predecessor subgraph.
    SetDirectionToParent(*neighbor, dir);
    if (neighbor->status == ENodeStatus::Idle) { queue.emplace(neighbor); }
  }
};

// @brief Validation process whether or not there is negative cycle.
static auto DoValidation = [](const THType cursor, const THType neighbor) {
  assert(neighbor != nullptr && cursor != nullptr);
  if (neighbor->dist_from_start > cursor->dist_from_start + 1) {
    return false;
  }
  return true;
};

// @brief Do bellman-ford algorithm.
[[nodiscard]] bool BellmanFord(TMazeContainer& map) {
  // Initialize starting point.
  map[0][0].dist_from_start = 0; 
  TQueue nodeQueue {}; nodeQueue.emplace(&map[0][0]);

  // Do bellman-ford algorithm.
  while (nodeQueue.empty() == false) { 
    auto& node = *nodeQueue.front(); nodeQueue.pop();
    node.status = ENodeStatus::Visited;

    // Relaxation procedure
    for (auto dir = 0; dir < 4; ++dir) { 
      auto& neighbor = node.neighbors[dir];
      if (neighbor.node == nullptr) { continue; }
      Relax(static_cast<EDirection>(dir), &node, neighbor.node, nodeQueue);
    }
  }

  // Do validation of negative weight cycle.
  for (auto& row : map) { 
    for (auto& node : row) {
      if (node.type != ENodeType::Floor) { continue; }
      for (auto dir = 0; dir < 4; ++dir) {                
        auto& neighbor = node.neighbors[dir];
        if (neighbor.node == nullptr) { continue; }
        if (DoValidation(&node, neighbor.node) == false) { return false; };
      }
    }
  }
  return true;
}

3. A*（A-Star）

A* search algorithm - Wikipedia

正確度と性能が高く、実際にゲームエンジンなどでよく使われるアルゴリズム。そしてダイクストラ法かベルマン・フォード法みたいな基本的なアルゴリズムを除き一番広まっているアルゴリズムでもある。
ダイクストラ法の拡張版。しかしダイクストラ法は貪欲法を使って目の前（ノードから隣接したノード）へのノードの間の距離を最短として最短経路を探す反面、A-starはヒューリスティックを使用して貪欲法とはちょっと違う様相を見せる。
A*アルゴリズムはグラフ全体の情報が得られないと最短経路が解けない。（Informed search algorithm）
ダイクストラ法より遥かに速い。

More deep inside

A*は各ループでスターティングポイント ${s}$ からゴール ${v}$ までの距離を推定して進行する道を選ぶ。

これを数式を表現んすると

${f(n) = g(n) + h(n)}$

になる。

${g(n)}$ はスターティングポイント ${s}$ から現在のノード ${n}$ までの距離（多分 ${\delta(s, n)}$ じゃないかなと）である。
${h(n)}$ はヒューリスティック関数で、今のノード ${n}$ からゴール ${v}$ までに推定した最短距離の重み（コスト）を関数げ表現したものだ。
`A*の終了条件は２つか一つ以上を満たす。
1. ${s}$ から ${v}$ まで繋がった場合
2. グラフで進行する辺がもう残されていない場合
の推定数値がただしければA*により求める最短距離は最短距離であることを保障する。
- 普通は最短距離ではなく、それに準ずる短距離が取れる。

実装

A*を実装するにはダイクストラ法のように二分ヒープを使う。（多分フィボナッチヒープも出来るはず？）
二分ヒープに入るものは ${f(n)}$ か、それとも ${f(n)}$ を持っているノードへの参照になる。
各ループごとに一番が低いノードを取り出して隣接するノードのとを更新する。そいて隣接ノードが最小ヒープに入る。
- ${n'.h(n)}$ の値は固定である。ヒューリスティック関数は簡単にはゴールまでの直線距離として実装する。
最小ヒープが空っぽか、それとも ${v.f(n)}$ が一番低い時に終了する。その時 ${v.h(n) = 0}$ になる。

コード

// @brief Compare function of minHeap. 
// if true, left is previous to right in heap container.
static auto MinHeapCmp = [](const SNode* left, const SNode* right) { 
  return left->GetF() < right->GetF();
};

using THType = SNode*;
using TMinHeap = std::priority_queue<THType, std::vector<THType>, decltype(MinHeapCmp)>;

// @brief Relaxation function. 
// compare distance from start and push neighbor to minHeap.
static auto Relax = [](const EDirection dir, const THType cursor, THType neighbor, 
                       TMinHeap& heap) {
  assert(neighbor != nullptr && cursor != nullptr);
  if (neighbor->dist_from_start > cursor->dist_from_start + 1) {
    // Update distance from start and parent node in subgraph.
    neighbor->dist_from_start = cursor->dist_from_start + 1;
    neighbor->parent          = cursor;
    // Set direction to parent node in predecessor subgraph.
    SetDirectionToParent(*neighbor, dir);
    if (neighbor->status == ENodeStatus::Idle) { heap.push(neighbor); }
  }
};

// @brief Do Astar algorithm to [0, 0] -> [goalX, goalY].
// If [goalX, goalY] disappear in priority_queue (moved into S), halt algorithm
// and show result.
void Astar(TMazeContainer& map, const DVector2& start, const DVector2& goalPos) {
  auto& startNode = map[start.x][start.y];
  startNode.dist_from_start = 0;      
  TMinHeap minHeap{MinHeapCmp};       
  minHeap.push(&startNode);

  while (minHeap.empty() == false) {  
    THType cursor   = minHeap.top(); minHeap.pop();     // Extract-Min
    if (cursor->mPos == goalPos) { return; }            // Check goal point.
    cursor->status  = decltype(SNode::status)::Visited; // Move into `S` set.
    for (auto dir = 0; dir < 4; ++dir) {                // Relaxation procedure
      auto& neighbor = cursor->neighbors[dir];
      if (neighbor.node == nullptr) { continue; }
      Relax(static_cast<EDirection>(dir), cursor, neighbor.node, minHeap);
    }
  }
}

結論

分量調整ダイ失敗しました。（３）に分けて書きます。うげー

NEUROMANTIC

自分でC/C++/UE4/Graphics/ゲームなどをやったことをメモするブログ

グラフ・最短距離アルゴリズムのまとめメモ（２）

序文

参照

本文

0. 本格的に入る前に知っておきたかったもの。

最短経路の表現

緩和（Relaxation）

1. ダイクストラ法（Dijkstra）

More deep inside

コード

2. ベルマン–フォード法（Bellman-ford）

More deep inside

コード

3. A*（A-Star）

More deep inside

実装

コード

結論