川渡り問題
From Wikipedia, the free encyclopedia
- 川岸にいる一団を対岸に渡す。
- 川を渡る手段は小船だけであり、小さいので全員は乗れないため、小分けにして往復する必要がある。
- 「小船を漕げる者が限定されており、その者が小船に乗っていないと移動できない」という条件が与えられる場合もある。
- 特定の組み合わせがどちらかの岸にできてはいけない。
- 多くは「○○がいない状態で□□と△△を一緒にしてはいけない」という形で条件が与えられる。
例題
簡単な例
1人の大人と2人の子供が岸にいて、ボートが1艘ある。ボートには、大人は1人だけが乗れ、子供は1人または2人が乗れる（ボートを漕ぐことは全員が可能）。全員が川を渡るにはどうすればよいか?
狼とヤギとキャベツ
この問題は、8世紀にカンタベリーの大主教が提示した問題といわれている。
オオカミとヤギを連れ、キャベツを持った農夫が川岸にいる。川には1艘のボートがある。
- ボートを漕げるのは農夫のみ。
- ボートには農夫のほか、動物1頭かキャベツ1個しか乗せられない。
- 農夫がいないときにオオカミとヤギを岸に残すと、オオカミがヤギを食べてしまう。
- 農夫がいないときにヤギとキャベツを岸に残すと、ヤギがキャベツを食べてしまう。
すべてを無事に対岸に渡すにはどうしたらよいか?
オオカミを狐、ヤギをガチョウ、キャベツを豆の袋に替えた問題もある。
宣教師と先住民
3人の宣教師と3人の先住民が川岸にいる。川には2人まで乗れるボートが1艘ある。
- ボートを漕げるのは宣教師のうちの1人と、先住民のうちの1人だけである。
- どちらかの岸で先住民の数が宣教師の数より多くなると、先住民は反旗を翻し宣教師に襲い掛かる。
全員が無事に対岸に渡るにはどうしたらよいか?
考え方
禁止されている状態にならないように移動させていれば、ほぼ一本道で解けてしまうこともある。
下記の点を考えるとうまくいくことが多い。
- ボートをこげる人を確保する。
- 対岸に渡した人（物）を，後でもう一度連れて帰る。
- 最初は，2人以上（または1人と何か）で渡るしかない。
- もし1人だけで渡ると，その1人が戻って来るしかないので，始めの状態に戻ってしまうから。
また、コンピュータプログラムで（普通のプログラミング言語で、あるいは論理プログラミングや何らかのソルバー等で）コンピュータに解かせようとする場合、問題の文としては明示されない（が、論理的に詰めてゆくと必要な）制約や可能な移動についての規則の追加が必要なこともある[1]。
バリエーション
一団の条件を変えれば新しい問題を作ることができる。嫉妬深い（自分がいないところで妻が他の男といるのが嫌という）夫婦たちの問題などが有名である。
また、
- 川の途中に中州を設ける。（人や荷物を置くことができる）
- ボートの定員や台数を変える。
等で新しい問題を作ることもできる。