ヽ|∵|ゝ(Fantom) の 開発blog? ホーム »幅優先探索
このページの記事一覧

【Java】15パズルを解く [A*(A-star)アルゴリズム]  


 前回、迷路の探索をA*(A-star, エースター)アルゴリズムでやったので、ついでに「15パズル」を解いてみよう。

15パズル

 パズル自体の解き方は言わば「全パターン総当り方式(全探索)」である。ただ、3x3 サイズの 8パズルでなら、全探索でも問題なく解けるのだが、4x4 サイズの 15パズルになると、単純な全探索では、答えの手数が大きいときにフリーズしたような状態になってしまい、いずれキューのバッファオーバーフローでプログラムが停止してしまう。なので、A*(A-star) のような枝刈りアルゴリズムが必須になる。
 
 A*(A-star, エースター)アルゴリズムの解説はWikipediaなどを見るか、前回の「A*(A-star, エースター)アルゴリズムで迷路を探索する」で簡単な考え方を解説している。「推定値」の使い方だけ覚えれば十分だろう。

●15パズル解法 [A*(A-star)アルゴリズム]
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.HashSet;

public class FifteenPuzzleAstar {

public static void main(String[] args) throws Exception {
new FifteenPuzzleAstar();
}

//4方向探索用
static final int[] dx = { 0, 1, 0, -1};
static final int[] dy = {-1, 0, 1, 0};
static final char[] dir = {'u', 'r', 'd', 'l'};

static final int N = 4; //盤サイズ
static final int NN = N * N; //パネル総数

//各パネルのマンハッタン距離のテーブル
static final int[][] MDTable = new int[NN][NN];
static {
for (int i = 0; i < NN; i++) {
for (int j = 0; j < NN; j++) {
MDTable[i][j] = getManhattanDistance(i % N, i / N, j % N, j / N);
}
}
}

//マンハッタン距離を求める
static int getManhattanDistance(int x1, int y1, int x2, int y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}

public FifteenPuzzleAstar() {

int[][] board = new int[][]{ //初期の盤の状態
{ 1, 7, 2, 4},
{ 6, 0,14, 3},
{13,10,11, 8},
{ 5, 9,15,12},
}; //rrdllldruuurdllddrurrd 22(手)

String ans = astar(board);
System.out.println(ans);
System.out.println(ans.length());
}

//A*(A-star)で15パズルを解く
String astar(int[][] board) {
Set<String> done = new HashSet<String>(); //既出パターンチェック用
Queue<Puzzle> q = new PriorityQueue<Puzzle>();

Puzzle p = new Puzzle();
p.setBoard(board); //初期の盤の状態をセットする
p.estimate = p.md; //推定値
q.add(p);
done.add(p.toString());

while (!q.isEmpty()) {
p = q.poll();
if (p.md == 0) { //全てのパネルが揃ったら0
return p.path; //空白の移動経路
}

done.add(p.toString());
int sx = p.space % N; //空白の位置
int sy = p.space / N;

for (int i = 0; i < dx.length; i++) {
int nx = sx + dx[i]; //空白の移動位置
int ny = sy + dy[i];
if (nx < 0 || N <= nx || ny < 0 || N <= ny) { //範囲外
continue;
}

Puzzle p2 = p.clone();
p2.changeSpace(nx, ny); //空白と数字パネルを入れ替える(スライドする)
if (!done.contains(p2.toString())) { //既出パターンチェック
p2.cost++; //手数
p2.estimate = p2.md + p2.cost; //推定値
//p2.estimate = p2.md; //推定値(実行速度を優先したいときはこっちにする)
p2.path += dir[i]; //空白の移動経路(移動方向の記録)
q.add(p2);
}
}
}

return "unsolvable"; //完成できなかったとき
}

//パズルの状態を保存する構造体(クラス)
class Puzzle implements Cloneable, Comparable<Puzzle> {
int[] panel = new int[NN]; //各位置にあるパネル番号(番号は1ベース)
int space; //空白のインデクス
int md; //全パネルのマンハッタン距離の合計
int cost; //手数
int estimate; //推定値
String path = ""; //空白の移動経路(移動方向の記録)

//盤の並びをセットする
void setBoard(int[][] board) {
int p = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] == 0) { //空白
panel[p] = NN; //空白は最大値にする
space = p; //空白のインデクス
} else {
panel[p] = board[i][j];
}
p++;
}
}

