ヽ|∵|ゝ(Fantom) の 開発blog? ホーム »最短経路
このページの記事一覧

【Java】パスカルの三角形を使って組合せを求める  


 前回、漸化式を使っての組合せの数を求めたが、別の解法として「パスカルの三角形」を利用して組合せを求める方法もある。パスカルの三角形とは「二項係数」とか「二項定理」とも呼ばれ、高校数学でやった二項式を展開するときの係数に合致しているが、他にも色々利用できる性質がある。



 まずは簡単に作り方を覚えてしまおう。非常に単純なので一度聞いたら忘れることもないだろう。作り方は以下のようになる。

1.頂点(一番上)に「1」を書き、ここをスタート地点とする。

2.スタート地点から左右(矢印の方向:斜め下)に向かって進んでいく。その際、交差する地点はその1つ前の値を合計する。これを繰り返す。

 これは道に例えると「網の目のように必ず2つの分岐点がある道を進むとき、その地点に最短で辿り着く方法は何通りあるか?」という数になる。つまり、地点Aに辿り着く方法が2通り、地点Bに辿り着く方法が1通りあるとき、その地点AとBが合流する地点Cは 2+1=3 通りあるという単純なものである。

 そしてこの値は、以下のように組合せを求める式の答えとも合致している。


 つまりこのパスカルの三角形を作ることをシミュレーションすれば、組合せの数も簡単に求めることができるというわけだ。さっそく上記の作り方をそのままコーディングしてみよう。

●パスカルの三角形を作る [O(hw)]
/**<h1>パスカルの三角形を作る</h1>
* <p>パスカルの三角形を斜めに傾けた配列を作成。左上が(0,0)で右下に拡がる感じになる。</p>
* @param w : 横数 (1~33)
* @param h : 縦数 (1~33)
* @return<b>long[][]</b> : パスカルの三角形を配列化したもの
*/
public static final long[][] pascalsTriangle(final int w, final int h) {
final long[][] arr = new long[h + 1][w + 1];
arr[0][0] = 1;

for (int i = 0; i <= h; i++) {
for (int j = 0; j <= w; j++) {
if (j > 0) {
arr[i][j] += arr[i][j - 1];
}
if (i > 0) {
arr[i][j] += arr[i - 1][j];
}
}
}

return arr;
}


//メインでは...
int w = 5;
int h = 4;
long[][] pascal = pascalsTriangle(w, h); //パスカルの三角形

 パスカルの三角形を下の図のように斜め45度傾けて配列に入れたと考えれば簡単だろう。


 つまり組合せの数を求めたいなら、この表を作って、値を取得すれば良いということになる。例えば、5C3 を求めたければ、配列の pascal[3][2] = 10 が「5個のものから3個取り出す組合せ」の数になる。nCr に置き換えれば、pascal[n - r][r] となる。また表を見てわかるように、対角線で値が対称になっているので、5C3 = 5C2 (nCr = nCn-r) となり、配列の縦横を入れ替えても同じとなる。もし、関数として作って置きたいなら、以下のような感じにすれば良い。

●パスカルの三角形から組合せの数を求める [O(n2)]
/**<h1>n 個のものから r 個取り出した組合せの数を求める</h1>
* <p>nCr をパスカルの三角形から求める。
* <br>n, r が 大きすぎるとオーバーフローするので注意。</p>
* @param n : すべての数 (1~66) (負の値はエラー)
* @param r : 取り出す数 (1~33) (負の値はエラー)
* @return<b>long</b> : 組合せの数
*/
public static final long combination(final int n, final int r) {
if (n < 0 || r < 0 || n < r) {
throw new ArithmeticException("n = " + n + ", r = " + r);
}
if (r == 0 || r == n) {
return 1;
}
if (r == 1) {
return n;
}

//パスカルの三角形
final long[][] pascal = pascalsTriangle(r, n - r);
return pascal[n - r][r];
}

 漸化式での組合せ[O(n)]と比べたメリットは、計算が単純な加算しかしていないため、オーバフローが少しばかりしにくい所だろうか。また、大量に計算するなら、1つパスカルの三角形を作っておいて[O(n2)]、配列から値を取り出すだけにすれば[O(1)]、実行負荷はほとんど無くなる(例えば、30個の組合せを1000回計算するなら、漸化式では 30[O(n)]x1000回 = 30000回演算、パスカルの三角形なら 30x30[O(n2)]=900 +1000[O(1)]回 = 1900回演算で、計算量が少なくなるので速い)。しかし単体で計算するなら、毎回配列を作る[O(n2)]ので、実行速度は遅くなるので注意しよう。


 ここで試しに練習問題をやってみよう。これはどちらかというとプログラミング問題というより数学の問題だ。

