6

List モナドを使用して非決定論的計算を行う方法を理解するという困難を乗り越えました。しかし、私のアルゴリズムは List モナドから得られる深さ優先検索ではなく、幅優先検索の恩恵を受けると思います。

これは、私のアルゴリズムの興味深い部分を示す抜粋です。ロジックパズルあかりのソルバーです。

solve :: Game -> [Game]
solve game = do
        let ruleBasedSolverResult = applyRuleBasedSolversUntilSteady game
        guard $ consistant ruleBasedSolverResult
        if solved ruleBasedSolverResult
                then return ruleBasedSolverResult
                else speculate ruleBasedSolverResult

speculate :: Game -> [Game]
speculate game = do
        coord <- coords game
        guard $ lightableUnlit game coord
        let solutions = solve $ light game coord
        if null solutions
                then solve $ exclude game coord
                else solutions

基本的に、いくつかの基本的な決定論的ルールを適用して、それが解決するかどうかを確認します。なければライトをいろいろなところに置いてみます。解決するために再帰した後、ライトがパズルを矛盾させる場合、ライトがあった場所に除外マークを配置して続行します。ライトの配置中に解決策が見つかった場合は、それらを解決策のリストに追加します。

これは問題なく動作しますが、多くの場合、推測する座標の明らかな選択があり、すぐに一貫性のないパズルになり、1 つ (または 2 つ) の検索レベルで x を配置できるようになるため、遅くなります。検索の途中までその座標を選択すると、最初に興味のないものをたくさん噛んでしまいます。したがって、幅優先検索のアイデアです。

「幅優先非決定性モナド」などをグーグルで検索したところ、次のような理解しにくい結果がいくつか得られました。

  • Control.Monad.Omegaこれは、私には当てはまらない無限に発散する決定論を防ぐように見えるため、私が必要としているものにはやり過ぎのように思えますが、私はそれを完全には理解していません。

  • Control.Monad.WeightedSearch Control.Monad.Omega のドキュメントでは、モナドとして使用する場合は代わりにこれを使用することを提案していますが、重み付けも私のニーズには少しやり過ぎだと思います。1 つは解決策のあるもの用で、もう 1 つは解決策がないもの用です。

  • Control.Monad.Levelツリーの葉だけが値を持っているので、これが私が望むものに対してうまくいくとは思いません。

  • Data.Treeこれは私が使いたいものかもしれないと思いますが、美しい方法があるように感じますが、それを使用するために List モナド コードを変換する方法がわかりません。

私の次の質問は、それを並列化する方法についてです:)

4

1 に答える 1