calcMD(); //全パネルのマンハッタン距離の合計を求める
}

//全パネルのマンハッタン距離の合計を求める
void calcMD() {
md = 0;
for (int i = 0; i < NN; i++) {
if (panel[i] != NN) { //空白は除外する
md += MDTable[i][panel[i] - 1]; //番号は1ベース
}
}
}

//空白と数字パネルを入れ替える(スライドする)
void changeSpace(int x, int y) {
int index = x + y * N; //インデクスに変換
md += MDTable[space][panel[index] - 1]; //全パネル距離合計から移動後の数字パネル距離を足す(差分計算)
md -= MDTable[index][panel[index] - 1]; //全パネル距離合計から現在の数字パネル距離を引く
panel[space] = panel[index]; //数字パネルを交換(スライド)
panel[index] = NN; //空白を交換
space = index; //空白のインデクス更新
}

//比較関数
@Override
public int compareTo(Puzzle o) {
return this.estimate - o.estimate; //推定値で小さい順
}

//盤の状態を文字列にする(既出パターンのキーとしても利用)
@Override
public String toString() {
StringBuilder sb = new StringBuilder(NN * 3);
for (int i = 0; i < NN; i++) {
if (i > 0) {
if (i % N == 0) {
sb.append("\n");
} else {
sb.append(" ");
}
}
sb.append(panel[i]);
}
return sb.toString();
}

//盤の状態を複製する
@Override
public Puzzle clone() {
try {
Puzzle obj = (Puzzle)super.clone();
obj.panel = this.panel.clone();
return obj;
} catch (CloneNotSupportedException e) {
throw new RuntimeException();
}
}
}
}

rrdllldruuurdllddrurrd

 答えとなる移動経路の文字列は空白の移動のものなので、人の指で数字パネルを動かす方向(スライド)は逆となる(空白が右に動くということは、数字パネルは左に動く)。スライド方向で表示したいときは上下左右を反転するメソッドでも付け加えると良いだろう。

 推定値は「各パネルが正しい並び(位置)に移動するのに必要な距離の総和+手数」になっている。指で数字パネルをスライドできる方向は4方向なので、移動コスト(距離)は「マンハッタン距離」になる。その各パネルの距離を合計したものが、全パネルを揃えるのに最低でも必要な手数と考えるわけだ(よって全てが揃ったとき、全距離の総和: md = 0となる)。手数より実行速度を優先したければ、推定値は md だけでも良い。

 グローバル変数の静的ブロックで「MDTable」(ManhattanDistanceTable)というものを作っているが、15 パズルはパネルが 16 個固定なので、各パネルの距離を一覧表として作成してあるだけである。リアルタイムで計算しても良いが、どうせ同じ答えになるのなら、このように配列化しておくと実行速度が速い。推定値の比較はパズルの状態を保存する構造体(Puzzle)に Comparable インタフェースを噛ませて、PriorityQueueで比較している。探索の優先順位などを変えたければここをいじるのが一番手っ取り早いだろう。

 空白と数字パネルを入れ替えるメソッド「Puzzle.changeSpace()」では、数字パネルの移動による md (ManhattanDistance) の差分を計算しているが、わかりにくければ、空白と数字パネルを入れ替え、空白のインデクス更新した後に、全パネルのマンハッタン距離の合計を求めるメソッド「Puzzle.calcMD()」を呼び出す方法でも良い。実行速度を優先したければ、差分の計算のままが良いだろう。

 既出パターン(パネルの並び方)の検出に Set(重複要素のないコレクション) を使っているが、Map(連想配列)でも良い。他の言語に移植するときは連想配列の方が互換性が高いかも知れない(今回は存在チェックだけで値を必要としないので、Set にした)。また、既出パターンのキーをデバッグ用の全パネルの数字を表示するメソッド「Puzzle.toString()」(System.out.println(p) などで並びを表示できる)の文字列を、手抜き(笑)でそのまま使ってしまっているが、パネルは15個(16)なので、16進数にするなど別の文字列に置き換えても良いだろう。少しだけメモリ節約になるかも知れない。


 また、今回の元ネタは「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」という本に載っている C++ での解法だ。それを Java で自分なりに書き換えたものと言って良い。内容的にはほぼ同じはずだが、手本はあくまでも単純な書き方(すべての機能を一続きに書くような)になっているものが多いので、今回は問題提示部分と探索部分、パズル内での動作をそれぞれにまとめ、なるべく機能分離するようにしてある。こうすると似たような構成のパズルなら、構造体(クラス)やプロパティ、メソッドを少し改造するだけで、再利用できる可能性が増えるからだ。解法を見なくてもそらで書けるようになったら、自分なりのコードも書けるようになる。前回の迷路探索とあまり変わらないのはそのためだ。色々いじってみると良いだろう。