4人でじゃんけんを1回するとき、あいこになる確率はどれくらいか?

//パスカルの三角形での解法
int n = 4; //4人
long[][] pascal = pascalsTriangle(n, n); //大きさは適当(n x n あればカバーできる)
long sum = 0; //勝敗がつく事象の合計
for (int i = 1; i < n; i++) { //4C1~4C3 まで(4人のうち1~3人勝つ[=勝敗がつく]組合せ)
sum += pascal[n - i][i];
}
sum *= 3; //グー、チョキ、パーの3手でそれぞれ勝てるため、3倍する
double d = 1.0 - sum / Math.pow(3, n); //あいこ = 全事象 - 勝敗がつく事象 [=余事象]
System.out.println(d); //0.4814814814814815 (13/27)

 答えは 約48% (= 13/27) である。「勝ち・負け・あいこの3つだから、1/3 じゃないの?」と思った人は気をつけよう。それは前回の「コイン4枚のうち2枚が表の確率」同様、ただ単に思い込みをしているだけだ。

 簡単に解法を書いてみると、じゃんけんの手はグー・チョキ・パーの3手だから、すべての事象は 3 x 3 x 3 x 3 = 81 通りである。このうち勝敗がつくのは4人のうち1~3人の誰かが勝てばいいわけだから、4C1 + 4C2 + 4C3 の合計になり、それぞれ3手あるので3倍になる。「あいこ」になる確率は「勝敗がつかない」確率だから、余事象を用いて (1 - 勝敗がつく事象) で、1 - 14/27 = 13/27 ≒ 0.48 (48%) となる。

 ちなみに、この問題はわざわざパスカルの三角形を使った解法で試してみたが、「n人でじゃんけんを1回するとき、あいこになる確率」を一般化すると、


となるので、一発計算で求めることもできる。

//あいこになる確率を一般化したものでの解法
int n = 4; //4人
double d = 1.0 - (Math.pow(2, n) - 2.0) / Math.pow(3, n - 1); //あいこ = 全事象 - 勝敗がつく事象 [=余事象]
System.out.println(d); //0.4814814814814815 (13/27)


 試しに 2人~20人でじゃんけんをしたとき、あいこになる確率を計算してみよう。

