2

非決定論的な問題を解決するプログラムを Haskell で書かなければなりません。List Monad は 75% で理解できると思うので、無意識の選択ですが...

（私の問題は、nxmボードを船と水で満たすことです。行と列の合計が与えられ、船のすべての部分にその値があり、現在は重要ではありません）。

アルゴリズムを効果的にするためにできるだけ早くガードしたい問題は、船の挿入の可能性が私が与えられたものに依存していることです/以前の動きで挿入したものはそれをボード状態と呼びましょうそして私はそれを渡す方法がわかりませんボードだけから新しい状態を生成することはできません)

私のアルゴリズムは次のとおりです。 1.最初のボードを初期化します 2.可能なすべての挿入を適用して最初の行を生成します（羊を垂直に挿入できるので、羊の他の部分を下の行に挿入することを覚えておく必要があります） 3.小さなボードの問題を解決します（ofc 2行ごとに生成した後、すべて問題ないことを確認します）

しかし、State Monadについて読んだ限り、新しい状態を渡す方法がわかりません。それは古い状態だけから新しい状態を生成します。これは私には不可能です。値の操作をしながら新しい状態を生成したいと思います) .

Haskell に対する憎しみで申し訳ありませんが、命令型言語でのプログラミングを数年続けた後、他の言語ではほぼ瞬時に書けるようなことをするためにモナドと戦わざるを得なくなりました。(まあ、Haskell の他のものは私にとっては問題なく、そのうちのいくつかは実際には非常に優れています)。

4

1 に答える 1

9

StateTlist モナドと組み合わせて、目的の動作を取得します。

リストモナドの非決定性を利用しながら、以前の選択の履歴を保持する簡単な例を次に示します。

import Control.Monad
import Control.Monad.Trans.Class
import Control.Monad.Trans.State

fill :: StateT [Int] [] [Int]
fill = do
    history <- get
    if (length history == 3)
        then return history
        else do
            choice  <- lift [0, 1, 2]
            guard (choice `notElem` history)
            put (choice:history)
            fill

fill試行するパスごとに個別の履歴を保持します。ボードがいっぱいになった場合は正常に戻りますが、現在の選択が前の選択と重複する場合は、その解決策を破棄して別のパスを試みます。

を使用して実行evalStateTし、最初の空の履歴を指定します。

>>> evalStateT fill []
[[2,1,0],[1,2,0],[2,0,1],[0,2,1],[1,0,2],[0,1,2]]

すべての可能なソリューションのリストを返します。この場合、それはたまたまボードを埋めることができたすべての順列のリストです。

于 2013-06-23T02:13:19.903 に答える