Chapter 93

幅優先探索

miku
miku
2021.11.20に更新

前回までの章でマップを作成をして二次元配列に値を入れるアルゴリズムについて扱った。次にこの章からはそのマップに対して最短経路やルートを求める探索アルゴリズムについて扱う。

この章で扱う幅優先探索ではマップを抽象化したグラフというデータ構造に対して最短経路を求めることができる。そのため、まずはグラフに対しての説明を行う。

グラフ

数字が付いている丸は対象物を表し、グラフでは頂点と呼ぶ。頂点と頂点の間の線は関係を表し、グラフでは辺と呼ぶ。

たとえば頂点は人物で、線の繋がりは友好関係を表している場合、1番と2番は友達であり、1番と5番は友達ではないが、2番という共通の友人を持っていることがわかる。

頂点が駅で、線は駅間の繋がりを表している場合、1番の駅から6番の駅まで移動することができるが、1番の駅から8番の駅まではどう移動してもたどり着くことはできない。

上記グラフ程度だと目視で繋がりを確認することができるが、頂点や辺の数が増えるとそうはいかなくなる。なので、プログラムで頂点と辺を管理して、たとえば1番から6番まで移動ができるのか、移動ができるなら最短で何回で移動ができるか、1番からたどり着くことができる頂点をすべて挙げたい、などの要望が出てくる。このような要望を実現するために探索を行う必要があり、幅優先探索は名前の通り探索の一種になる。

グラフの管理

まずは探索の前にグラフの頂点や辺を管理するためのコードを書く。

const edge = [[1, 2], [0], [0]];

二次元配列 edge を用意して edge[i] には頂点 i に繋がっている各頂点を配列に入れる。

const edge = [[1, 2], [0], [0]];

// 頂点0に繋がっている頂点を1つずつ取り出す
for (const v of edge[0]) {
  console.log(v); // 1 2
}

たとえば頂点0に繋がっている頂点を1つずつ取り出すには上記のように書けばいい。

幅優先探索

幅優先探索では、まず探索を開始する頂点を選択する。ここでは (1) を選んだとする。

(1) に繋がっている1つ離れた各頂点 (2, 3, 4) を調べ、次は2つ離れた各頂点 (5, 6, 7) を調べ・・・と始点に近いところから網羅的に探索を行う。

上記手順をコードに落とすための具体的なアルゴリズムは下記のとおり。

  1. 始点を配列に加える。
  2. 配列から先頭にある頂点を取り出す。
  3. 取り出した頂点に繋がっている未探索の頂点を全て配列の末尾に追加する。
  4. 配列の中身が空なら処理を終了、そうでなければ 2 に戻る。

このように探索を行うと、探索を開始した始点に繋がっているすべての頂点を、始点に近い順に取り出すことができる。

一度確認した頂点は探索済みであるというフラグを持たせなければならない。たとえばある頂点aを取り出した後、頂点aに繋がっている頂点bを取り出した際に、頂点bから頂点aに繋がっているので、また頂点aを配列に追加してしまうと無限ループに陥ってしまうからだ。

幅優先探索を行うコード

const n = 8; // 頂点数
const edge = [[1, 2, 3], [4, 5], [0], [0, 6], [1], [1], [3], []];

// 始点startから幅優先探索を行う
function bfs(start) {
  // 各頂点が探索済みかどうかを確認するための配列
  // 最初はすべて false で初期化しておき、頂点iが探索済みなら seen[i] に true を入れる
  const seen = new Array(n).fill(false);
  // 始点を探索済みにする
  seen[start] = true;
  // 未探索の頂点を入れる配列
  const queue = [start];

  // 未探索の頂点が空になるまでループを行う
  while (queue.length > 0) {
    // 配列から先頭の要素を取り出す
    const cur = queue.shift();
    console.log(cur); // 取り出した頂点番号を出力

    // 取り出した頂点に繋がっている頂点を1つずつ確認する
    for (const next of edge[cur]) {
      // すでに探索済みなら対象外
      if (seen[next]) continue;
      seen[next] = true; // 探索済みにする

      queue.push(next); // 配列の末尾に追加する
    }
  }
}

bfs(0);

queue 配列が空になった時点で頂点 start から辿ることができるすべての頂点が探索済みである。この時点で seen[i] === false になっている頂点 i は 頂点 start から辿り着くことができない頂点であることがわかる。

始点から任意の頂点までの最短距離