2人でじゃんけんを1回するとき、あいこになる確率 = 0.33333333333333337
3人でじゃんけんを1回するとき、あいこになる確率 = 0.33333333333333337
4人でじゃんけんを1回するとき、あいこになる確率 = 0.4814814814814815
5人でじゃんけんを1回するとき、あいこになる確率 = 0.6296296296296297
6人でじゃんけんを1回するとき、あいこになる確率 = 0.7448559670781894
7人でじゃんけんを1回するとき、あいこになる確率 = 0.8271604938271605
8人でじゃんけんを1回するとき、あいこになる確率 = 0.8838591678097851
9人でじゃんけんを1回するとき、あいこになる確率 = 0.922267946959305
10人でじゃんけんを1回するとき、あいこになる確率 = 0.9480770207793527
11人でじゃんけんを1回するとき、あいこになる確率 = 0.9653508103439516
12人でじゃんけんを1回するとき、あいこになる確率 = 0.9768892501707621
13人でじゃんけんを1回するとき、あいこになる確率 = 0.9845890700943284
14人でじゃんけんを1回するとき、あいこになる確率 = 0.9897247922786035
15人でじゃんけんを1回するとき、あいこになる確率 = 0.9931494433687528
16人でじゃんけんを1回するとき、あいこになる確率 = 0.9954328228623964
17人でじゃんけんを1回するとき、あいこになる確率 = 0.9969551687804513
18人でじゃんけんを1回するとき、あいこになる確率 = 0.9979700970332521
19人でじゃんけんを1回するとき、あいこになる確率 = 0.9986467261931519
20人でじゃんけんを1回するとき、あいこになる確率 = 0.9990978157413181

 つまり人数が増えていくたびに、あいこになる確率は限りなく 100% に近づいていく。5人以上のとき 60% を超え、9人以上のときは 90% を超えるので、もはや勝負がつかなくなる。人数が増えたとき、あいこが延々と続くようになるのはこういうことだ(笑)。人数が多いとき、4人以下で分割してじゃんけんした方が効率が良いことも理にかなっている。


 また、パスカルの三角形の作り方のコードを見て、アルゴリズマーな人なら(笑)、「あれ?このコード見たことあるな…」と思ったかもしれない。実はこれは「格子状の道の経路数を求める」(ヒョウ本 P.176~177)に載っている「動的計画法」のコードと同じだったりする。 

 その問題を挙げてみると、

以下のような格子状の道があるとき、S から G まで最短で移動する方法は何通りあるか?


というような問いである。

 実はこれも高校数学の教科書に載っているのだが、解法を簡単に書いてみると、下へ進む道を a 、右に進む道を b として1列に並べると、aaaabbbbb のようになり「9本の道から4本の道を選ぶ組合せの数」になることがわかる(9本の道から4本の道を a とすれば、残りの5本の道は b と決まるため)。そして、この格子状の経路は先のパスカルの三角形を斜めに倒した表と一致するので、全く同じコードになるわけだ。

 つまり、この格子状の経路を数え上げる問題は組合せの問題と本質的に同じになる。だから漸化式での方法でも一発で求めることができることになる。

 しかし、例えばこの格子状の道に通行止めがあった場合を考えよう。そうなると単純な組合せの計算一発では求められなくなる。その場合は、パスカルの三角形の作り方を改造すれば意外と簡単に求められるのだ。例えば先のパスカルの三角形を作るコードに通行止めのフラグでも入れて「その地点には行けない(経路数 = 0)」を挿入してしまえば良い。


●パスカルの三角形を改造して経路数を求める
//パスカルの三角形に通行止めフラグ(closed[][])を入れた
public static final long[][] pascalsTriangle(final int w, final int h, final boolean[][] closed) {
final long[][] arr = new long[h + 1][w + 1];
arr[0][0] = 1;

for (int i = 0; i <= h; i++) {
for (int j = 0; j <= w; j++) {
if (closed[i][j]) {
continue;
}
if (j > 0) {
arr[i][j] += arr[i][j - 1];
}
if (i > 0) {
arr[i][j] += arr[i - 1][j];
}
}
}

return arr;
}


//メインでは・・・
int w = 5;
int h = 4;
boolean[][] closed = new boolean[h + 1][w + 1];
closed[1][3] = true; //通行止め
closed[2][1] = true; //通行止め
closed[3][2] = true; //通行止め
long[][] pascal = pascalsTriangle(w, h, closed);
System.out.println(pascal[h][w]); //25 となる

 この手の経路数数え上げの問題は再帰を使うのも常套だが、平面を再帰で探索すると、O(2hw) くらいの計算量はかかってしまうので、非常に重くなる。あと、マスが 100 x 100 = 10000 を超えると Stack Overflow を起こすこともあるので気をつけよう。このパスカルの三角形を改造した解法(動的計画法)なら、計算量は O(hw) でしかない。

 組合せの数と経路数の数え上げのロジックが繋がっていることを覚えておくと、利用価値があるかもしれない。色々考察してみると良いだろう。


(関連記事)
【Java】組合せの数を求める
【Java】順列の数を求める
【Java】プリミティブ型での階乗計算
【Java】1000000!のような巨大な階乗計算をする [任意精度整数(多倍長整数)]
【Java】任意精度整数(多倍長整数)で演算する