(関連記事)
【Java】A*(A-star, エースター)アルゴリズムで迷路を探索する
【Java】ダイクストラ法[単一始点最短経路] (Dijkstra's algorithm, Single Source Shortest Path)
【Java】ハノイの塔を解く
【Java】8クイーンを解く[8クイーン問題]


■参考になる書籍


スポンサーサイト

category: Java

thread: プログラミング

janre: コンピュータ

tag: アルゴリズム  最短経路  幅優先探索  パズル解法 
tb: 0   cm: --

【Java】A*(A-star, エースター)アルゴリズムで迷路を探索する  


 A*(A-star, エースター)探索アルゴリズムとは簡単に言えばダイクストラ法に推定値を用いた最良優先探索アルゴリズムである。「推定値」というくらいなので正確さに欠けるときもあるが、通常は枝刈り(一部探索を打ち切ること)が行われるので、実行速度が速いという特徴がある。ヒューリスティクス探索と呼ばれることもある。そういう特徴からゲームなどに使われることも多い。敵AIがプレイヤーを追跡するのにも使える。

 以前、頂点と辺でのダイクストラ法を書いたが、比較してみると、ほとんどダイクストラ法と変わらない事がわかるだろう。実際「推定値」を使って比較している部分を「移動コスト」に書き換えればダイクストラ法そのものになる。

●A*(A-star)アルゴリズムで迷路探索
import java.util.PriorityQueue;
import java.util.Queue;

public class MazeShortestAstar {

public static void main(String[] args) throws Exception {
new MazeShortestAstar();
}

static final int INF = Integer.MAX_VALUE; //INF値

//4方向探索用
static final int[] dx = { 0, 1, 0, -1};
static final int[] dy = {-1, 0, 1, 0};
static final char[] dir = {'u', 'r', 'd', 'l'};

String path = ""; //移動経路(戻値用)

//マンハッタン距離を求める
static int getManhattanDistance(int x1, int y1, int x2, int y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}
//チェビシェフ距離を求める
static int getChevyshevDistance(int x1, int y1, int x2, int y2) {
return Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2));
}

public MazeShortestAstar() {

int n = 10; //↓方向
int m = 10; //→方向
String[] maze = new String[]{
"S..#...#..",
".#.#.#.#.#",
"...#.#....",
"##...#.##.",
".....#.#..",
".#####.#.#",
".......#..",
"##.######.",
"...#...#..",
".#...#...G",
};

int ans = astar(n, m, maze);
System.out.println(ans);
System.out.println(path);
}

//A*(A-star)探索アルゴリズム
int astar(int n, int m, String[] maze) {
int[][] grid = new int[n][m]; //移動コスト(距離)の記録
int sx, sy, gx, gy; //スタートとゴール位置
sx = sy = gx = gy = 0;

//迷路データのパース
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maze[i].charAt(j) == '#') {
grid[i][j] = -1; //壁
} else if (maze[i].charAt(j) == 'S') {
grid[i][j] = 0; //スタートは距離0
sy = i;
sx = j;
} else if (maze[i].charAt(j) == 'G') {
grid[i][j] = INF;
gy = i;
gx = j;
} else {
grid[i][j] = INF;
}
}
}

//A*(A-star) 探索
Queue<Position> q = new PriorityQueue<Position>();

Position p = new Position(sx, sy);
p.estimate = getManhattanDistance(sx, sy, gx, gy); //推定値
q.add(p);

