アルゴリズムとデータ構造

(1)

アルゴリズムとデータ構造

2012 年 7 月 23 日

酒居敬一 ([email protected])

http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2012/index.html

(2)

バックトラック法

（３５２ページ）

•   組織的かつ論理的なしらみつぶし解法

•   単純に全ての場合を試すのではなく、

問題の性質を考慮して無駄な計算を省く

•   例：ｎ女王問題

–   盤面に女王を置ける場合の数はとおり

–   しかし、ひとつの列に女王はひとつしか置けない

•   とおりまで減らすことができる

–   さらに、ひとつの行に女王はひとつしか置けない

n2

C

n

(3)

… …

…

3

１２３４５ｎ

１２３４ｎ１２３４ｎ

１２３ｎ

…

１行目の女王の位置

２行目の女王の位置

３行目の女王の位置

×

× ×

×

深さ優先探索により、

すべての場合を調べるのではなく、

解の探索の途中で可能性の無い枝を刈り払う → 枝刈り

図６.１.３ｎ女王問題の解の探索（３５４ページ）

(4)

女王が盤面の

（ｘ１, ｙ１）に居るとき、

ａｒｒａｙ［ｘ１］＝ｙ１ｘ１

ｙ２ｘ２

ｙ１Ｊａｖａ

（０, ０）ｘ３

ｙ３

（ｘ２, ｙ２）に女王は置けない

↓

ｙ１‐ｘ１＝ｙ２‐ｘ２が成り立たないこと

ｍｉｎｏｒ［ｙ１‐ｘ１］＝ｆａｌｓｅ

（ｘ３, ｙ３）に女王は置けない

↓

ｘ１＋ｙ１＝ｘ３＋ｙ３が成り立たないこと

ｍａｊｏｒ［ｘ１＋ｙ１］＝ｆａｌｓｅ各列には１個しか置けないので、ｈｏｒｉｚｏｎｔａｌ［ｘ１］＝ｆａｌｓｅ

(5)

public class BackTrack {

private final boolean[] horizontal;

private final boolean[] major;

private final boolean[] minor;

private final int[] array;

private final StringBuffer hr = new StringBuffer();

private final StringBuffer queen = new StringBuffer();

public BackTrack(int n){

horizontal = new boolean[n];

major = new boolean[2*n - 1];

minor = new boolean[2*n - 1];

array = new int[n];

Arrays.fill(horizontal, true);

Arrays.fill(major, true);

Arrays.fill(minor, true);

for(int i = 0; i < n; i++) hr.append("+---");

hr.append('+');

for(int j = 0; j < n - 1; j++) queen.append("¦ ");

queen.append("¦ X ");

for(int j = 0; j < n - 1; j++) queen.append("¦ ");

queen.append('¦');

} }

5

左下がりの対角線上に置けるかどうか

1行に1個しか置けないようにしたデータ構造その列に置けるかどうか

右下がりの対角線上に置けるかどうか

盤面そのものを表す

特別なデータ構造はない！

(6)

private void backtrack(int level){

if(level >= horizontal.length){

for(int x: array){

System.out.println(hr);

System.out.append(queen, 4*x, 4*x + 4*array.length + 1);

System.out.println();

}

System.out.println(hr);

} else {

int row̲a = level;

int row̲i = level + horizontal.length - 1;

for(int i = 0; i < horizontal.length; i++){

if(horizontal[i] && major[row̲a + i] && minor[row̲i - i]){

horizontal[i] = false;

major[row̲a + i] = false;

minor[row̲i - i] = false;

array[row̲a] = i;

backtrack(level + 1);

horizontal[i] = true;

major[row̲a + i] = true;

minor[row̲i - i] = true;

} } } }

ｑｕｅｅｎを置かなかったことにする

（後戻りするのでバックトラック法）

解の出力

横４文字・縦２文字で升目１つ

ｑｕｅｅｎを置いてみる

新しいｑｕｅｅｎの位置

すべての場合の盤面を

生成し検査するのでもない

