ある夫婦３組が２人乗りのボートで対岸に渡るという縦型探索アルゴリズムを

ある夫婦３組が２人乗りのボートで対岸に渡るという縦型探索アルゴリズムをC言語でプログラミングしたいのですが、どのようなプログラミングをすればよいのでしょうか？

ルールは、
１、夫婦の妻は一人では対岸に渡ることができない。（一人で戻るのは可能）
２、妻は、自分の旦那以外とは一緒に渡れない
です。

縦型探索なので、OpenListやClosedListを使うのですが、わかりません。
回答でもヒントでもよいのでよろしくお願いします。

またなにか、わからないことやくわしいことが聞きたいなどもどんどんかきこんでください。
お願いします。

No.3 回答者： emu0202 回答日時： 2010/07/07 12:41

Ｃ言語で実装するという話だと、情報系の大学生のレベルを超えていると思います。

Ｃ言語はあきらめて、Promelaという言語、SPIN model checkerというツールを用いて解くことをオススメします。

No.2 回答者： nak777r 回答日時： 2010/07/07 12:17

A=夫 a=妻

B=夫 b=妻
C=夫 c=妻

移動可能なパターン
1=A
2=Aa
3=AB
4=AC
5=B
6=Bb
7=BC
8=C
9=Cc

こっち　あっち
AaBbCc　AaBbCc　回　可能パターン　
111111　000000　01　123456789　

回が奇数ならこっちからあっちに行くターン
回が偶数ならあっちからこっちに行くターン

可能パターンの内数字の小さい方からやっていく事にする

AaBbCc　AaBbCc　回　可能パターン　試行パターン
111111　000000　01　123456789　1
011111　100000　02　-00000000　-

行きと同じ状態で帰る事になる可能パターンの項目は '-'で記載
すると、２回目で手詰まりとなる

試行パターン 1が手詰まりだったので１個戻し試行パターン2でやってみる

AaBbCc　AaBbCc　回　可能パターン　試行パターン
111111　000000　01　123456789　2
001111　110000　02　1-0000000　1

行きと同じとなる試行パターン2 を '-' とすると、他に可能なパターンは 1のみ

AaBbCc　AaBbCc　回　可能パターン　試行パターン
111111　000000　01　123456789　2
001111　110000　02　1-0000000　1
101111　010000　03　-03456789　3

前回と同じになる試行パターン1 を '-' また a は居ないため可能パターン2は
成立しないため '0' で記載した、すると次は 試行パターン 3（AB)となる

AaBbCc　AaBbCc　回　可能パターン　試行パターン
111111　000000　01　123456789　2
001111　110000　02　1-0000000　1
101111　010000　03　-03456789　3
000111　111000　04　12-000000　1

同様に続けていくと

AaBbCc　AaBbCc　回　可能パターン　試行パターン
111111　000000　01　123456789　2
001111　110000　02　1-0000000　1
101111　010000　03　-03456789　3
000111　111000　04　12-000000　1
100111　011000　05　-00400089　4
000101　111010　06　123-50780　1
100101　011010　07　-00000000　-

７回目で手詰まりになったので、１つ前の試行パターンを次に可能な2にする

AaBbCc　AaBbCc　回　可能パターン　試行パターン
111111　000000　01　123456789　2
001111　110000　02　1-0000000　1
101111　010000　03　-03456789　3
000111　111000　04　12-000000　1
100111　011000　05　-00400089　4
000101　111010　06　123-50780　2
110101　001010　07　1-0000000　1
010101　101010　06　-03450780　3
　：　　　：　　：　　：

イメージとしてはこんな感じになっていく
んじゃないかな

No.1 回答者： tatsu99 回答日時： 2010/07/06 18:12

プログラムは別として、

徳川さん夫婦
織田さん夫婦
豊臣さん夫婦がいたとして、
１．徳川さん夫婦が二人で渡り、旦那が戻る。
２．織田さん夫婦が二人で渡り、旦那が戻る。
３．豊臣さん夫婦が二人で渡り、旦那が戻る。
４．徳川さんと織田さんの旦那同士でわたり、徳川さんが戻る。
５．徳川さんと豊臣さんの旦那同士でわたり、おしまい。
というのはＯＫですか。

この回答への補足

ありがとうございます。

それもオッケーです＾＾

補足日時：2010/07/06 21:32