Haskellの宣教師と人食い問題の解決

Haskell言語を勉強して、私は再び、新しいスキルを開発するためのタスクを見つけるという問題に直面しました。 いくつかの熟考の後、宣教師と人食い人のフェリーの問題のために、Pythonでずっと前に書かれた幅優先探索アルゴリズムを実装することが決定されました。 この決定は私にはかなり簡潔に思えたので、私はそれを人々と共有することを決めました（そして同時に批判に耳を傾けます）。



興味のある方は、Catに進んでください。

タスクステートメント

3人の宣教師と3人の人食い人を川の1つの銀行から他の銀行に輸送する必要があります。 彼らが移動するボートでは、一度に2人しか入ることができませんが、移動中に1つの海岸の人食い人の数が宣教師の数を超える場合、宣教師は食べられます（もちろん避けなければなりません）。 一連の安全な（ジェームズクックの悲しい運命に宣教師を導いていない）トラフィックを見つける必要があります。

解決策

劇場はハンガーから始まり、Haskellプログラムは作業に必要なモジュールのインポートから始まります。 それらから始めましょう。

import Data.List
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

宣教師、人食い人、ボートが置かれている海岸の位置に関する情報を保存するために、データタイプを定義します。

 data State = State { missioners :: Int, cannibals :: Int, bank :: Char} deriving (Eq, Show)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

気配りのある読者は、「Stateに整数フィールドが2つしかないのはなぜですか？ 宣教師は左岸と右岸の両方にいることができます。 同じことが人食い人にも当てはまります。 4つの数値フィールドが判明します。」

本当の発言ですが、特定の理由で、ボートなしで上陸している人々の数に関する情報は冗長です（一部の人にとっては、少し後で言われます）。



ボートがある海岸から別の海岸に泳ぐためには、可能なすべての動きを設定する必要があります。 それらは5つだけです。

 move01 (State msn cnb bk) = State (3 - msn + 2) (3 - cnb) (oppositeBank bk) move02 (State msn cnb bk) = State (3 - msn) (3 - cnb + 2) (oppositeBank bk) move03 (State msn cnb bk) = State (3 - msn + 1) (3 - cnb + 1) (oppositeBank bk) move04 (State msn cnb bk) = State (3 - msn + 1) (3 - cnb) (oppositeBank bk) move05 (State msn cnb bk) = State (3 - msn) (3 - cnb + 1) (oppositeBank bk)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

気づいた？ 反対側の銀行に何人の宣教師がいるかについての情報を保存する必要はありません。現在の銀行の宣教師の数を3人から引くことで、常に彼らの数を得ることができます。 人食い人も同じです。



inverseBank-海岸ラベルを反対に変更する最も単純な関数。

 oppositeBank :: Char -> Char oppositeBank bank | bank == 'L' = 'R' | otherwise = 'L'
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

新しい状態を作成したら、それが可能かどうかを確認する必要があります（簡単に言えば、ボートで海岸に4人の宣教師がいる、またはさらに楽しいことは、1.5木こりから1人の人食い人がいるという状況に至らなかったということです）。

 isStatePossible :: State -> Bool isStatePossible (State msn cnb bk) = msn >= 0 && msn <= 3 && cnb >= 0 && cnb <= 3
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

条件が安全かどうかも確認する必要があります。 3つの可能なオプションがあります。 1つは、宣教師の数に等しい人食い人種の数です。 2番目-現在の海岸に3人の宣教師がいます（この場合、反対側の海岸には宣教師はい​​ません。状況は安全です）。 3番目は2番目の反対です。すべての宣教師は反対側の銀行に集まりました。

それでは書き留めましょう。

 isStateSafe :: State -> Bool isStateSafe (State msn cnb bk) = (cnb == msn) || (msn == 3) || (msn == 0)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、最も重要なことである幅優先探索に目を向けます。 リンクをクリックすると、その内容を確認できますが、実装の説明に焦点を当てます。

 bfsSolution :: [[State]] -> [State] bfsSolution (path:tail') | State 3 3 'R' `elem` extensions = State 3 3 'R' : path | otherwise = bfsSolution $ tail' ++ [ext : path | ext <- extensions, (not . elem ext) path] where headState = head path extensions = filter (\x -> isStatePossible x && isStateSafe x) [move01 headState, move02 headState, move03 headState, move04 headState, move05 headState]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

bfsSolutionは再帰的な手順です。 まず、すでに構築されているパスのリストから、先頭にあるパスを取得します。 私たちはそれを継続し、すべての可能な（そして安全な）継続を構築しようとしています。 構築された継続の1つが最終状態である場合、プロシージャは作業を終了し、継続されたパスを返します。 それ以外の場合は、生成されたすべてのパスをリストの末尾に追加して、プロシージャを再度呼び出します。

状態は非常に重要です。

 (not . elem ext) path
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このパスを構築する過程で、アルゴリズムによって渡された状態の1つに戻ることはできません。 たとえば、手順nで2人の宣教師を左岸から右に送った場合、手順（n + 1）で彼らを左岸に戻す意味はありません-時間を無駄にし、1つの手順を進めません（指定されたプログラムが見つけます）私のネットブックでは、解決策は0.85秒です;上記の条件を削除すると、計算がかなり大きくなります-答えを見つけるのに45秒かかります）。



最後の仕上げが主な機能です。

 main = do mapM_ (putStrLn . show) $ (reverse . bfsSolution) ([[State 3 3 'L']])
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

おわりに

この記事は、この問題に対するすべての可能な解決策の包括的なレビューおよび網羅的な説明を主張するものではありません。 興味のある読者は、リターンを使用して詳細検索アルゴリズムを実装できます。 上記のソリューションを「思い起こさせる」という別の（まだ実装されていない）アイデアもあります。リストのリストに生成されたすべてのソリューションを保存することをやめ、n進ツリーを実装します。

ご清聴ありがとうございました。