様々な問題を解決するために解を探索する場合には、幾つかの探索手法が有効である。本章では、スタックを用いた深さ優先探索とキューを用いた幅優先探索について説明する。
５．１ 水差し問題（water jug problem）
○課題
４リットルと３リットルの水差しがある。この２つの水差しを使って正確に
２リットルを計るにはどうすればよいか。
|
空 空 2 l 空
4 l 3 l 4 l 3 l
●補足
４リットル・３リットルの水差しの水の量がそれぞれｘ・ｙである時、(x, y) と表現すれば、２つの水差しで可能な操作は以下の８通りである。
①水差しを満杯にする
既に満杯になっている場合は除くため、
x < 4 ならば、(x, y) を (4, y) とする（FILL A）
y < 3 ならば、(x, y) を (x, 3) とする（FILL B）
②水差しを空にする
水が入っていない場合を除くため、
x > 0 ならば、(x, y) を (0, y) とする（EMPTY A）
y > 0 ならば、(x, y) を (x, 0) とする（EMPTY B）
③他方が満杯になるまで、水を注ぐ
他方が既に満杯の場合および満杯にできない場合を除くため、
x < 4 かつ x+y >= 4 ならば、(x, y) を (4, x+y-4) とする（FILL A<-B）
y < 3 かつ x+y >= 3 ならば、(x, y) を (x+y-3, 3) とする（FILL B<-A）
④空になるまで、他方に水を注ぐ
既に空の場合および他方が溢れるか満杯になる場合を除くため、
x > 0 かつ x+y < 3 ならば、(x, y) を (0, x+y) とする（EMPTY A->B）
y > 0 かつ x+y < 4 ならば、(x, y) を (x+y, 0) とする（EMPTY B->A）
（注）満杯になる場合を除くのは③と重ならないようにするためである。
○外部仕様
２つの水差しの容量と計りたい容量を指定して、計りたい容量になるまでの操作を標準出力に出力する。課題を解く際は、４、３、２を指定すればよい。
○概要設計
１．引数により、２つの水差しの容量と計りたい容量を指定する
２．計りたい容量になるまでの操作系列を求める
３．操作系列を標準出力に出力する
○詳細設計
●アクセス関数
ａ．操作系列の計算
O=SOLVE(A, B, C)：容量 A と B の２つの水差しで C を求める操作列 O を求める
ｂ．操作系列の出力
PRINT(O)：操作系列 O を標準出力に出力する
●データ構造
"FILL A", "EMPTY A" などのように操作の内容を示す文字列を操作系列として保持する。
typedef struct {
char *operation[OPERATION_SIZE];
int size;
} OperationRec, *Operation;
○コーディング
【PRINT操作】
void PRINT(Operation O)
{
int i;
for(i=0; i<O->size; ++i)
printf("%s\n", O->operation[i]);
printf("\n");
}
問 5.1.1 水差しの数が２個以上、一般にｎ個の場合の問題に対応するには、どのようなアクセス関数を準備すればよいか考えよ。
問 5.1.2 伝道師と人食い土人（M&C）の問題は、以下のように定義される。
川の左岸に伝道師と人食い土人が３人ずつおり、２人乗りのボートが一艘ある。人食い土人は伝道師より人数が多くなると伝道師を食べてしまう。全員が安全に右岸に渡るためには、どのようにすればよいか。
M&C 問題を解くためのアクセス関数を考えよ。
問 5.1.3 狼と山羊とキャベツと男の問題は、以下のように定義される。
川の左岸に男がおり、他に１つしか乗せられないボートで、狼と山羊とキャベツを右岸に運びたい。男がいないと、狼は山羊を食べ、山羊はキャベツを食べてしまう。安全に右岸に渡るためには、どのようにすればよいか。
この問題を解くためのアクセス関数を考えよ。
５．２ 問題解決と探索
問題解決においては、状態空間表現をはじめとして幾つかの問題表現方法がある。状態空間表現（state space representation）では、与えられた問題を解きはじめる初期状態（initial state）、問題が解ける状態を示す目標状態（goal state）、状態を目標に近づけるための操作であるオペレータ（operator）によって定義する。すなわち、
（Ｓ，Ｏ，Ｇ）：Ｓは初期状態、Ｇは目標状態、Ｏはオペレータ
の三つ組みによって記述できる。下図は、初期状態にオペレータを適用して目標状態を探索する様子を探索木によって表現したものである。節点が各状態であり、枝がオペレータに対応する。なお、ある節点から子節点を求めることを節点の展開という。
○ 初期状態
○ ○
○ ○ ○ ○
○ ○ ○ ● ○ ○ ● ○
目標状態 目標状態
探索木を探索する際の方法には、深さ優先探索（縦型探索）、幅優先探索（横型探索）などがある。深さ優先探索は、ある節点（状態）を調べた後、その子節点を先に調べ、幅優先探索は、同じレベルの節点を先に調べる。（下図参照）
深さ優先探索 幅優先探索
① ①
② ⑤ ② ③
③ ④ ⑥ ● ④ ⑤ ⑥ ●
例題5.2.1 ４リットル・３リットルの水差しで２リットルを計るという水差し問題を深さ優先探索および幅優先探索で調べるとどのような探索順になるかを示せ。
７０ｍｍ
(0, 0)
○ 初期状態
(4, 0) (0, 3)
○ ○
(4, 3) (0, 0) (1, 3) (4, 3) (0, 0) (3, 0)
○ ○ ○ ○ ○ ○
(0,3)(4,0) (4,3)(0,3)(1,0)(4,0) (4, 0) (3, 3) (0, 3)
○ ○ ○ ○ ○ ○ ○ ○ ○
(4,3) (0,0) (3,0) (4,0)(1,3)(0,0)(0,1) (4,3) (0,3) (3,0) (4,2)
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ●
目標状態
(4,0) (3,3) (0,0) (0,3) (4,1) (0,3) (0,0) (1,0)
○ ○ ○ ○ ○ ○ ○ ○
(4,3) (0,3) (3,0) (4,2)
○ ○ ○ ● 目標状態
上図が水差し問題の探索木である。一度調べた状態はそれ以上調べないとすれば、
深さ優先探索では
(0,0)(4,0)(4,3)(0,3)(4,3)＊(0,0)＊(3,0)(4,0)＊(3,3)(4,3)＊(0,3)＊(3,0)＊(4,2)
と探索し、解に至る系列は (0,0)(4,0)(4,3)(0,3)(3,0)(3,3)(4,2) となる。ただし、＊は一度調べた状態であることを示す。深さ優先探索では必ずしも解に至る最短経路を求めることができるとは限らない。
幅優先探索では
(0,0)(4,0)(0,3)(4,3)(0,0)＊(1,3)(4,3)＊(0,0)＊(3,0)(0,3)＊(4,0)＊(4,3)＊(0,3)＊
(1,0)(4,0)＊(4,0)＊(3,3)(0,3)＊(4,0)＊(1,3)＊(0,0)＊(0,1)(4,3)＊(0,3)＊(3,0)＊
(4,2)
と探索し、解に至る系列は (0,0)(0,3)(3,0)(3,3)(4,2) となる。幅優先探索では必ず解に至る最短経路を求めることができる。
○概要設計
問題解決においては、これから調べようとする状態を保持するリスト（オープンリスト）および既に調べた状態を保持するリスト（クローズドリスト）を利用して以下のような順序で探索を行う。
(1) オープンリストに初期状態を設定する
(2) クローズドリストを空にする
(3) オープンリストが空ならば、解はないので、終了する
(4) オープンリストから次（通常は先頭）の状態を取り出し、状態ｓとする
(5) 状態ｓが目標状態ならば、解が見つかったので、終了する
(6) 状態ｓがクローズドリストにあれば、(3) へ
そうでなければ、状態ｓをクローズドリストに追加する
(7) 状態ｓを展開して子の状態を求める
(8) 子の状態をオープンリストに追加する
(9) (3) へ
○詳細設計
●アクセス関数
ａ．探索の実行
goal=SEARCH(initial)：初期状態 initial から探索を行い、目標状態 goal を返す
ｂ．目標状態の判定
int GOAL(state)：状態 state が目標状態かどうかを判定する
ｃ．状態の初期化
INIT_STATE(initial, open, closed)：初期状態 initial が設定されたオープンリスト open と空のクローズドリスト closed を返す
ｄ．次の状態の取り出し
state=NEXT_STATE(open)：オープンリスト open から次の状態 state を取り出す
ｅ．オープンリストへの子の状態の追加
EXPAND_STATE(open, state)：状態 state の子の状態を求め、オープンリスト open に追加する
ｆ．クローズドリストへの状態の追加
SET_STATE(state, closed)：状態 state をクローズドリスト closed に追加する
ｇ．クローズドリストにおける状態の判定
int MEMBER_STATE(state, closed)：状態 state がクローズドリスト closed にあれば 1、なければ 0 を返す
●データ構造
水差し問題における状態のフィールドとして、各水差しの水の量 x と y、その状態になるまでの操作系列を保持する o を定義する。
typedef struct {
int x, y; /* ２つの水差しの水の量 */
OperationRec o; /* 操作系列 */
} StateRec, *State;
○コーディング
SEARCH 以外のアクセス関数は、各探索法の節で説明する。
【SEARCH操作】
State SEARCH(State initial)
{
OpenList open; ClosedList closed;
State state;
INIT_STATE(initial, &open, &closed);
while((state=NEXT_STATE(open))!=NULL) { /* 次の状態がある間 */
if(GOAL(state)) /* 目標状態 */
return(state);
else if(!MEMBER_STATE(state, closed)) { /* 未調査の時 */
SET_STATE(state, closed);
EXPAND_STATE(open, state); /* 状態の展開 */
}
}
}
（注）OpenList と ClosedList というデータ型は、オープンリストとクローズドリストの実現方法によって変化する。
例題5.2.2 ４リットル・３リットルの水差しで２リットルを計るという水差し問題をオープンリストとクローズドリストを用いて解け。子の状態をオープンリストに追加する際、先頭に追加することにする。このようにすれば、深さ優先探索となる。
オープンリスト |
クローズドリスト |
状態ｓ |
((0,0))((4,0)(0,3))((4,3)(0,0)(1,3)(0,3))((0,3)(4,0)(0,0)(1,3)(0,3))((4,3)(0,0)(3,0)(4,0)(0,0)(1,3)(0,3))((0,0)(3,0)(4,0)(0,0)(1,3)(0,3))((3,0)(4,0)(0,0)(1,3)(0,3))((4,0)(3,3)(0,0)(0,3)(4,0)(0,0)(1,3) (0,3))((3,3)(0,0)(0,3)(4,0)(0,0)(1,3)(0,3))((4,3)(0,3)(3,0)(4,2)(0,0)(0,3)(4,0) (0,0)(1,3)(0,3))((0,3)(3,0)(4,2)(0,0)(0,3)(4,0)(0,0) (1,3)(0,3))((3,0)(4,2)(0,0)(0,3)(4,0)(0,0)(1,3) (0,3))((4,2)(0,0)(0,3)(4,0)(0,0)(1,3)(0,3))目標状態
|
()((0,0))((4,0)(0,0))((4,3)(4,0)(0,0))((0,3)(4,3)(4,0)(0,0))((0,3)(4,3)(4,0)(0,0))((0,3)(4,3)(4,0)(0,0))((3,0)(0,3)(4,3)(4,0)(0,0))
((3,0)(0,3)(4,3)(4,0)(0,0))((3,3)(3,0)(0,3)(4,3)(4,0) (0,0))((3,3)(3,0)(0,3)(4,3)(4,0) (0,0))((3,3)(3,0)(0,3)(4,3)(4,0) (0,0))((3,3)(3,0)(0,3)(4,3)(4,0) (0,0))
|
(0,0)(4,0)(4,3)(0,3)(4,3)(0,0)(3,0)(4,0)
(3,0)(4,3)
(0,3)
(3,0)
(4,2)
|
問 5.2.1 オープンリストとクローズドリストを用いて、子の状態をオープンリストの最後に追加することにより、例題5.2.2 を幅優先探索で解け。
問 5.2.2 ４リットル・３リットルの水差しで１リットルを計るという水差し問題を深さ優先探索および幅優先探索で調べるとどのような探索順になるかを示せ。
問 5.2.3 伝道師と人食い土人（M&C）問題について、深さ優先探索および幅優先探索で調べるとどのような探索順になるかを示せ。
問 5.2.4 狼と山羊とキャベツと男の問題について、深さ優先探索および幅優先探索で調べるとどのような探索順になるかを示せ。
５．３ スタックの実現
配列によりスタックを実現することを考える。スタックは、常に最も上（スタックトップと呼ぶ）のデータを対象として処理を行う。したがって、スタックトップの位置を保持し、データを入れればスタックトップを増加させ、データを取り出せば減少させればよい。ただし、実際にはスタックトップではなく、次にデータを入れる場所を top とした。
push 1 pop
【push操作】 【pop操作】
●アクセス関数
ａ．スタックの生成
S=CREATE(N)：大きさ N のスタック S を生成する
ｂ．スタックが空かどうかを判定
int EMPTY(S)：スタック S が空ならば 1、そうでなければ 0 を返す
ｃ．スタックが一杯かどうかを判定
int FULL(S)：スタック S が一杯ならば 1、そうでなければ 0 を返す
ｄ．スタックにデータを入れる
PUSH(S, X)：スタック S にデータ X を入れる
ｅ．スタックからデータを取り出す
X=POP(S)：スタック S からスタックトップのデータ X を取り出す
●データ構造
スタックは、スタックトップを示す top、スタックの大きさを示す size、スタック本体 stack から構成される。ここでは、今までと異なり、静的にデータ領域を割り当てるのではなく、必要な領域を動的に割り当てることにした。
○コーディング
【CREATE操作】
StackRec に必要な領域を malloc により動的に割り当て、スタック本体に必要な領域を指定された大きさだけ calloc によりゼロクリアして割り当てる。さらに、top を 0 に、size を N に初期化する。
Stack CREATE(int N)
{
Stack S;
if((S=malloc(sizeof(StackRec)))!=NULL &&
(S->stack=calloc(N, sizeof(StateRec)))!=NULL) {
S->top=0;
S->size=N;
return(S);
}
else {
fprintf(stderr, "スタックを生成できませんでした\n");
exit(1);
}
}
【EMPTY操作】
top が 0 ならば空である。
int EMPTY(Stack S)
{
return(S->top==0);
}
【FULL操作】
top が size と一致すればそれ以上入れられない。
int FULL(Stack S)
{
return(S->top==S->size);
}
【PUSH操作】
top の指す場所にデータを入れ、top を１つ増加させる。
void PUSH(Stack S, StateRec x)
{
if(FULL(S)) {
fprintf(stderr, "スタックが溢れました\n");
exit(1);
}
S->stack[S->top++]=x;
}
【POP操作】
top を１つ減少させ、その位置のデータを返す。
StateRec POP(Stack S)
{
if(EMPTY(S)) {
fprintf(stderr, "スタックが空です\n");
exit(1);
}
return(S->stack[--S->top]);
}
問 5.3.1 スタックを静的に割り当てた場合のコーディングを考えよ。
問 5.3.2 EMPTY, FULL 操作をマクロにより定義してみよ。
５．４ スタックによる深さ優先探索（depth-first search）
○スタックと深さ優先探索
オープンリストにはスタックを、クローズドリストには集合を用いる。スタックは、追加したデータが常に先頭に入るという性質を持つので、深さ優先探索となる。
(1) スタックに初期状態を設定する（push）
(2) 集合を空にする
(3) スタックが空ならば、解はないので、終了する
(4) スタックの先頭の状態を取り出し、状態ｓとする（pop）
(5) 状態ｓが目標状態ならば、解が見つかったので、終了する
(6) 状態ｓが集合にあれば、(3) へ
そうでなければ、状態ｓを集合に追加する
(7) 状態ｓを展開して子の状態を求める
(8) 子の状態をスタックに追加する（push）
(9) (3) へ
例題5.4.1 ４リットル・３リットルの水差しで２リットルを計るという水差し問題をスタックを用いて解いてみよ。
|
|
|
|
|
|
|
|
(0,3)(4,0)(0,0)(1,3)(0,3)
|
|
|
(4,3)＊(0,0)(3,0)(4,0)(0,0)(1,3)(0,3)
|
|
|
|
|
(0,0)＊(3,0)(4,0)(0,0)(1,3)(0,3)
|
|
|
(3,0)(4,0)(0,0)(1,3)(0,3)
|
|
|
(4,0)＊(3,3)(0,0)(0,3)(4,0)(0,0)(1,3)(0,3)
|
|
|
(3,3)(0,0)(0,3)(4,0)(0,0)(1,3)(0,3)
|
|
|
(4,3)＊(0,3)(3,0)(4,2)(0,0)(0,3)(4,0)(0,0)(1,3)(0,3)
|
|
|
|
|
(0,3)＊(3,0)(4,2)(0,0)(0,3)(4,0)(0,0)(1,3)(0,3)
|
|
|
(3,0)＊(4,2)(0,0)(0,3)(4,0)(0,0)(1,3)(0,3)
|
|
|
(4,2)(0,0)(0,3)(4,0)(0,0)(1,3)(0,3)
|
|
|
○集合操作
クローズドリストは集合で実現する。集合操作については既に説明したが、動的に割り当てる場合に例をあげておく。
●データ構造
typedef struct {
char *set;
int size;
} SetRec, *Set;
●コーディング
【MAKE操作】
SetRec に必要な領域を malloc により動的に割り当て、集合本体 set に必要な領域を指定された大きさだけ calloc によりゼロクリアして割り当てる。さらに、size を N に初期化する。
Set MAKE(int N)
{
Set S;
if((S=malloc(sizeof(SetRec)))!=NULL &&
(S->set=calloc(N, sizeof(S->set[0])))!=NULL) {
S->size=N;
return(S);
}
else {
fprintf(stderr, "集合を生成できませんでした\n");
exit(1);
}
}
【SET操作】
void SET(int X, Set S)
{
S->set[X]=1;
}
【MEMBER操作】
int MEMBER(int X, Set S)
{
return(S->set[X]);
}
○コーディング
【SOLVE操作】
水差しの容量と計量を大域変数 A, B, C に代入し、初期状態を (0,0) として SEARCH 操作を呼び出す。
Operation SOLVE(int a, int b, int c)
{
StateRec i_rec;
State state;
A=a; B=b; C=c;
i_rec.x=0; i_rec.y=0;
i_rec.o.size=0;
state=SEARCH(&i_rec);
return(state!=NULL? &state->o : NULL);
}
【SEARCH操作】
OpenList を Stack、ClosedList を Set にすればよい。
State SEARCH(State initial)
{
Stack open; Set closed;
State state;
INIT_STATE(initial, &open, &closed);
while((state=NEXT_STATE(open))!=NULL) {
printf("(%d, %d)\n", state->x, state->y);
if(GOAL(state))
return(state);
else if(!MEMBER_STATE(state, closed)) {
SET_STATE(state, closed);
EXPAND_STATE(open, state);
}
}
}
【GOAL操作】
２つの水差しのどちらか一方でも指定した水量Ｃになればよい。
【INIT_STATE操作】
オープンリスト用のスタック open とクローズドリスト用の集合 closed を生成し、オープンリストに初期状態 initial を設定する。
void INIT_STATE(State initial, Stack *open, Set *closed)
{
*open=CREATE(STACK_SIZE);
*closed=MAKE(SET_SIZE);
ADD_STATE(*open, initial, "INITIALIZE", 0, 0);
}
【NEXT_STATE操作】
スタックの先頭を POP 操作により取り出す。データが破壊されないように、静的に割り当てた s_rec にコピーを作り、そのアドレスを返している。
【EXPAND_STATE操作】
オペレータを適用して得られた子の状態をスタックに追加し、操作系列を更新する。実際の処理は ADD_STATE より行う。
void EXPAND_STATE(Stack S, State state)
{
int x=state->x, y=state->y;
if(y>0 && (x+y)<A) ADD_STATE(S, state, "EMPTY B->A", x+y, 0);
if(x>0 && (x+y)<B) ADD_STATE(S, state, "EMPTY A->B", 0, x+y);
if(y<B && (x+y)>=B) ADD_STATE(S, state, "FILL B<-A", x+y-B, B);
if(x<A && (x+y)>=A) ADD_STATE(S, state, "FILL A<-B", A, x+y-A);
if(y>0) ADD_STATE(S, state, "EMPTY B", x, 0);
if(x>0) ADD_STATE(S, state, "EMPTY A", 0, y);
if(y<B) ADD_STATE(S, state, "FILL B", x, B);
if(x<A) ADD_STATE(S, state, "FILL A", A, y);
}
【SET_STATE操作】
ここで定義巣した集合操作では整数値しか処理できないので、状態 (x,y) を整数値に変換する必要がある。状態 (x,y) を 10*x+y という値に変換している。
void SET_STATE(State state, Set S)
{
SET(state->x*10+state->y, S);
}
【MEMBER_STATE操作】
状態 (x,y) を変換した 10*x+y が集合にあるかどうかを判定する。
int MEMBER_STATE(State state, Set S)
{
return(MEMBER(state->x*10+state->y, S));
}
【ADD_STATE関数】
現在の状態 state に操作 o を適用して状態 (x,y) に遷移した後の新しい状態をスタックに入れる。
void ADD_STATE(Stack S, State state, char *o, int x, int y)
{
StateRec s_rec;
s_rec.x=x;
s_rec.y=y;
s_rec.o=state->o;
s_rec.o.operation[s_rec.o.size++]=o;
PUSH(S, s_rec);
}
【main関数】
int A, B, C;
void main(int argc, char **argv)
{
Operation O;
if(argc!=4) {
fprintf(stderr, "使用法: %s 容量A 容量B 計量C\n", argv[0]);
exit(1);
}
O=SOLVE(atoi(argv[1]), atoi(argv[2]), atoi(argv[3]));
if(O!=NULL)
PRINT(O);
else printf("解が見つかりません\n");
}
問 5.4.1 オペレータの適用順序は "FILL A", "FILL B", ... という順になっているが、この順を逆順に変更するとどのような操作系列が得られるか。
問 5.4.2 操作系列ではなく、初期状態から目標状態までの状態の系列を出力するためには、どのようなアクセス関数が必要であるか考えよ。
問 5.4.3 状態 (x,y) を整数に変換する際、10*x+y という変換を行っているため、集合用に 10*A+B+1 の領域が必要である。必要最小限の領域だけを準備するためには、どのような変換を行えばよいか。
５．５ キューの実現
配列によりキューを実現することを考える。キューは、最も上から取り出し、最も下へ追加する処理を行う。したがって、２つの位置 top と bot を保持し、データを追加すれば bot を増加し、データを取り出せば top を増加させればよい。
enqueue 2 dequeue
【enqueue操作】 【dequeue操作】
●アクセス関数
ａ．キューの生成
Q=CREATE(N)：大きさ N のキュー Q を生成する
ｂ．キューが空かどうかを判定
int EMPTY(Q)：キュー Q が空ならば 1、そうでなければ 0 を返す
ｃ．キューが一杯かどうかを判定
int FULL(Q)：キュー Q が一杯ならば 1、そうでなければ 0 を返す
ｄ．キューにデータを入れる
ENQUEUE(Q, X)：キュー Q にデータ X を入れる
ｅ．キューからデータを取り出す
X=DEQUEUE(Q)：キュー Q からデータ X を取り出す
●データ構造
キューは、取り出し位置を示す top、入力位置を示す bot、大きさを示す size、データの数を示す n、キュー本体 queue から構成される。ここでは、今までと異なり、静的にデータ領域を割り当てるのではなく、必要な領域を動的に割り当てることにする。
○コーディング
【CREATE操作】
Queue CREATE(int N)
{
Queue Q;
if((Q=malloc(sizeof(QueueRec)))!=NULL &&
(Q->queue=calloc(N, sizeof(StateRec)))!=NULL) {
Q->top=(-1);
Q->bot=Q->n=0;
Q->size=N;
return(Q);
}
else {
fprintf(stderr, "キューを生成できませんでした\n");
exit(1);
}
}
【EMPTY操作】
int EMPTY(Queue Q)
{
return(Q->n==0);
}
【FULL操作】
int FULL(Queue Q)
{
return(Q->n==Q->size);
}
【PUSH操作】
void ENQUEUE(Queue Q, StateRec x)
{
if(FULL(Q)) {
fprintf(stderr, "キューが溢れました\n");
exit(1);
}
++Q->n;
Q->queue[Q->bot++]=x;
if(Q->bot==Q->size) Q->bot=0;
}
【DEQUEUE操作】
StateRec DEQUEUE(Queue Q)
{
if(EMPTY(Q)) {
fprintf(stderr, "キューが空です\n");
exit(1);
}
--Q->n;
if(++Q->top==Q->size) Q->top=0;
return(Q->queue[Q->top]);
}
問 5.5.1 キューを静的に割り当てた場合のコーディングを考えよ。
問 5.5.2 EMPTY, FULL 操作をマクロにより定義してみよ。
５．６ キューによる幅優先探索（breadth-first search）
○キューと幅優先探索
オープンリストにはキューを、クローズドリストには集合を用いる。キューは、データを最後に追加するという性質を持つので、幅優先探索となる。
(1) キューに初期状態を設定する（enqueue）
(2) 集合を空にする
(3) キューが空ならば、解はないので、終了する
(4) キューの先頭の状態を取り出し、状態ｓとする（dequeue）
(5) 状態ｓが目標状態ならば、解が見つかったので、終了する
(6) 状態ｓが集合にあれば、(3) へ
そうでなければ、状態ｓを集合に追加する
(7) 状態ｓを展開して子の状態を求める
(8) 子の状態をキューに追加する（dequeue）
(9) (3) へ
例題5.6.1 ４リットル・３リットルの水差しで２リットルを計るという水差し問題をキューを用いて解いてみよ。
|
|
|
|
|
|
|
|
(4,3)(0,0)(1,3)(4,3)(0,0)(3,0)
|
|
|
(0,0)＊(1,3)(4,3)(0,0)(3,0)(0,3)(4,0)
|
|
|
|
|
(1,3)(4,3)(0,0)(3,0)(0,3)(4,0)
|
|
|
(4,3)＊(0,0)(3,0)(0,3)(4,0)(4,3)(0,3)(1,0)(4,0)
|
|
|
(0,0)＊(3,0)(0,3)(4,0)(4,3)(0,3)(1,0)(4,0)
|
|
|
(3,0)(0,3)(4,0)(4,3)(0,3)(1,0)(4,0)
|
|
|
| (0,3)＊(4,0)(4,3)(0,3)(1,0)(4,0)(4,0)(3,3)(0,0)(0,3) |
|
|
|
|
(4,0)＊(4,3)＊(0,3)＊(1,0)(4,0)(4,0)(3,3)(0,0)(0,3)
|
|
|
(1,0)(4,0)(4,0)(3,3)(0,0)(0,3)
|
|
|
(4,0)＊(4,0)＊(3,3)(0,0)(0,3)(4,0)(1,3)(0,0)(0,1)
|
|
|
(3,3)(0,0)(0,3)(4,0)(1,3)(0,0)(0,1)
|
|
|
| (0,0)＊(0,3)＊(4,0)＊(1,3)＊(0,0)＊(0,1)(4,3)(0,3)(3,0)(4,2) |
|
|
|
|
(0,1)(4,3)(0,3)(3,0)(4,2)
|
|
|
(4,3)＊(0,3)＊(3,0)＊(4,2)(4,1)(0,3)(0,0)(1,0)
|
|
|
(4,2)(4,1)(0,3)(0,0)(1,0)
|
|
|
○コーディング
スタックの場合と変更になる部分を記述する。変更点は、PUSH, POP 操作の関数名がそれぞれ ENQUEUE, DEQUEUE になること、ADD_STATE におけるオペレータの記述順が逆順になること、スタック型 Stack がキュー型 Queue になることである。
【INIT_STATE操作】
void INIT_STATE(State initial, Queue *open, Set *closed)
{
*open=CREATE(STACK_SIZE);
*closed=MAKE(SET_SIZE);
ADD_STATE(*open, initial, "INITIALIZE", 0, 0);
}
【NEXT_STATE操作】
【SET_STATE操作】
void SET_STATE(State state, Set S)
{
SET(state->x*10+state->y, S);
}
【MEMBER_STATE操作】
int MEMBER_STATE(State state, Set S)
{
return(MEMBER(state->x*10+state->y, S));
}
【EXPAND_STATE操作】
void EXPAND_STATE(Queue Q, State state)
{
int x=state->x, y=state->y;
if(x<A) ADD_STATE(Q, state, "FILL A", A, y);
if(y<B) ADD_STATE(Q, state, "FILL B", x, B);
if(x>0) ADD_STATE(Q, state, "EMPTY A", 0, y);
if(y>0) ADD_STATE(Q, state, "EMPTY B", x, 0);
if(x<A && (x+y)>=A) ADD_STATE(Q, state, "FILL A<-B", A, x+y-A);
if(y<B && (x+y)>=B) ADD_STATE(Q, state, "FILL B<-A", x+y-B, B);
if(x>0 && (x+y)<B) ADD_STATE(Q, state, "EMPTY A->B", 0, x+y);
if(y>0 && (x+y)<A) ADD_STATE(Q, state, "EMPTY B->A", x+y, 0);
}
【SEARCH操作】
State SEARCH(State initial)
{
Queue open; Set closed;
State state;
INIT_STATE(initial, &open, &closed);
while((state=NEXT_STATE(open))!=NULL) {
printf("(%d, %d)\n", state->x, state->y);
if(GOAL(state))
return(state);
else if(!MEMBER_STATE(state, closed)) {
SET_STATE(state, closed);
EXPAND_STATE(open, state);
}
}
}
【ADD_STATE関数】
void ADD_STATE(Queue Q, State state, char *o, int x, int y)
{
StateRec s_rec;
s_rec.x=x;
s_rec.y=y;
s_rec.o=state->o;
s_rec.o.operation[s_rec.o.size++]=o;
ENQUEUE(Q, s_rec);
}
問 5.6.1 キューについて、問 5.4.1、問 5.4.2、問 5.4.3 を考えよ。
問 5.6.2 状態を展開して子の状態を求める際、既にクローズドリストにあるものもオープンリストに追加している。既にクローズドリストにある状態を追加しないようにせよ。