経路探索(Bellman-Ford法を使う)

グラフの 2 点間の距離を求める Bellman-Ford 法を使えるライブラリを見つけたので、試してみます。

GitHub - woltsu/deno-graphs: Graph algorithms for deno

Graph …

• 参考
• 動作確認
• 追加実装

参考

• woltsu/deno-graphs

動作確認

サンプルを元に動作確認してみます。

app01.ts

import {
  Graph,
  Vertex,
  bellmanFord,
  exactPath,
} from "https://raw.githubusercontent.com/woltsu/deno-graphs/master/mod.ts";

const G = new Graph();

const a = new Vertex("a");
const b = new Vertex("b");
const c = new Vertex("c");
const d = new Vertex("d");
const e = new Vertex("e");

// 次の関係が有ってすべての点間の重さは1、すべて双方向でつながっている
// a--c
// |  |
// b--d--e
//

a.add(b, 1);
a.add(c, 1);

b.add(a, 1);
b.add(d, 1);

c.add(a, 1);
c.add(d, 1);

d.add(b, 1);
d.add(c, 1);
d.add(e, 1);

e.add(e, 1);

G.add(a);
G.add(b);
G.add(c);
G.add(d);
G.add(e);

//s を開始点として、各点までの距離を計算
const shortestPaths = bellmanFord(G, a);
console.log(shortestPaths);
// =>[
//     { a: 0, b: 1, c: 1, d: 2, e: 3 },
//     {
//       a: null,
//       b: Vertex { key: "a", edges: [ [Object], [Object] ] },
//       c: Vertex { key: "a", edges: [ [Object], [Object] ] },
//       d: Vertex { key: "b", edges: [ [Object], [Object] ] },
//       e: Vertex { key: "d", edges: [ [Object], [Object], [Object] ] }
//     }
//   ]

// 第4引数に指定した距離で、点s->点tに到達できるか計算
console.log(exactPath(G, a, d, 0));
// => false
console.log(exactPath(G, a, d, 1));
// => false
console.log(exactPath(G, a, d, 2));
// => true
console.log(exactPath(G, a, d, 3));
// => false
console.log(exactPath(G, a, d, 4));
// => true

指定した点から各点への距離、指定した距離で到達できるかが取得できました。

追加実装

bellmanFord の実行結果を見てみると、返り値の 2 番目は各点へ到達するために直前の点になっています。

app01.ts(抜粋)

const shortestPaths = bellmanFord(G, a);
console.log(shortestPaths);
// =>[
//     { a: 0, b: 1, c: 1, d: 2, e: 3 },
//     {
//       a: null,
//       b: Vertex { key: "a", edges: [ [Object], [Object] ] },
//       c: Vertex { key: "a", edges: [ [Object], [Object] ] },
//       d: Vertex { key: "b", edges: [ [Object], [Object] ] },
//       e: Vertex { key: "d", edges: [ [Object], [Object], [Object] ] }
//     }
//   ]

これを使って、経由点の配列を取得します。

app02.ts

import {
  bellmanFord,
  Graph,
  Vertex,
} from "https://raw.githubusercontent.com/woltsu/deno-graphs/master/mod.ts";

//  bellmanFord の結果から、経路を取得する
function getRoute(path: any, start: Vertex, goal: Vertex) {
  const p = path[1];
  let lastP = goal.key;
  const paths = [];

  while (true) {
    paths.unshift(lastP);
    if (start.key == lastP) break;
    lastP = p[lastP].key;
  }
  return paths;
}

const G = new Graph();

const a = new Vertex("a");
const b = new Vertex("b");
const c = new Vertex("c");
const d = new Vertex("d");
const e = new Vertex("e");
const f = new Vertex("f");

// a--c
// |  |
// b--d--e
// |
// f

a.add(b, 1);
a.add(c, 1);

b.add(a, 1);
b.add(d, 1);
b.add(f, 1);

c.add(a, 1);
c.add(d, 1);

d.add(b, 1);
d.add(c, 1);
d.add(e, 1);

e.add(d, 1);

f.add(b, 1);

G.add(a);
G.add(b);
G.add(c);
G.add(d);
G.add(e);
G.add(f);

const shortestPaths = bellmanFord(G, a);
console.log(shortestPaths);
// =>[
//     { a: 0, b: 1, c: 1, d: 2, e: 3, f: 2 },
//     {
//       a: null,
//       b: Vertex { key: "a", edges: [ [Object], [Object] ] },
//       c: Vertex { key: "a", edges: [ [Object], [Object] ] },
//       d: Vertex { key: "b", edges: [ [Object], [Object], [Object] ] },
//       e: Vertex { key: "d", edges: [ [Object], [Object], [Object] ] },
//       f: Vertex { key: "b", edges: [ [Object], [Object], [Object] ] }
//     }
//   ]
console.log(getRoute(shortestPaths, a, e));
// => [ "a", "b", "d", "e" ]

経路を取得できました。

試しに次のように距離を変更して ab 間の距離を 5 にします。

// a--1--c
// |     |
// 5     1
// |     |
// b--1--d----e
// |
// 1
// |
// f

app02.ts(距離変更)

import {
  bellmanFord,
  Graph,
  Vertex,
} from "https://raw.githubusercontent.com/woltsu/deno-graphs/master/mod.ts";

function getRoute(path: any, start: Vertex, goal: Vertex) {
  const p = path[1];
  let lastP = goal.key;
  const paths = [];

  while (true) {
    paths.unshift(lastP);
    if (start.key == lastP) break;
    lastP = p[lastP].key;
  }
  return paths;
}

const G = new Graph();

const a = new Vertex("a");
const b = new Vertex("b");
const c = new Vertex("c");
const d = new Vertex("d");
const e = new Vertex("e");
const f = new Vertex("f");

a.add(b, 1);
a.add(c, 1);

b.add(a, 1);
b.add(d, 1);
b.add(f, 1);

c.add(a, 1);
c.add(d, 1);

d.add(b, 1);
d.add(c, 1);
d.add(e, 1);

e.add(d, 1);

f.add(b, 1);

G.add(a);
G.add(b);
G.add(c);
G.add(d);
G.add(e);
G.add(f);

const shortestPaths = bellmanFord(G, a);
console.log(shortestPaths);
console.log(getRoute(shortestPaths, a, e));
// => [ "a", "c", "d", "e" ]

ab 間の距離を大きくしたことで、[ "a", "b", "d", "e" ]と選択されていた経路が[ "a", "c", "d", "e" ]に変わりました。

---

グラフでの経路探索ができました。
NPCをマップ空間上で移動・巡回させるなどさせるとき使えそうです。

このリポジトリ、deno~~という名前であるものの、Deno の API は介在しないので、ブラウザでの直接読み出しも可能そうです。

ではでは。