横型から縦型への変換

[晶]

今、横型探索から縦型探索に書き換えているんですが…
どう書き換えたらよいかわかりません。

すみませんが…誰か教えていただけないでしょうか??

横型のプログラムです。
ちなみに言語はC言語です。

int main( void )
{
struct Cell start_state;
struct Cell open_list;
struct Cell closed_list;
struct Cell *temp;
struct Cell *s;
int i,j;

/* リストの初期化（空リストにする）*/
open_list.prev = open_list.next = &open_list;
closed_list.prev = closed_list.next = &closed_list;
start_state.prev = start_state.next = &start_state;

/* 初期状態の設定 */
start_state.state.wolf = 0;
start_state.state.goat = 0;
start_state.state.cabbage = 0;
start_state.state.man = 0;

/* OpenList に初期状態を追加 */
push_back( &open_list, &start_state );

j=0;
/* OpenList が空になるまで、以下を繰り返し実行 */
while( open_list.next != &open_list ) {
j++;
/* OpenList の先頭から状態を一つ取り出す */
s = open_list.next;

/* 途中経過を表示 */
print_progress( s , &open_list , &closed_list , j );
printf("\n");

/* OpenList からsを削除 */
remove_state( s );

/* ClosedList の末尾に状態 s を追加 */
push_back( &closed_list,s );

/* 目標状態なら結果を出力して終了 */
if ( succeeded(s) ) {
print_result( s, &closed_list );
break;
}

/* 禁止状態なら、状態 s を破棄し次に移る */
if ( failed(s) ) {
printf("%d%d%d%d は禁止状態 \n",
s->state.man, s->state.wolf,
s->state.goat, s->state.cabbage);
continue;
}

for( i=0; i<4 ; i++) {
/* 状態 s に可能なオペレーターを適用 */
switch( i ) {
case 0:
temp = move_man( s ); /* 人を移動 */
break;
case 1:
temp = move_wolf( s ); /* 狼を移動 */
break;
case 2:
temp = move_goat( s ); /* 山羊を移動 */
break;
case 3:
temp = move_cabbage( s ); /* キャベツを移動 */
break;
}
/* OpenListの更新（横型探索）*/
if ( find( &open_list, temp ) == &open_list
&& find( &closed_list, temp ) == &closed_list )
/* OpenList、ClosedListに無ければOpenListの末尾に追加 */
push_back( &open_list, temp );
}
}
return( 0 );
}

[晶]

プログラムは横型で、これを縦型にするために書き換えたいんです。

[ookami]

私がちゃんと読めていないだけかもしれませんが、

Cell というのは晶さんが定義されたクラスで、Listか何かを継承しているのでしょうか。
見た感じ、パスがnextとprevしか無いように見えますが、
縦型か横型かというのは、ノード間が複数のパスで繋がっている場合なのではないでしょうか...？

トンチンカンなことを言っていたらすみません...

[晶]

ookamiさんへ

Cellというのは、私が定義したクラスです。
Listの処理として使っています。
使い方は以下のプログラムです。

/* OpenList、ClosedList */
struct Cell {
struct Cell *next; /* リスト中の次の状態へのポインタ */
struct Cell *prev; /* リスト中の前の状態へのポインタ */
struct Cell *path; /* 親状態を指すポインタ */
struct State state; /* 状態を表す変数 */
};

/* リスト処理 */
/* リストの先頭に追加 */
void push_front( struct Cell *l, struct Cell *n )
{
n->prev = l;
n->next = l->next;
l->next->prev = n;
l->next = n;
}

/* リストの末尾に追加 */
void push_back( struct Cell *l, struct Cell *n )
{
n->prev = l->prev;
n->next = l;
l->prev->next = n;
l->prev = n;
}

/* OpenListから状態を削除 */
void remove_state( struct Cell *n )
{
n->prev->next = n->next;
n->next->prev = n->prev;
}

/* リスト中に同じ状態があるか判定 */
struct Cell *find( struct Cell *l, struct Cell *n )
{
struct Cell *p;
p=l->next;
while ( p!=l) {
if ( p->state.man==n->state.man &&
p->state.wolf==n->state.wolf &&
p->state.goat==n->state.goat &&
p->state.cabbage==n->state.cabbage )
return ( p ); /* 見つかった状態へのポインタを返す */
p=p->next;
}
return ( l ); /* リストの先頭へのポインタを返す */
}

/* 目標状態か判定 */
int succeeded( struct Cell *s )
{
if (s->state.man==1 && s->state.wolf==1
&& s->state.goat==1 && s->state.cabbage==1)
return( 1 );
else
return( 0 );
}

[ookami]

晶さんが「横型検索」とおっしゃっているのは、find関数のことですよね？