幅優先探索では始点から近い順に頂点を順番に取り出すので、その特性を利用して始点から任意の頂点までの最短距離を計算することができる。

const n = 8;
const edge = [[1, 2, 3], [4, 5], [0], [0, 6], [1], [1], [3], []];

function bfs(start) {
  // 距離としてとり得ることがないであろう値
  const INF = 1000000000;
  // 始点startから頂点iまでの最短距離
  const dist = new Array(n).fill(INF);
  dist[start] = 0; // 始点から始点までの距離は0にする

  const seen = new Array(n).fill(false);
  seen[start] = true;
  const queue = [start];

  while (queue.length > 0) {
    const cur = queue.shift();

    for (const next of edge[cur]) {
      if (seen[next]) continue;
      seen[next] = true; // 始点からnextまでの距離は、始点からcurまでの距離+1になる。

      dist[next] = dist[cur] + 1;

      queue.push(next);
    }
  }

  console.log(dist);
}

bfs(0);

配列 dist は、始点から頂点 i まで移動するのに必要な最短距離を dist[i] に入れる。最初に初期値として全ての要素には距離としてとり得ることはないであろう値を入れておく。解説では10億を INF という定数にしていて、それを初期値にしている。

まず最初に分かっているのは始点から始点までの距離は 0 なので dist[start]0 を入れる。

ループ内の cur までの最短距離は dist[cur] なので、その cur に繋がっている next のまでの最短距離は dist[cur] + 1 になる。なのでその値を dist[next] に入れる。

コードの最適化

const n = 8;
const edge = [[1, 2, 3], [4, 5], [0], [0, 6], [1], [1], [3], []];

function bfs(start) {
  const INF = 1000000000;
  const dist = new Array(n).fill(INF);
  dist[start] = 0;

  const queue = [start];

  while (queue.length > 0) {
    const cur = queue.shift();
    console.log(cur);

    for (const next of edge[cur]) {
      if (dist[next] !== INF) continue;
      dist[next] = dist[cur] + 1;
      queue.push(next);
    }
  }
}

bfs(0);

dist[i]INF だと、頂点 i は未探索だということがわかるので、if (seen[next])if (dist[next] !== INF) に置き換えれば seen 配列は不要になる。

2点の最短距離を求める

function setup() {
  createCanvas(windowWidth, windowHeight);

  const INF = 1000000000;
  const n = 8;
  const edge = [[1, 2, 3], [4, 5], [0], [0, 6], [1], [1], [3], []];

  function bfs(start, end) {
    const dist = new Array(n).fill(INF);
    dist[start] = 0;

    const queue = [start];

    while (queue.length > 0) {
      const cur = queue.shift();

      if (cur === end) break;

      for (const next of edge[cur]) {
        if (dist[next] !== INF) continue;
        dist[next] = dist[cur] + 1;
        queue.push(next);
      }
    }

    return dist[end];
  }

  console.log(bfs(0, 1)); // 1
  console.log(bfs(0, 6)); // 2
  console.log(bfs(0, 7)); // 1000000000
}

bfs(start, end) で、start~end までの最短距離を求める。ルートが繋がっていない場合は INF を返す。

二次元配列での幅優先探索

次に本題のマップデータが入った二次元配列における幅優先探索を扱う。たとえばマップ上を上下左右に移動できる場合、あるセル map[y][x] が繋がっているセルは map[y - 1][x], map[y + 1][x], map[y][x - 1], map[y][x + 1] と明確にわかるので、頂点同士の繋がりである edge 配列を作る必要がない。

const x = 0;
const y = 0;

const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

for (let i = 0; i < 4; i++) {
  const tx = x + dx[i];
  const ty = y + dy[i];

  /*
  -1 0
  1 0
  0 -1
  0 1
  */
  console.log(tx, ty);
}

上下左右に移動するできる場合、相対的な移動量としては (-1, 0), (1, 0), (0, -1), (0, 1) になる。その (x, y) と組合せとなる配列 dx[], dy[] を用意して、(dx[i], dy[i]) のように取り出して (x, y) と足し合わせると (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1) の座標が順番に取り出せる。

const INF = 1000000000;
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
const W = 4; // マップの高さ
const H = 4; // マップの幅
const WALL = 1; // マップデータの1は通れない壁を表す
const map = [
  [0, 0, 1, 0],
  [0, 1, 1, 1],
  [0, 0, 1, 0],
  [0, 0, 0, 0],
];

