Loading article…
宣教師と人食い人種問題と、それに密接に関連する嫉妬深い夫問題は、古典的な川渡り 論理パズルである。[1]宣教師と人食い人種問題は人工知能におけるよく知られたおもちゃの問題であり、ソウル・アマレルによって問題表現の例として使用された。 [2] [3]
問題
宣教師と人食い人種の問題では、3人の宣教師と3人の人食い人種が、最大2人まで乗れるボートで川を渡らなければならない。ただし、両岸で宣教師がいる場合、人食い人種の数の方が宣教師の数より多くならない（もし宣教師がいる場合、人食い人種が宣教師を食べてしまう）という制約がある。ボートは人が乗っていない状態では川を渡ることはできない。また、いくつかのバリエーションでは、人食い人種の1人は片腕しかなく、漕ぐことができない。[1]
嫉妬深い夫の問題では、宣教師と人食い人種が3組の夫婦になり、夫が同席しない限り、女性は他の男性と一緒にいられないという制約がある。この制約の下では、女性が男性より多い状態で川岸に男性と女性が同時にいることはできない。もしそうなった場合、少なくとも1人の女性は夫と一緒ではないことになるからだ。したがって、男性を宣教師に、女性を人食い人種に変えれば、嫉妬深い夫の問題に対する解決策は宣教師と人食い人種の問題に対する解決策にもなる。[1]
解決する
宣教師と人食い人種問題を解決するためのシステム。現在の状態は単純なベクトル ⟨m, c, b⟩ で表されます。ベクトルの要素は、それぞれ宣教師、人食い人種の数、ボートが間違った側にあるかどうかを表します。ボートと宣教師と人食い人種全員が間違った側からスタートするため、ベクトルは ⟨3,3,1⟩ に初期化されます。アクションは、状態ベクトルを操作するためにベクトルの減算/加算を使用して表されます。たとえば、一人の人食い人種が川を渡った場合、状態からベクトル ⟨0,1,1⟩ が減算され、⟨3,2,0⟩ が生成されます。状態は、間違った側にまだ 3 人の宣教師と 2 人の人食い人種がいて、ボートが現在反対側の岸にあることを反映します。問題を完全に解決するには、初期状態をルートとする単純なツリーを形成します。次に、5 つの可能なアクション (⟨1,0,1⟩、⟨2,0,1⟩、⟨0,1,1⟩、⟨0,2,1⟩、および ⟨1,1,1⟩) が初期状態から減算され、その結果がルートの子ノードを形成します。いずれかの岸に宣教師よりも人食い人種が多いノードは無効な状態であるため、それ以上の検討対象から除外されます。生成される有効な子ノードは、⟨3,2,0⟩、⟨3,1,0⟩、および ⟨2,2,0⟩ です。これらの残りのノードごとに、可能なアクション ベクトルをそれぞれ追加することによって子ノードが生成されます。アルゴリズムは、ツリーの各レベルで減算と加算を交互に繰り返し、値としてベクトル ⟨0,0,0⟩ を持つノードが生成されるまで続けます。これは目標状態であり、ツリーのルートからこのノードまでのパスは、問題を解決する一連のアクションを表します。
解決
嫉妬深い夫の問題に対する最も古い解法は、片道11回を使うもので、次の通りである。夫婦は、α（男性）とa（女性）、βとb、γとcとして表される。[4] 、291ページ。
赤い実線は、オプションで漕げない人食い人種を表します。
右の図では、妻または人食い人種がボートに残っている場合 (丸で囲まれている)、より短い解決法が可能です。
これは問題に対する最短の解決策ではあるが、唯一の最短の解決策ではない。[4] 、291ページ。
しかし、一度にボートから出られるのは 1 人の男性だけであり、夫は岸にいるときにのみ妻と一緒にいると見なされ、岸にいるときにボートに乗っているだけではない場合には、5 から 6 への移動は不可能です。なぜなら、γがボートから降りるとすぐに、岸にいるb は、夫がボートに乗っているにもかかわらず、夫と一緒にいなくなるからです。
前述のように、嫉妬深い夫の問題に対するこの解決策は、男性を宣教師に、女性を人食い人種に置き換えることで、宣教師と人食い人種の問題に対する解決策にもなります。この場合、宣教師と人食い人種の個々のアイデンティティは無視できます。今示した解決策は依然として最も短く、4つの最も短い解決策の1つです。[5]
岸辺のボートに乗っている（ただし岸にはいない）女性が一人でいる（つまり岸に男性がいない）とみなされる場合、このパズルは片道 9 回で解くことができます。
バリエーション
明らかな一般化は、嫉妬深いカップル（または宣教師と人食い人種）の数、ボートの定員、またはその両方を変えることです。ボートに2人乗れる場合、2組のカップルは5回の往復が必要です。4組以上のカップルの場合、この問題には解決策がありません。[6] ボートに3人乗れる場合、最大5組のカップルが渡ることができます。ボートに4人乗れる場合、任意の数のカップルが渡ることができます。[4] 、300ページ。 これらの一般化を分析し解決するための簡単なグラフ理論アプローチは、1966年にFraley、Cooke、およびDetrickによって提案されました。[7]
川の真ん中に島を作れば、何組のカップルでも2人乗りのボートを使って川を渡ることができる。川の両岸を渡ることが許可されていない場合、n組のカップルを川の向こうに渡すのに片道8 n −6回の往復が必要となる。 [1] 、p. 76両岸を渡ることが許可されている場合、nが4を超えると4 n +1回の往復が必要となるが、 nが4の場合の最小の解決法では16回の往復のみが必要となる。[1] 、p. 79。嫉妬深いカップルを宣教師と人食い人種に置き換えた場合、川の両岸を渡ることが許可されていなければ往復回数は変わらない。一方、川の両岸を渡ることが許可されていれば、 nが少なくとも3であると仮定する と往復回数は4 n −1回に減少する。 [1] 、p. 81。
歴史
嫉妬深い夫問題が初めて登場するのは、中世の文献Propositiones ad Acuendos Juvenesで、これは通常アルクイン（804年死去）の著作とされる。アルクインの定式化では、カップルは兄弟姉妹であるが、制約は同じで、女性は兄弟がいない限り、他の男性と一緒にいることはできない。[1] 、74ページ。13 世紀から15世紀にかけて、この問題は北欧全域で知られるようになり、カップルは夫婦となった。[4] 、291～293ページ。 この問題は後に、主人と従者という形で表現され、宣教師と人食い人種という定式化は19世紀末まで登場しなかった。[1] 、81ページ カップルの数や船の大きさを変えることが16世紀初頭に検討された。[4] 、293ページ296. カデ・ド・フォントネーは1879年に川の真ん中に島を置くことを検討した。この問題の変種である2人乗りのボートは、1989年にイアン・プレスマンとデイヴィッド・シングマスターによって完全に解決された。 [1]
2020年、この問題を扱った漫画の人種差別的なテーマをめぐる論争により、AQA試験委員会はこの問題を含む教科書を撤回した。[8]
参照
参考文献
- ^ abcdefghi プレスマン、イアン; シングマスター、デイヴィッド（1989年6月）。"「嫉妬深い夫たち」と「宣教師と人食い人種」「.数学ガゼット. 73 (464): 73–81. doi :10.2307/3619658. JSTOR 3619658.
- ^ Amarel, Saul (1968). Michie, Donald (ed.). 「行動についての推論の問題の表現について」.機械知能. 3.アムステルダム、ロンドン、ニューヨーク: Elsevier/North-Holland: 131–171. 2008年3月8日時点のオリジナルよりアーカイブ。
- ^ Cordeschi, Roberto (2006)。「迷路を探索し、知識を求める: 初期の人工知能の課題」。在庫あり、Oliviero、Schaerf, Marco (編)。AI理論とシステムにおける推論、アクション、インタラクション: Luigia Carlucci Aiello に捧げられたエッセイ。コンピュータ サイエンスの講義ノート。第 4155 巻。ベルリン/ハイデルベルク: Springer。pp. 1–23。doi : 10.1007/ 11829263_1。ISBN 978-3-540-37901-0。
- ^ abcde フランシ、ラファエラ (2002). 「川を渡る嫉妬深い夫たち：アルクインからタルターリアまでの問題」。イヴォンヌ州ドルド・サンプロニウスにて。ドーベン、ジョセフ W.フォルケルツ、メンソ。ヴァン・ダーレン、ベンノ（編）。中国からパリへ: 2000 年にわたる数学的アイデアの伝達。シュトゥットガルト：フランツ・シュタイナー・ヴェルラ。 289–306ページ。ISBN 3-515-08223-9。
- ^ リム、ルビー (1992)。ショー、リン・C.、他 (編)。人食い人種と宣教師。APL '92、APL に関する国際会議 (サンクトペテルブルク、1992 年 7 月 6 日～10 日)。ニューヨーク: 計算機協会。pp. 135～142。doi : 10.1145 / 144045.144106。ISBN 0-89791-477-5。
- ^ Peterson, Ivars (2003年12月13日). 「Tricky Crossings」. Science News . 164 (24) . 2011年3月12日閲覧。
- ^ Fraley, Robert; Cooke, Kenneth L.; Detrick, Peter (1966 年 5 月). 「難しい交差パズルのグラフィカルな解決法」.数学雑誌. 39 (3): 151–157. doi :10.1080/0025570X.1966.11975705. JSTOR 2689307.
- ^ ウールコック、ニコラ（2020年7月18日）。「試験委員会AQAが白人宣教師を調理する人食い人種の画像付きGCSEブックを承認」 タイムズ。ISSN 0140-0460 。 2020年7月19日閲覧。