見た感じ、Cellクラスは「双方向リスト」なので、やはり、横型検索か縦型検索か、ということにはならないのではないでしょうか。

念のため、言葉の確認を...(いや 私が勘違いしているだけかもしれませんので)
http://ja.wikipedia.org/wiki/%E5%B9%85% ... 2%E7%B4%A2
>幅優先探索
>「横型探索」とも言われる。

↑仰っている「横型検索」は、これですよね？


全体としてどんなことをしようとしていて、
データ構造はどんな感じで(たぶんイラストがあった方がよい)、
どんな問題があるか(問題があるからロジックを変更しようとしているのですよね？)
...あたりを書いてもらえますか？

[晶]

返事遅くなってすみません。
最初の方から説明しますね。
問題は川渡りの問題です。
ある人がオオカミとヤギとキャベツをボートで川の対岸に渡さなければならない。
ボートには人とオオカミ、人とヤギ、人とキャベツ、あるいは人が1人しか乗る場所はない。
また、人がいないとオオカミはヤギをヤギはキャベツを食べてしまう。
みんなで渡りきるにはどう渡ればいいか??

添付は横型探索アルゴリズムをC言語を用いたプログラムです。

この川渡りの問題で縦型探索アルゴリズムになるように書き換えたいんですが…
自分でOpenListの更新の部分を作り替えたらOpenListの更新がうまくできませんでした。

[ookami]

むむむ... なるほど...。

最初は、データ構造とfind関数に着目して、「横型検索などではないのでは」と言ったのですが、
全体を見ると、たしかに「横型検索」になっている気がしてまいりました。
# find関数は、「線形検索」ですね。

確認ですが、

　Cell: 人・狼・ヤギ・キャベツがそれぞれ右にいるか左にいるかという状態を表す要素で、
　　　　かつ、双方向リストのポインタと、親状態へのポインタを持つクラス。

　open_list:すでに見つかった、禁止状態でない(何かが何かを食べない)Cellのリスト

　closed_list:すでに見つかった、禁止状態のCellのリスト

という使い方でよろしいでしょうか。
# Cell のリスト構造がちょっち複雑なんですね。
# 双方向リスト と 木構造を合わせ持っているという...
# で、木構造は結果の表示のみに使っており、
# 探索には関係ないようですね。

「再帰」は使っていいでしょうか？
(使っていいテクニックに制限はありますか？)

[ookami]

...もしかして、

if ( find( &open_list, temp ) == &open_list
&& find( &closed_list, temp ) == &closed_list )
push_back( &open_list, temp );

の、
push_back を push_front に変えるだけでよかったりして^^;
ちゃんと試してないのでアレですが。

[晶]

返事遅くなってすみません。
私もpush_back を push_front に変えることはしたんですが、それだけだと探索が最初の一つしかできなくて…

[晶]

/* OpenListの更新（横型探索）*/
if ( find( &open_list, temp ) == &open_list
　　　　　 && find( &closed_list, temp ) == &closed_list )
/* OpenList、ClosedListに無ければOpenListの末尾に追加 */
push_back( &open_list, temp );

これは「新しく得られた各状態Pについて、次を実行する。
PがClosedListかつOpenListに無ければ、PをOpenListの末尾に追加する」というプログラムです。

ここを縦型探索にするため、「(1)PがClosedListに入っていない。
(2)OpenListに重複した状態があれば前に追加された方を削除する。
(3)PをOpenListの先頭に追加する」という感じに書き換えたいんです。

使ってはいけないテクニックなどは得にありません。

[ookami]

push_back を push_front に変えると、
以下のような結果になりましたが、
これは期待した結果ではないということでしょうか？

Open List = 0000
Closed List =
1: Testing 0000

Open List = 1001 1010 1100 1000
Closed List = 0000
2: Testing 1001

1001 は禁止状態
Open List = 1010 1100 1000
Closed List = 0000 1001
3: Testing 1010

Open List = 0010 1100 1000
Closed List = 0000 1001 1010
4: Testing 0010

：
(以下省略)

-- 追記

走査の順番を図にしてみました。

[晶]

はい。
どうやったんですか？？

[ookami]

56003 で示されていたソースについて、
56016 で書いたとおり、

if ( find( &open_list, temp ) == &open_list
&& find( &closed_list, temp ) == &closed_list )
push_back( &open_list, temp );

の、
push_back を push_front に変えただけです。
が...
> 私もpush_back を push_front に変えることはしたんですが、
とのことだったので、既に試されているのだろうと思い、
「これは期待した結果ではないということでしょうか？」という...。

えーと。
> 探索が最初の一つしかできなくて
という所が問題なんでしょうか。

[晶]

回答ありがとうございます。
私が他の部分のプログラムもイジってたみたいでした。
ookamiさんの言うとおりにしたら解決できました。
本当にありがとうございました。