// (sx, sy)~(gx, gy)までの最短距離を返す
function bfs(sx, sy, gx, gy) {
  // 縦H 横Wの二次元配列を作りINFで埋める
  const dist = Array(H)
    .fill()
    .map(() => Array(W).fill(INF));
    
  // 始点までの最短距離は0
  dist[sy][sx] = 0;

  // 配列に始点を入れておく
  const queue = [{ x: sx, y: sy }];
  
  // 配列が空になるまでループ
  while (queue.length > 0) {
    const cur = queue.shift();

    // 目標の地点が見つかった時点でループを抜ける
    if (cur.x === gx && cur.y === gy) break;

  // 今いる(cur.x, cur.y)の上下左右のセルを取り出す
    for (let i = 0; i < 4; i++) {
      const tx = cur.x + dx[i];
      const ty = cur.y + dy[i];

   // 配列外、セルが壁、セルが探索済みならcontinue
      if (tx < 0 || tx >= W || ty < 0 || ty >= H) continue;
      if (map[ty][tx] === WALL) continue;
      if (dist[ty][tx] !== INF) continue;

      // 始点からの距離を設定、配列の末尾に位置を追加する
      dist[ty][tx] = dist[cur.y][cur.x] + 1;
      queue.push({ x: tx, y: ty });
    }
  }

  return dist[gy][gx];
}

console.log(bfs(1, 2, 1, 0)); // 4
console.log(bfs(1, 2, 3, 0)); // 1000000000

最短経路を求める

ただ探索を行うのではなく、始点から終点までの経路を出力したい場合がある。今探索中の頂点 cur から辺で繋がっている頂点が next0, next1, next2 のとき、どの頂点が最短経路かはわからないが、始点から近い頂点を探索する性質上、next0, next1, next2 までの最短経路は cur を通ることがわかる。なので配列に新しい頂点を追加する際、その頂点の一つ前は cur だったことを記録しておくと、最終的に、終点から始点までを辿ることができる。

prev[y * w + x] = cur;

配列である prev を用意して、prev[i] には1つ前の頂点を入れる。二次元配列の場合キーが (x, y) と2つあるので、一次元のキーに変換した y * w + x を利用する。

let routes = [];

// 目的地点から逆に辿る
let cx = gx;
let cy = gy;

while (true) {
  // 逆に辿っているため配列に追加するときは前から要素を入れる
  routes.unshift({ x: cx, y: cy });

  // 始点まで来たら終了
  if (cx === sx && cy === sy) {
    break;
  }

  // 連想配列から前の地点を取り出す
  const index = cy * W + cx;
  const prev = prevs[index];
  cx = prev.x;
  cy = prev.y;
}

console.log(routes);

prev[] から始点から終点までのルートを構築する場合、終点の一つ前の頂点、その頂点の一つ前の頂点・・・と、取り出した頂点が始点になるまでループを行う。取り出した順番とは逆の順番が欲しいルートになるので、配列に取り出した頂点を追加する場合は、前から追加を行う。

const INF = 1000000000;
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
const W = 4;
const H = 4;
const WALL = 1;
const map = [
  [0, 0, 1, 0],
  [0, 1, 1, 1],
  [0, 0, 1, 0],
  [0, 0, 0, 0],
];

function bfs(sx, sy, gx, gy) {
  const prev = [];
  const dist = Array(H)
    .fill()
    .map(() => Array(W).fill(INF));
  dist[sy][sx] = 0;

  const queue = [{ x: sx, y: sy }];
  while (queue.length > 0) {
    const cur = queue.shift();

    if (cur.x === gx && cur.y === gy) break;

    for (let i = 0; i < 4; i++) {
      const tx = cur.x + dx[i];
      const ty = cur.y + dy[i];

      if (tx < 0 || tx >= W || ty < 0 || ty >= H) continue;
      if (map[ty][tx] === WALL) continue;
      if (dist[ty][tx] !== INF) continue;

      dist[ty][tx] = dist[cur.y][cur.x] + 1;
      queue.push({ x: tx, y: ty });
      prev[ty * W + tx] = cur;
    }
  }

  let routes = [];
  let cx = gx;
  let cy = gy;

  while (true) {
    routes.unshift({ x: cx, y: cy });

    if (cx === sx && cy === sy) {
      break;
    }

    const index = cy * W + cx;
    const p = prev[index];
    cx = p.x;
    cy = p.y;
  }

  return routes;
}