while (!q.isEmpty()) {
p = q.poll();
if (p.cost > grid[p.y][p.x]) {
continue;
}
if (p.y == gy && p.x == gx) { //ゴールに到達
path = p.path; //移動経路(戻値用)
break;
}

for (int i = 0; i < dx.length; i++) {
int nx = p.x + dx[i];
int ny = p.y + dy[i];
if (nx < 0 || m <= nx || ny < 0 || n <= ny) { //範囲外
continue;
}
if (grid[ny][nx] > grid[p.y][p.x] + 1) {
grid[ny][nx] = grid[p.y][p.x] + 1;

Position p2 = new Position(nx, ny);
p2.cost = grid[ny][nx]; //移動コスト(スタートからの移動量)
p2.estimate = getManhattanDistance(nx, ny, gx, gy) + p2.cost; //推定値
p2.path = p.path + dir[i]; //移動経路(移動方向の記録)
q.add(p2);
}
}
}

return grid[gy][gx]; //見つからないときは INF 値になる
}

//位置情報の構造体
class Position implements Comparable<Position>{
int x; //座標
int y;
int cost; //移動コスト(スタートからの移動量)
int estimate; //推定値(ゴールまでのマンハッタン距離+移動コスト)
String path = ""; //移動経路(移動方向の記録)

//コンストラクタ
public Position(int x, int y) {
this.x = x;
this.y = y;
}

//比較関数
@Override
public int compareTo(Position o) {
return this.estimate - o.estimate; //推定値で小さい順
}
}
}

24
rrddddllddrrdddrrurrdrrr

 ゴールに到達できなかったときは、戻値が INF 値(Integer.MAX_VALUE)になる。ダイクストラ法と同じように、コストに負の値は使えない(大小関係が崩れる、無限ループするなど)。今回は各位置への移動コストは1固定だが、迷路データによってコストを変えることもできる。例えば毒を受ける道はコスト2かかるなどという感じだ。その場合は迷路をパースする際に値を設定し、移動判定の部分「if (grid[ny][nx] > grid[p.y][p.x] + 1) {~}」の「+1」など、コストに関わる部分をそのコストに置き換えれば良い。

 今回は4方向の移動にしてるので、推定値は「ゴールまでのマンハッタン距離+スタートからの移動量」にしている。8方向移動にするのなら、チェビシェフ距離の方が良いだろう。正確さを加えるために、推定値が同じときは、移動コストで比較するという推定値を2重にする方法もあるが、実際にやってみると、例えば障害物があまりない、広いフロアのような迷路データではダイクストラ法と同じ動作になってしまうため、4方に探索の手が伸ばされ、枝刈り効果がなくなる。実行速度と正確さのどちらかで使い分けた方が無難だろう。

 また、推定値に移動コストを足す理由を少し考えてみよう。例えばゴールまでの距離だけだと最短は円形(4方向の場合はひし形になるが)に広がるので、反対方向も同じになる。だからそこに辿り着くまでの移動コストが足されていれば、遠回りは最短候補から外れて枝刈りができるわけだ。つまり逆に遠回りが最短のときは効果が少ない。またこの推定値の意味を考えるなら「ここを通ってスタートからゴールへ行くには、たぶんN歩かかる」という値(N)と考えればわかりやすい。

 推定値の比較は位置情報の構造体(Position)に Comparable インタフェースを噛ませて、PriorityQueueで比較している。探索の優先順位などを変えたければここをいじるのが一番手っ取り早いだろう。冒頭にも書いたが、比較関数「compareTo()」の戻値「this.estimate - o.estimate」を「this.cost - o.cost」に書き換えればダイクストラ法となる。推定値は基本的に最短かそれ以下にしておかないと上手く動作できないが、探索の目的によって色々変えてみたり、条件で分岐させるのも良いかも知れない。とはいえ私も色々計算方法を試してみたが、この「ゴールまでの最短距離+移動コスト」が平均的に効率が良いようだ。斜め移動を含む8方向での距離計算用に、チェビシェフ距離を求める「getChevyshevDistance()」をオマケとして付けてあるが、今回は使ってない。

 以下はデバッグ用に出力した各データをキャプチャしてみたものだ。「cost」はスタートからの移動量、「sequence」は探索した順序、「estimate」は計算された推定値、「count」は探索した回数、「path」はゴールまでの移動手順、色を付けてある「-1」は壁で、「X」は枝刈りされて未探索の場所だ。「Dijkstra」(ダイクストラ)は先に述べたように、比較関数を移動コストに変更しただけだ。動きの違いを見てみると、「A-Star」の方が大きく枝刈りされていて、探索回数が少なくなっている。実行速度を優先したい場合には有用だということがわかるだろう。


 この例では戻値はスタートからゴールまでの移動コストを返しているが、簡単な移動経路(移動方向の記録)もついでに返している(グローバル変数なのは手抜き(笑))。本来ならリストで座標を返すべきかも知れないが、まぁ、ラーニング用コードなのでこれで十分だろう。この移動経路から座標を計算するか、リストなどに順次座標を追加していくように改造すれば、簡単に実現できる。

 また、今回のコードは幅優先探索をベースとした枝刈りアルゴリズムということになるが、深さ優先探索をベースとした「反復深化」という手法もある。一般的に深さ優先探索幅優先探索よりメモリが少なくて済むので、携帯デバイスなどで使うときにはメリットがあるかも知れない。ゲームのようにリアルタイムで状況が変化するものは、正確さより実行速度を要する場合が多いので、ヒューリスティクス的なアルゴリズムは学習価値があるだろう。パフォーマンスが大きく改善される可能性もある。色々試してみると良いだろう。