■参考になる書籍


スポンサーサイト

category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数  動的計画法  最短経路  練習問題 
tb: 0   cm: --

【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】ワーシャル-フロイド法[全点対間最短経路] (Warshall-Floyd algorithm, All Pairs Shortest Path)  


 最小全域木(全ての頂点を最小コストで繋ぐ)、単一始点最短経路(始点から到達点までの最短距離)の他には全点対間最短経路(各頂点間の最小コスト[最短距離])を求めるアルゴリズムとしてワーシャル-フロイド法というものがある。

 解説などは Wikipedia他のホームページなどに譲るが、簡単な考え方としては、頂点(i → j)のコストと、中継点を含んだ(i → k → j)のコストを全パターン比較して、最小を求めることによって、各頂点同士の最短距離を記録していくと考えれば良い。紙に3つの頂点を書いて、(A → B と A → C → B)、(B → C と B → A → C)、(C → A と C → B → A)のようにぐるぐる基準点を回転して、小さいコストを記録していく感じだ。頂点が増えても、その三角路が組み合わさっている感じになる(実際には見えない頂点間も最短計算に使用している)。

 また、このアルゴリズムも負の閉路(辺の重みの総和が負になるような閉路)を検出できるという特徴がある。というのは、各頂点間のコストの表を初期化する際、配列の d[i][i] となるような位置を0にしておくと(つまり自分から自分までのコストは当然0なので)、負の閉路があった場合、負の値になることによって判断できるというものである(例えば、頂点(i → i)=0、k が負のコストのとき、(i → k → i)<0 になり、比較したとき負の値に更新される。k が正の場合は0以下になることはない)。

 今回は前回までの辺情報の構造体は使用しない。とりあえず例(図)はこちらと同じものを使わせてもらった。


例(頂点番号と辺の重みを表す)

●ワーシャル-フロイド法[全点対間最短経路] WarshallFloyd
public class WarshallFloyd {

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

public WarshallFloyd() {
//図をデータにしたもの
int n = 6; //頂点数
int[][] adj = new int[][]{
//接続元ノード, 接続先ノード, 重み
{0, 1, 1},
{0, 3, 2},
{0, 4, 3},
{1, 2, 4},
{1, 4, 1},
{2, 4, 1},
{2, 5, 3},
{3, 4, 2},
{4, 5, 3}
};

//辺の情報を無向グラフ用にする(有向グラフでも構わない)
int[][] edges = new int[adj.length * 2][3];
int len = adj.length;
for (int i = 0; i < len; i++) {
edges[i] = adj[i]; //そのままコピー(シャローコピー)
//無向グラフにしたいので、逆方向も接続する
edges[i + len][0] = adj[i][1];
edges[i + len][1] = adj[i][0];
edges[i + len][2] = adj[i][2];
}

int[][] ans = warshallFloyd(n, edges); //各頂点間の最短コスト(表)

//表を出力
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j > 0) {
System.out.print(" ");
}
if (ans[i][j] == INF) {
System.out.print("INF");
} else {
System.out.print(ans[i][j]);
}
}
System.out.println();
}

//負の閉路の判定
System.out.println("Negative Cycle = " + isNegativeCycle(ans));
}

static final int INF = Integer.MAX_VALUE; //INF 値((int)1e9, 1 << 30, Integer.MAX_VALUE / 2 などでも良い)

//ワーシャル-フロイド法[全点対間最短経路(All Pairs Shortest Path)]
int[][] warshallFloyd (int n, int[][] edges) {
//初期化
int[][] d = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
d[i][j] = (i == j) ? 0 : INF; //i と j が同じ位置(d[i][i])は、負の閉路チェックに使う
}
}

//隣接行列のように、重みを入れる
for (int i = 0; i < edges.length; i++) {
d[edges[i][0]][edges[i][1]] = edges[i][2];
}

//ワーシャル-フロイド法(全点対間最短経路)
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
if (d[i][k] == INF) {
continue;
}
for (int j = 0; j < n; j++) {
if (d[k][j] == INF) {
continue;
}
d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
}
}
}

return d;
}

//負の閉路チェック
boolean isNegativeCycle(int[][] d) {
int n = d.length;
for (int i = 0; i < n; i++) {
if (d[i][i] < 0) {
return true; //負の閉路がある
}
}
return false;
}
}


 今回の戻値は各頂点間での最小コスト(距離)の表となる。負の閉路のチェックは別の関数(isNegativeCycle())にしているが、最短路計算の関数(warshallFloyd())に入れて、d の代わりに null を戻すようにしても良いだろう(負の閉路があった場合、値が使えないので)。

 辺の情報は今までのように構造体は使わず、int[][] のまま使っている(ただし、無向グラフ用に逆方向を追加している。有向グラフでも構わない)。最短路計算(warshallFloyd())内で結果となる表(d[][])を初期化しているが、この「初期化~隣接行列のように、重みを入れる」部分を別の関数に独立すれば、他の形式に対応することもできるだろう。

 最短距離の更新する際の計算は INF 値のままでやるとオーバーフローを起こすので、処理をスキップしている。コードが長く感じるなら「if (d[i][k] == INF) continue;」のように1行にするのも良いだろう。

 オーダーは O(V3)なので、重い感じもするが、単一始点最短経路を全パターンやることを考えれば、こちらの方が簡潔だろう。そう考えれば、一気にそれぞれの頂点同士の最短を知りたいときに使える。ネットワーク上の負荷の軽い箇所を探すとかね。結果の○で囲んである値を図と比較してみると、最短に更新されているのがわかる。また、直接繋がってない経路(例えば、1 → 3 のような)コストも計算されていることがわかるだろう。負の閉路を試したければ、この例は無向グラフになっているので、適当にどこかのコストを負にすれば、Negative Cycle = true となる。


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


category: Java

thread: プログラミング

janre: コンピュータ

tag: アルゴリズム  最短経路 
tb: 0   cm: --

【Java】ベルマン-フォード法[単一始点最短経路] (Bellman-Ford algorithm, Single Source Shortest Path)  


 前回同様単一始点最短経路アルゴリズムにベルマン-フォード法がある。よく見ればわかるが、ダイクストラ法の最短距離の更新処理をそのまま抜き出した感じだったりする。ダイクストラ法との違いは、計算順序が辺の総当り的な方法になっていることだろう。そのためオーダーが O(VE)[頂点数×辺の数]になっている。

 また、そのオーダー O(VE)[頂点数×辺の数]から、負の閉路(辺の重みの総和が負になるような閉路)があったとき、最短距離の更新が無限ループすることから、負の閉路を検出することもできる。

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