（生成後検査法ではない）

枝刈り

(7)

+---+---+---+---+---+---+---+---+

¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ X ¦ +---+---+---+---+---+---+---+---+

¦ ¦ ¦ ¦ X ¦ ¦ ¦ ¦ ¦ +---+---+---+---+---+---+---+---+

¦ X ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ +---+---+---+---+---+---+---+---+

¦ ¦ ¦ X ¦ ¦ ¦ ¦ ¦ ¦ +---+---+---+---+---+---+---+---+

¦ ¦ ¦ ¦ ¦ ¦ X ¦ ¦ ¦ +---+---+---+---+---+---+---+---+

¦ ¦ X ¦ ¦ ¦ ¦ ¦ ¦ ¦ +---+---+---+---+---+---+---+---+

¦ ¦ ¦ ¦ ¦ ¦ ¦ X ¦ ¦ +---+---+---+---+---+---+---+---+

¦ ¦ ¦ ¦ ¦ X ¦ ¦ ¦ ¦ +---+---+---+---+---+---+---+---+

+---+---+---+---+---+---+---+---+

¦ ¦ ¦ ¦ ¦ ¦ X ¦ ¦ ¦ +---+---+---+---+---+---+---+---+

¦ ¦ ¦ X ¦ ¦ ¦ ¦ ¦ ¦ +---+---+---+---+---+---+---+---+

¦ X ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ +---+---+---+---+---+---+---+---+

¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ X ¦ +---+---+---+---+---+---+---+---+

¦ ¦ ¦ ¦ ¦ X ¦ ¦ ¦ ¦ +---+---+---+---+---+---+---+---+

¦ ¦ X ¦ ¦ ¦ ¦ ¦ ¦ ¦ +---+---+---+---+---+---+---+---+

¦ ¦ ¦ ¦ X ¦ ¦ ¦ ¦ ¦ +---+---+---+---+---+---+---+---+

¦ ¦ ¦ ¦ ¦ ¦ ¦ X ¦ ¦ +---+---+---+---+---+---+---+---+

public static void main(String[] args) { for(String a: args){

int n;

try {

n = Integer.parseInt(a);

}catch(IllegalArgumentException e){

continue;

}

new BackTrack(n).backtrack(0);

} }

7

ｎ＝８の例

８-ｑｕｅｅｎ問題の解の一部

(8)

幅優先探索

（３６５ページ）

•   深さ優先探索は有用である

–   閉路のあるグラフでも深さ優先探索はできる

•   グラフがメモリ上に存在しないときは深さ優先探索が使えない

–   頂点を辿ったという印を付けられない

•   ８パズルのように探索のためのグラフを

動的生成するときは、幅優先探索する

(9)

9

1 7 8

6 5 4

3

2 1

7 8

6 5 4

3

2 1

7 8

6 5 4

3

2 1

7 8

6 5 4

3 2

1

7 8 6 5 4

3 2

1

7 8 6 5 4

3 2

1 7

8 6 5 4

3 2

1 7

8 6 5 4

3 2

1 7

8 6 5 4

3 2

1 7

8 6

5 4

3 2

1 7

8 6

5 4

3 2

1 7

8 6 5 4

3 2

図６.２.２と図６.２.３８パズルのグラフの一部

• １２手で一巡する閉路が存在する

• 各状態から作れる状態の数は２から４

• 全ての状態をメモリに置くには多い

• この場合の「多い」とはメモリ容量に対して

(10)

Ｓ^１

Ｓ２

Ｓ３

初期状態

• 初期状態から生成できる新しい状態Ｓ１を求める

• 次にＳ１から新しい状態Ｓ２を求める

• ただし余分の状態は取り除く

• 初期状態へ戻るものも取り除く

• さらにＳ２からＳ３状態を… と順に生成を続ける

• 解となる状態が生成できたら終了

• このときＳｋ状態を生成するためにＳｋ-１とＳｋ-２状態が必要

(11)