(関連記事)
【Java】15パズルを解く [A*(A-star)アルゴリズム]
【Java】ダイクストラ法[単一始点最短経路] (Dijkstra's algorithm, Single Source Shortest Path)
【Java】プリム法[最小全域木] (Prim's algorithm, Minimum Spannig Tree)
【Java】ベルマン-フォード法[単一始点最短経路] (Bellman-Ford algorithm, Single Source Shortest Path)


■参考になる書籍


category: Java

thread: プログラミング

janre: コンピュータ

tag: アルゴリズム  最短経路  幅優先探索 
tb: 0   cm: --

【Java】ダイクストラ法[単一始点最短経路] (Dijkstra's algorithm, Single Source Shortest Path)  


 前回プリム法最小全域木を求めるアルゴリズム(全ての頂点を最小コストで繋ぐ)だったが、少し似ている単一始点最短経路アルゴリズム(始点から到達点までの最短距離)にダイクストラ法がある。考え方は同じようなもので、プリム法は最小となる各辺のコストを記録するのに対し、ダイクストラ法は始点から各頂点までの距離を最短で記録していく方法だ。Wikipedia によると、元々プリム法を参考にしたようなので(?)、少し書き換えるだけで簡単に作れる。

 今回も前回と比較するために、同じ辺情報の構造体を使ってやってみよう。

●ダイクストラ法[単一始点最短経路] Dijkstra
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Dijkstra {

public static void main(String[] args) throws Exception {
new Dijkstra();
}

public Dijkstra() {
//Wikipedia の例(図)をデータにしたもの
int n = 6; //頂点数
int s = 0; //スタート頂点(頂点番号は -1 されている[元は 1])
int g = 4; //ゴール頂点(頂点番号は -1 されている[元は 5])
int[][] adj = new int[][]{
//接続元ノード, 接続先ノード, 重み
{0, 1, 7},
{0, 2, 9},
{0, 5, 14},
{1, 2, 10},
{1, 3, 15},
{2, 3, 11},
{2, 5, 2},
{3, 4, 6},
{4, 5, 9}
}; //s:0 → g:4 のとき、答えは 20

//隣接リスト
@SuppressWarnings("unchecked")
List<Edge>[] edges = new List[n];
for (int i = 0; i < n; i++) {
edges[i] = new ArrayList<Edge>();
}

for (int i = 0; i < adj.length; i++) {
edges[adj[i][0]].add(new Edge(adj[i][0], adj[i][1], adj[i][2]));
edges[adj[i][1]].add(new Edge(adj[i][1], adj[i][0], adj[i][2])); //無向グラフなので、逆方向も接続する
}

int ans = dijkstra(n, edges, s, g);
System.out.println(ans); //s → g の最短距離
}

static final int INF = 100100100; //INF 値(十分に大きな値)

//ダイクストラ法[単一始点最短経路(Single Source Shortest Path)]
int dijkstra(int n, List<Edge>[] edges, int s, int g) {
int[] distance = new int[n]; //始点からの最短距離

Arrays.fill(distance, INF); //各頂点までの距離を初期化(INF 値)
distance[s] = 0; //始点の距離は0

Queue<Edge> q = new PriorityQueue<Edge>();
q.add(new Edge(s, s, 0)); //始点を入れる

while (!q.isEmpty()) {
Edge e = q.poll(); //最小距離(cost)の頂点を取り出す
if (distance[e.target] < e.cost) {
continue;
}

//隣接している頂点の最短距離を更新する
for (Edge v : edges[e.target]) {
if (distance[v.target] > distance[e.target] + v.cost) { //(始点~)接続元+接続先までの距離
distance[v.target] = distance[e.target] + v.cost; //現在記録されている距離より小さければ更新
q.add(new Edge(e.target, v.target, distance[v.target])); //始点~接続先までの距離
}
}
}

return distance[g]; //到達できなかったときは、INF となる
}

//辺情報の構造体
class Edge implements Comparable<Edge> {
public int source = 0; //接続元ノード
public int target = 0; //接続先ノード
public int cost = 0; //重み

public Edge(int source, int target, int cost) {
this.source = source;
this.target = target;
this.cost = cost;
}

@Override
public int compareTo(Edge o) {
return this.cost - o.cost; //重みの小さい順
}

@Override
public String toString() { //デバッグ用
return "source = " + source + ", target = " + target + ", cost = " + cost;
}
}
}

20

 ゴールの頂点に到達できなかったときは、戻値が INF 値(十分に大きな値)になる。ダイクストラ法の性質上、辺のコストに負の値は使えない(大小関係が崩れる、無限ループするなど)。

 隣接リストは List<Edge>[] のように List の配列で作っている。List のリスト(List<List<Edge>>)でも良いが、頂点数が固定なら、この方が簡潔だろう。「@SuppressWarnings("unchecked")」は警告を消しているだけなので、無くても動く。

 優先度付きキュー(PriorityQueue)に追加される辺情報(Edge)は始点からの距離(cost)を持った構造体を突っ込んでいる。つまり取り出されるのは、始点から順次繋がってきた頂点のいずれかの最短距離となる。

 優先度付きキュー(PriorityQueue)の順番は辺情報の構造体(Edge)に Comparable インタフェースを噛ませて、コストを比較しているが、PriorityQueue のコンストラクタに Comparator を匿名クラスで定義しても良いだろう。そうすれば優先順位は色々変更できる。例えば優先順位に「推定値」を用いれば「A*(A-star, エースター)アルゴリズム」となる。


 この例では戻値は単一始点最短経路のコストを返しているが、選択した辺を知りたければ、少し改造して、各頂点の最短距離を更新するときに、その接続元を記録しておき、逆から辿れば(到達点→始点)わかる。頂点番号だけでも良いが、今回は前回に合わせて、辺情報の構造体で返すようにしてみよう。

●ダイクストラ法で選択した辺を返す版
・・・(略)・・・
import java.util.Collections;

public class Dijkstra {
・・・(略)・・・
public Dijkstra() {
・・・(略)・・・
List<Edge> paths = new ArrayList<Edge>(); //選択した辺(戻値用)

int ans = dijkstra(n, edges, s, g, paths);
System.out.println(ans); //s → g の最短距離

//選択した辺(確認)
int len = paths.size();
for (int i = 1; i < len; i++) { //一番最初[0]は始点のためスキップ
System.out.println(paths.get(i));
}
}

static final int INF = 100100100; //INF 値(十分に大きな値)

//ダイクストラ法[単一始点最短経路(Single Source Shortest Path)]
//選択した辺を返す
int dijkstra(int n, List<Edge>[] edges, int s, int g, List<Edge> paths) {
int[] distance = new int[n]; //始点からの最短距離
int[] parent = new int[n]; //接続元ノード

Arrays.fill(distance, INF); //各頂点までの距離を初期化(INF 値)
distance[s] = 0; //始点の距離は0
Arrays.fill(parent, -1); //-1 は始点または未到達

Queue<Edge> q = new PriorityQueue<Edge>();
q.add(new Edge(s, s, 0)); //始点を入れる

while (!q.isEmpty()) {
Edge e = q.poll(); //最小距離(cost)の頂点を取り出す
if (distance[e.target] < e.cost) {
continue;
}

//隣接している頂点の最短距離を更新する
for (Edge v : edges[e.target]) {
if (distance[v.target] > distance[e.target] + v.cost) { //(始点~)接続元+接続先までの距離
distance[v.target] = distance[e.target] + v.cost; //現在記録されている距離より小さければ更新
q.add(new Edge(e.target, v.target, distance[v.target])); //始点~接続先までの距離
parent[v.target] = e.target; //接続元を記録
}
}
}

//選択した辺(逆から辿る[到達点→始点])
paths.clear();
if (parent[g] > -1) {
int p = g;
while (p > -1) {
paths.add(new Edge(parent[p], p, distance[p]));
p = parent[p];
}
Collections.reverse(paths); //反転する(始点→到達点)
}

return distance[g]; //到達できなかったときは、INF となる
}
・・・(略)・・・
}

20
source = 0, target = 2, cost = 9
source = 2, target = 5, cost = 11
source = 5, target = 4, cost = 20

 頂点だけで良ければ、選択した辺を作っている所を、List<Integer> などにして、p だけを追加していけば良い(引数部分も型に合わせる)。[0] は始点になるので、List.remove(0) で除去しても良い。

 隣接行列を使ったり、優先度付きキュー(PriorityQueue)使わない方法もあるが、辺が多いときはオーダーが O(V2) [V:頂点の数] になるので注意。PriorityQueue を使う場合は実装にもよるが、おおよそ O(E lon V) [E:辺の数, V:頂点の数] と考えておけば良いだろう。

 迷路で敵がプレイヤーを追跡するときなどにも良いかもね(ただし、大きな迷路などでは A*(A-star, エースター)[ダイクストラ法に推定値を入れ、枝刈りをするアルゴリズム]などが使われる事が多い)。その場合、このサンプルでは最後まで探索を行っているが、最短距離を求めた時点で探索終了した方が効率的だろう。実装が簡単なので、色々改造して使うと良い。


(関連記事)
【Java】A*(A-star, エースター)アルゴリズムで迷路を探索する
【Java】ベルマン-フォード法[単一始点最短経路] (Bellman-Ford algorithm, Single Source Shortest Path)
【Java】ワーシャル-フロイド法[全点対間最短経路] (Warshall-Floyd algorithm, All Pairs Shortest Path)
【Java】プリム法[最小全域木] (Prim's algorithm, Minimum Spannig Tree)
【Java】クラスカル法[最小全域木] (Kruskal's algorithm, Minimum Spannig Tree)


■参考になる書籍


category: Java

thread: プログラミング

janre: コンピュータ

tag: アルゴリズム  最短経路  幅優先探索 
tb: 0   cm: --

【Java】プリム法[最小全域木] (Prim's algorithm, Minimum Spannig Tree)  


 前回のついでに、クラスカル法と同様、最小全域木を求めるアルゴリズムとしてプリム法というアルゴリズムがある。解説などは Wikipedia や他のホームページなどに譲るとして、前回と比較するために、同じ例を使って書いてみる。

●プリム法[最小全域木] Prim
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Prim {

public static void main(String[] args) throws Exception {
new Prim();
}

public Prim() {
//Wikipedia の例(図)をデータにしたもの
int n = 7; //頂点数
int[][] adj = new int[][]{
//接続元ノード, 接続先ノード, 重み
{0, 1, 7},
{0, 3, 5},
{1, 2, 8},
{1, 3, 9},
{1, 4, 7},
{2, 4, 5},
{3, 4, 15},
{3, 5, 6},
{4, 5, 8},
{4, 6, 9},
{5, 6, 11}
}; //答えは 39

//隣接リスト
@SuppressWarnings("unchecked")
List<Edge>[] edges = new List[n];
for (int i = 0; i < n; i++) {
edges[i] = new ArrayList<Edge>();
}

for (int i = 0; i < adj.length; i++) {
edges[adj[i][0]].add(new Edge(adj[i][0], adj[i][1], adj[i][2]));
edges[adj[i][1]].add(new Edge(adj[i][1], adj[i][0], adj[i][2])); //無向グラフなので、逆方向も接続する
}

int ans = prim(n, edges);
System.out.println(ans); //最小全域木の重み
}

//プリム法[最小全域木(Minimum Spannig Tree)]
int prim(int n, List<Edge>[] edges) {
boolean[] done = new boolean[n]; //訪問フラグ

Queue<Edge> q = new PriorityQueue<Edge>();
q.add(new Edge(0, 0, 0)); //0から(ダミー)

int totalCost = 0; //最小全域木の重み
while (!q.isEmpty()) {
Edge e = q.poll(); //最小コストの辺を取り出す
if (done[e.target]) {
continue;
}

done[e.target] = true; //訪問済にする
totalCost += e.cost;
q.addAll(edges[e.target]); //隣接しているすべての辺を追加
}

return totalCost;
}

//辺情報の構造体
class Edge implements Comparable<Edge> {
public int source = 0; //接続元ノード
public int target = 0; //接続先ノード
public int cost = 0; //重み

public Edge(int source, int target, int cost) {
this.source = source;
this.target = target;
this.cost = cost;
}

@Override
public int compareTo(Edge o) {
return this.cost - o.cost;
}

@Override
public String toString() { //デバッグ用
return "source = " + source + ", target = " + target + ", cost = " + cost;
}
}
}

 隣接リストは List<Edge>[] のように List の配列で作っている。List のリスト(List<List<Edge>>)でも良いが、頂点数が固定なら、この方が簡潔だろう。「@SuppressWarnings("unchecked")」は警告を消しているだけなので、無くても動く。

 優先度付きキュー(PriorityQueue)には一番始めにダミーを入れているが、最小全域木はどこから始めても同じなので、0(頂点)以外でも良い(その場合は Edge の source と target は同じにして、cost は 0 にする)。

 頂点から伸びている辺のリストは、無造作にキューに入れてしまっているが、訪問(done)し終わった頂点は不要なので、キューに入れる前に、はじいても良い。辺が大量にあるデータなら少しは速くなるかも知れない(この例では簡単にするため、一気にすべて突っ込んでいる)。

 優先度付きキュー(PriorityQueue)の順番は辺情報の構造体(Edge)に Comparable インタフェースを噛ませて、コストを比較しているが、PriorityQueue のコンストラクタに Comparator を匿名クラスで定義しても良いだろう。そうすれば優先順位は色々変更できる。


 この例では戻値は最小全域木の総コストを返しているが、選択した辺を知りたければ、少し改造して辺のリストを記録すれば良い。

●プリム法で選択した辺を返す版
・・・(略)・・・
import java.util.LinkedList;

public class Prim {
・・・(略)・・・
public Prim() {
・・・(略)・・・
List<Edge> paths = new LinkedList<Edge>(); //選択した辺(戻値用)

int ans = prim(n, edges, paths);
System.out.println(ans); //最小全域木の重み

//選択した辺(確認)
int len = paths.size();
for (int i = 1; i < len; i++) { //一番最初[0]はダミーのためスキップ
System.out.println(paths.get(i));
}
}

//プリム法[最小全域木(Minimum Spannig Tree)]
//選択した辺を返す
int prim(int n, List<Edge>[] edges, List<Edge> paths) {
boolean[] done = new boolean[n]; //訪問フラグ

Queue q = new PriorityQueue();
q.add(new Edge(0, 0, 0)); //0から(ダミー)

paths.clear();
int totalCost = 0; //最小全域木の重み
while (!q.isEmpty()) {
Edge e = q.poll(); //最小コストの辺を取り出す
if (done[e.target]) {
continue;
}

done[e.target] = true; //訪問済にする
totalCost += e.cost;
paths.add(e); //選択した辺を記録(一番最初はダミー)
q.addAll(edges[e.target]); //隣接しているすべての辺を追加
}

return totalCost;
}
・・・(略)・・・
}

 辺のリストの [0] はダミーになるので、List.remove(0) で除去しても良い。

 隣接行列を使ったり、優先度付きキュー(PriorityQueue)を使わずに、配列に最小コストを記録していく方法もあるが、かえって難しい気がする。色々やってみると良いだろう。


(関連記事)
【Java】クラスカル法[最小全域木] (Kruskal's algorithm, Minimum Spannig Tree)
【Java】素集合データ構造[互いに素な集合] (Union Find Tree, Disjoint Set Forest)
【Java】ダイクストラ法[単一始点最短経路] (Dijkstra's algorithm, Single Source Shortest Path)
【Java】ベルマン-フォード法[単一始点最短経路] (Bellman-Ford algorithm, Single Source Shortest Path)
【Java】ワーシャル-フロイド法[全点対間最短経路] (Warshall-Floyd algorithm, All Pairs Shortest Path)


■参考になる書籍


category: Java

thread: プログラミング

janre: コンピュータ

tag: アルゴリズム  最短経路  幅優先探索 
tb: 0   cm: --
IS<インフィニット・ストラトス> アーキタイプ・ブレイカー
キルドヤ


プロフィール

Twitter

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop