bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

Haskellでクイズ「嫉妬深い男たち」を解く(2)

1.人工知能における幅優先探索

「嫉妬深い男たち」を解くための良いアルゴリズムは見つかっただろうか。アルゴリズムが見つかったとしても、クイズが与えられるたびに、それを解くためのアルゴリズムを見つけていたのではきりがない。

人工知能の分野では、解を探索するための、一般的なアルゴリズムを提供している。とくに有名なのは、深さ優先探索幅優先探索である。

「嫉妬深い男たち」の問題は、①川に着いたときに、乗船する人たちを選び出す。②対岸に着いたら、帰る舟に乗船する人たちを選び出す。③舟が戻ってきたら、また、乗船する人たちを選び出す、という操作を全員が対岸に渡るまで、繰り返すことになる。

上記の操作を一般化すると、舟が着いたときに、岸にいる人とこちら側に渡ってきた人の中から、次に乗船する人たちを選び出すという操作を繰り返すこととなる。

乗船できる人たちの候補は、通常は、一つとは限らず、複数ある場合が多い。深さ優先探索は、①いくつかある候補の中から、一つだけを実行する、②それがうまくいけば、それを実行した後の候補の中から一つだけ実行する、③もし、うまくいかなければ、ひとつ前に戻り、そこで実行されなかった候補の中から一つを選んで、同じ動作を繰り返す。④ひとつ前に戻っても実行されなかった候補がなければ、さらに、ひとつ前に戻り、同じ処理を繰り返す、という処理を行う。深さ優先探索の利点は、これまでの履歴をあまり記憶しておかなくてもよいという点にあるが、欠点は震度が最も少ない解を見つけられない可能性があるという点にある。

幅優先探索では、その利点と欠点は、深さ優先探索と逆になっている。幅優先探索は、①全ての候補を列挙する(これは深度1での可能なすべての候補である)、②列挙されたすべての候補について、その次に可能となる候補のすべてを列挙する(これは深度2での可能なすべての候補である)、③この操作を買いが見つかるところまで続ける(これは深度\(n\)での可能なすべての候補である)。

2.人工知能の解法を「嫉妬深い男たち」に応用する

「嫉妬深い男たち」の問題は、三組のカップルと登場人物が少ないので、(また、最近のパソコンはメモリをたくさん積んでいて、膨大な履歴を記憶することもあまり気にならなくなってきたので、)幅優先探索で解くこととする。三組のカップルが川岸に着いた時、乗船できるあらゆる候補を列挙しなければならない。それはつぎのようになる。

{(女性1), (女性2) ,(女性3), (女性1, 女性2) , (女性2, 女性3) , (女性3, 女性1) , (男性1, 女性1) , (男性2, 女性2) , (男性3, 女性3) }

幅優先探索を選んだが、深度1の段階で9個の候補がある。深度2ともなるとさらに多くなりそうで、先行きに不安を覚える。あきらめて、深さ優先探索に移行したほうが良いのであろうか?