public class PuzzleBoard { private final int[] board;

private int hole = -1;

private static int size;

private final PuzzleBoard parent;

public PuzzleBoard(int[] new̲board){

if(size == 0){

size = (int)Math.sqrt((double)new̲board.length);

} // 例外処理は割愛 this.board = new̲board;

for(int i = 0; i < new̲board.length; i++){

if(new̲board[i] == 0){

hole = i;

}

} // 例外処理は割愛 this.parent = null;

}

private PuzzleBoard(PuzzleBoard current, int new̲hole){

this.board = current.board.clone();

this.board[current.hole] = this.board[new̲hole];

this.board[new̲hole] = 0;

this.hole = new̲hole;

this.parent = current;

} }

11

初期状態と最終状態の生成用

パズルの盤の定義（その１）

途中の状態の生成用

(12)

public boolean equals(Object obj) {

PuzzleBoard in = (PuzzleBoard)obj;

int[] array = in.board;

for(int i = 0; i < this.board.length; i++){

if(array[i] != this.board[i]){

return false;

}

} // 例外処理は割愛 return true;

}

public int hashCode() {

return board[0] * board[1] + this.hole; // 実行時間に大きく影響する }

public PuzzleBoard getParent() { return parent;

}

public String toString(){

StringBuffer sb = new StringBuffer();

int k = 0;

for(int i = 0; i < size; i++){

for(int j = 0; j < size; j++){

sb.append(this.board[k++]).append(' ');

}

sb.append('\n');

}

sb.append('\n');

12

結果の表示用

ハッシュテーブルを使うために equals()とhashCode()を実装

パズルの盤の定義（その２）

(13)

public static void generate(Collection<PuzzleBoard> from, Collection<PuzzleBoard> to, Collection<PuzzleBoard> other){

for(PuzzleBoard b: from){

int i = b.hole - size;

if(0 <= i){

PuzzleBoard new̲board = new PuzzleBoard(b, i);

if(!from.contains(new̲board)&&!to.contains(new̲board)&&!other.contains(new̲board)) to.add(new̲board);

}

i = b.hole + size;

if(i < b.board.length){

PuzzleBoard new̲board = new PuzzleBoard(b, i);

}

i = b.hole % size;

if(i != 0){

PuzzleBoard new̲board = new PuzzleBoard(b, b.hole - 1);

}

if(i != (size - 1)){

PuzzleBoard new̲board = new PuzzleBoard(b, b.hole + 1);

} } }

スペースを上に動かす

パズルの盤の定義（その３）

スペースを下に動かす

スペースを左に動かす

スペースを右に動かす

(14)

public class Puzzle {

private static int[] initial̲state = {5,3,6, 8,7,1, 2,0,4};

private static int[] final̲state = {0,1,2, 3,4,5, 6,7,8};

private static PuzzleBoard initial̲board = new PuzzleBoard(initial̲state);

private static PuzzleBoard final̲board = new PuzzleBoard(final̲state);

public static void main(String[] args) {

HashSet<PuzzleBoard> set1 = new HashSet<PuzzleBoard>();

HashSet<PuzzleBoard>[] aspect = new HashSet[]{set1, set2, set3}; // from, to, other aspect[1].add(initial̲board); // 初期状態

int step;

for(step = 1; !aspect[1].contains(final̲board); step++){ // 最終状態に到達するまで探索 HashSet<PuzzleBoard> tmp = aspect[0];

aspect[0] = aspect[1]; aspect[1] = aspect[2]; aspect[2] = tmp;

aspect[1].clear();

PuzzleBoard.generate(aspect[0], aspect[1], aspect[2]);

System.out.print(step + ": ");

System.out.println(aspect[1].size());

}

aspect[2].clear(); // ここから結果の表示

aspect[2].add(final̲board); // 最終状態だけからなるコレクション aspect[1].retainAll(aspect[2]); // 最終局面で最終状態だけ残す。

for(PuzzleBoard board: aspect[1]){

for(PuzzleBoard current = board; current != null; current = current.getParent()){

System.out.println("step: " + --step);

(15)

15

step: 6 5 3 6 2 1 0 7 8 4 step: 5 5 3 6 2 0 1 7 8 4 step: 4 5 3 6 2 8 1 7 0 4 step: 3 5 3 6 2 8 1 0 7 4 step: 2 5 3 6 0 8 1 2 7 4 step: 1 5 3 6 8 0 1 2 7 4 step: 0 5 3 6 8 7 1 2 0 4 1: 3

2: 5 3: 10 4: 14 5: 28 6: 42 7: 80 8: 108 9: 202 10: 278 11: 524 12: 726 13: 1348 14: 1804 15: 3283 16: 4193 17: 7322 18: 8596 19: 13930 20: 14713 21: 21721 22: 19827 23: 25132 24: 18197 25: 18978 26: 9929 27: 7359

step: 20 1 2 5 6 3 4 7 0 8 step: 19 1 2 5 6 3 4 7 8 0 step: 18 1 2 5 6 3 0 7 8 4 step: 17 1 2 5 6 0 3 7 8 4 step: 16 1 2 5 0 6 3 7 8 4 step: 15 0 2 5 1 6 3 7 8 4 step: 14 2 0 5 1 6 3 7 8 4 step: 27

0 1 2 3 4 5 6 7 8 step: 26 1 0 2 3 4 5 6 7 8 step: 25 1 2 0 3 4 5 6 7 8 step: 24 1 2 5 3 4 0 6 7 8 step: 23 1 2 5 3 0 4 6 7 8 step: 22 1 2 5 0 3 4 6 7 8 step: 21 1 2 5 6 3 4 0 7 8

step: 13 2 5 0 1 6 3 7 8 4 step: 12 2 5 3 1 6 0 7 8 4 step: 11 2 5 3 1 0 6 7 8 4 step: 10 2 5 3 0 1 6 7 8 4 step: 9 0 5 3 2 1 6 7 8 4 step: 8 5 0 3 2 1 6 7 8 4 step: 7 5 3 0 2 1 6 7 8 4

探索は１０秒くらい

初期状態

最終状態３

１７２４８

６５

１５４６７８３

２

(16)

先手番

後手番

先手番

後手番

図６.３.１ゲームの木（の部分木だと考えてください）

ミニマックス法では、バックトラック法により木の葉から評価を決めていく。

ゲームの木の探索

（３７６ページ）

+1

-1

+1 -1

+1

+1 +1

+1

+1 -1

-1 -1

(17)

17

0

+1 -1

+1

+1 0 -1 -1

先手番

後手番

先

手勝

後手勝引

分

• ゲーム終了の状態に＋１・０・‐１を与える

• ゲームの途中では自分に有利なほうの枝を辿る

• ゲームの木の途中の頂点の値を決定できる

• 手番が先手・後手に応じて最大・最小を選択

• 全手読みができれば

• 先手必勝・引き分け・後手必勝がわかる

• 全手読みは時間的にも空間的にも困難

• 全手読みが不可能な場合

• その局面での勝ちやすさ（負けやすさ）を求める

• 先手有利を正の数、後手有利を負の数…

• その数値を求める関数を評価関数という

• 先読みする深さを限定して評価する

• 確率的要素が入るゲームは、ここでは扱わない

• 完全情報ゲームのみを対象とする

(18)

18

S

A B

G F

E H

2 4 1 3 7 1 2 3

先手番

後手番

先手番

後手番４以上

４以下なら打ち切り

４以下

４以上なら打ち切り

４７以上３

調べるだけ無駄

４

３以下

• 数字は大きいほど先手に有利、つまり、小さいほど後手に有利

• 

先手はより大きな数値を持つ方向を選ぶ

• 

後手はより小さな数値を持つ方向を選ぶ

• 評価関数の値について

• 深さ制限つきのミニマックス法

• 一定の深さまで読んで、最大値もしくは最小値を選ぶ

• α-β法

３

調べるだけ無駄

アルゴリズムとデータ構造