/*
0: {x: 1, y: 2}
1: {x: 0, y: 2}
2: {x: 0, y: 1}
3: {x: 0, y: 0}
4: {x: 1, y: 0}
*/
console.log(bfs(1, 2, 1, 0));

bfs(sx, sy, gx, gy)(sx, sy)~(gx, gy) までの最短経路を返す。

最短経路の可視化

const Cell = {
  Floor: "floor",
  Wall: "wall",
};

const INF = 1000000000;
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
const cellSize = 10;
const Colors = {
  Visited: "#1c8b94",
  Routes: "#de980f",
  StartGoal: "#cd3830",
  Wall: "#757161",
};
const mapString = `
#######################################################
#_____________________________________________________#
#_________________________#___________________________#
#_________________________#___________________________#
#_________________________#___________________________#
#_________________________#___________###########_____#
#_________________________#___________#_______________#
#_________________________#####_______#__G____________#
#___________S_____________#___#_______##______________#
#_________________________#___#________#______________#
#_____________________________#________#______________#
#_________________________#___#________#______________#
#_________________________#___#______###______________#
#_________________________#___#_______________________#
#_________________________#####_______________________#
#_________________________#___________________________#
#_____________________________________________________#
#######################################################
`;

let map, w, h, sx, sy, gx, gy, queue, dist, prevs, visited, routes, isPlaying;

function setup() {
  createCanvas(windowWidth, windowHeight);

  parseStringMap();

  queue = [{ x: sx, y: sy }];
  prevs = [];
  visited = [];
  dist = [];
  for (let y = 0; y < map.length; y++) {
    dist[y] = new Array(map[0].length).fill(INF);
  }
  dist[sy][sx] = 0;

  while (0 < queue.length) {
    const cur = queue.shift();
    visited.push(cur);

    if (cur.x === gx && cur.y === gy) break;

    for (let i = 0; i < 4; i++) {
      const tx = cur.x + dx[i];
      const ty = cur.y + dy[i];

      if (!(0 <= tx && tx < w && 0 <= ty && ty < h)) continue;
      if (map[ty][tx] === Cell.Wall) continue;
      if (dist[ty][tx] !== INF) continue;

      dist[ty][tx] = dist[cur.y][cur.x] + 1;
      queue.push({ x: tx, y: ty });
      prevs[ty * w + tx] = cur;
    }
  }

  routes = [];
  let cx = gx;
  let cy = gy;

  while (true) {
    routes.unshift({ x: cx, y: cy });
    if (cx === sx && cy === sy) {
      break;
    }
    const index = cy * w + cx;
    const prev = prevs[index];
    cx = prev.x;
    cy = prev.y;
  }

  initFill();
  const c = Colors.StartGoal;
  fillCell(sx, sy, c);
  fillCell(gx, gy, c);
  isPlaying = true;
}

function draw() {
  if (isPlaying) {
    if (visited.length > 0) {
      const cur = visited.shift();
      const [cx, cy] = [cur.x, cur.y];
      if ((cx == sx && cy == sy) || (cx == gx && cy == gy)) {
        return;
      }
      fillCell(cx, cy, Colors.Visited);
    } else if (routes.length > 0) {
      const cur = routes.shift();
      const [cx, cy] = [cur.x, cur.y];
      if ((cx == sx && cy == sy) || (cx == gx && cy == gy)) {
        return;
      }
      fillCell(cx, cy, Colors.Routes);
    }
  }
}

function parseStringMap() {
  map = [];
  const ms = mapString.split("\n");
  ms.shift();
  ms.pop();

  h = ms.length;
  w = ms[0].length;

  for (let y = 0; y < h; y++) {
    map[y] = [];
    for (let x = 0; x < w; x++) {
      switch (ms[y][x]) {
        case "_":
          map[y][x] = Cell.Floor;
          break;
        case "S":
          sx = x;
          sy = y;
          map[y][x] = Cell.Floor;
          break;
        case "G":
          gx = x;
          gy = y;
          map[y][x] = Cell.Floor;
          break;
        default:
          map[y][x] = Cell.Wall;
          break;
      }
    }
  }
}

function initFill() {
  clear();
  strokeWeight(1);

  for (let y = 0; y < h; y++) {
    for (let x = 0; x < w; x++) {
      if (map[y][x] === Cell.Wall) {
        fillCell(x, y, Colors.Wall);
      }
    }
  }
}

function fillCell(x, y, c) {
  fill(c);
  const tx = x * cellSize;
  const ty = y * cellSize;
  rect(tx, ty, cellSize, cellSize);
}