●ベルマン-フォード法[単一始点最短経路] BellmanFord
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BellmanFord {

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

public BellmanFord() {
//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

//辺情報の配列を作る
List<Edge> list = new ArrayList<Edge>();
for (int i = 0; i < adj.length; i++) {
list.add(new Edge(adj[i][0], adj[i][1], adj[i][2]));
list.add(new Edge(adj[i][1], adj[i][0], adj[i][2])); //無向グラフなので、逆方向も接続する
}

Edge[] edges = list.toArray(new Edge[0]); //配列に変換

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

//ベルマン-フォード法[単一始点最短経路(Single Source Shortest Path)]
int bellmanford(int n, Edge[] edges, int s, int g) {
int[] distance = new int[n]; //始点からの最短距離
int[] count = new int[n]; //更新カウント(負の閉路チェック用)

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

boolean negative = false; //負の閉路フラグ
boolean update = true; //更新フラグ

while (update && !negative) {
update = false;
for (Edge e : edges) {
//接続元+接続先までの距離
if (distance[e.source] != Integer.MAX_VALUE && distance[e.source] + e.cost < distance[e.target]) {
distance[e.target] = distance[e.source] + e.cost; //現在記録されている距離より小さければ更新
update = true;

if (++count[e.target] >= n) { //負の閉路チェック
negative = true;
break;
}
}
}
}

if (negative) {
return Integer.MIN_VALUE; //負の閉路があったときは、-INF(Integer.MIN_VALUE)を返す
}
return distance[g]; //到達できなかったときは、INF(Integer.MAX_VALUE)になる
}

//辺情報の構造体
class Edge implements Comparable {
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;
}
}
}

 ゴールの頂点に到達できなかったときは、戻値が INF 値(Integer.MAX_VALUE)になる。また、負の閉路があったときは、-INF 値(Integer.MIN_VALUE)を返している。わかりにくければ、適当に -1 などに変更しても良いだろう。

 ベルマン-フォード法は辺の総当りなので、隣接リストではなく、より簡潔に、線形的な配列(Edge[])にしている。

 負の閉路の検出には各頂点の更新数(count[])で判別している。これは負の閉路がなければ、各頂点の更新は n - 1 を超えることはないからだ(例えば頂点が全部で5コなら、1つの頂点には辺は4つまでしか繋がらない=更新も4回まで)。オーダー O(VE)[頂点数×辺の数]から、全体のループ「while (update && !negative) {}」を、Wikipedia のコードのように頂点数の回数「for i from 1 to size(vertices) - 1:」のようにするならば、更新数は配列ではなく、int 型などにして「count >= n * edges.length」にしても良いだろう。ただし、計算量は増える。

 最短距離の更新の条件に「if (distance[e.source] != Integer.MAX_VALUE && ~」という条件が含まれるが、これは Integer.MAX_VALUE に加算をすると、オーバーフローを起こし、マイナスの値になってしまうためだ。これはダイクストラ法と違って、順次始点から近い頂点から計算されるわけでなく、辺情報の配列を無秩序に計算するためなので、初期化のデフォルト値を、コストを加算しても十分大きな値((int)1e9, 1 << 30, Integer.MAX_VALUE / 2 など)にすれば、この条件文を消すことができる。


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

●ベルマン-フォード法で選択した辺を返す版
・・・(略)・・・
import java.util.Collections;
import java.util.LinkedList;

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

int ans = bellmanford(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));
}
}

//ベルマン-フォード法[単一始点最短経路(Single Source Shortest Path)]
//選択した辺を返す。
int bellmanford(int n, Edge[] edges, int s, int g, List<Edge> paths) {
int[] distance = new int[n]; //始点からの最短距離
int[] parent = new int[n]; //接続元ノード
int[] count = new int[n]; //更新カウント(負の閉路チェック用)

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

boolean negative = false; //負の閉路フラグ
boolean update = true; //更新フラグ

while (update && !negative) {
update = false;
for (Edge e : edges) {
//接続元+接続先までの距離
if (distance[e.source] != Integer.MAX_VALUE && distance[e.source] + e.cost < distance[e.target]) {
distance[e.target] = distance[e.source] + e.cost; //現在記録されている距離より小さければ更新
parent[e.target] = e.source; //接続元を記録
update = true;

if (++count[e.target] >= n) { //負の閉路チェック
negative = true;
break;
}
}
}
}

if (negative) {
return Integer.MIN_VALUE; //負の閉路があったときは、-INF(Integer.MIN_VALUE)を返す
}

//選択した辺(逆から辿る[到達点→始点])
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(Integer.MAX_VALUE)になる
}
・・・(略)・・・
}

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


 ベルマン-フォード法負の閉路を持っている可能性がある場合や、迷路というより、網の目のようなネットワーク経路などに向いているかも知れない。このサンプルでは更新がなかったとき、探索を打ち切っているので、計算量は「辺の数×頂点数」よりもずっと小さい回数で済む。デバッグ出力して確かめてみると、負の閉路がない場合は「辺の数+数回の更新」で終わることが多いので(データの順序にもよる。始点に近い順に並んでいると計算が速い)、ダイクストラ法とそれほど変わらない気がする。


(関連記事)
【Java】ダイクストラ法[単一始点最短経路] (Dijkstra's 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)
【Java】素集合データ構造[互いに素な集合] (Union Find Tree, Disjoint Set Forest)


category: Java

thread: プログラミング

janre: コンピュータ

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


プロフィール

Twitter

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop