Haskellで効率的に実装された反復深化検索はどのようにできますか？

StackOverflow https://stackoverflow.com/questions/3757855

質問

解決したい最適化の問題があります。何らかのデータ構造があります：

data Foo =
  { fooA :: Int
  , fooB :: Int
  , fooC :: Int
  , fooD :: Int
  , fooE :: Int
}

と評価関数：

rateFoo :: myFoo -> Int

結果を最適化する必要があります rateFoo 構造体の値を変更することにより。この特定のケースでは、使用することにしました 反復的な深化検索 この問題を解決するために。 （無限の）最適化のための（無限の）検索ツリーは、別の関数によって作成されます。

fooTree :: Foo -> Tree

私の検索機能は次のように見えます：

optimize :: Int -> Foo -> Foo
optimize threshold foo = undefined

私が持っていた質問は、始める前にこれです：

ツリーは各ポイントのデータによって生成できるため、アルゴリズムで現在必要なツリーの部分のみを生成することは可能ですか？メモリを保存するために必要に応じてメモリを解放し、ツリーを再生することは可能ですか？ O(n) そして、nは小さいままですが、時間の経過とともに木全体をメモリにするほど小さくありません）？

これは私がランタイムから興奮できるものですか？ランタイムはできますか 平均 式（評価された式を避けられていない表現に変えます）？または、私がこれのためにしなければならない汚いハックは何ですか？

役に立ちましたか？

解決

これが私のアドバイスです：

  1. 可能な限り最も簡単な方法でアルゴリズムを実装するだけです。
  2. プロフィール。
  3. 必要に応じて、速度またはメモリの使用を最適化します。

私はすぐに、GHCが何をするか、ゴミコレクションがどのように機能するかについて推論するのに十分な経験がないことをすぐに学びました。時には、私が確信していることは、最初に記憶に及ぼすものになると確信しています。

現実世界のハスケル 章 プロファイリングと最適化 ステップ2と3に到達すると、非常に役立ちます。

たとえば、IDDFSの非常に単純な実装があります。 f 子供を拡大し、 p 検索述語です x 出発点です。

search :: (a -> [a]) -> (a -> Bool) -> a -> Bool
search f p x = any (\d -> searchTo f p d x) [1..]
  where
    searchTo f p d x
      | d == 0    = False
      | p x       = True
      | otherwise = any (searchTo f p $ d - 1) (f x)

検索してテストしました "abbaaaaaacccaaaaabbaaccc" と children x = [x ++ "a", x ++ "bb", x ++ "ccc"] なので f. 。かなり速いようで、メモリはほとんど必要ありません（深さの線形と思います）。このようなことを最初に試してから、十分でない場合は、より複雑なデータ構造に移動してみませんか？

他のヒント

ランタイムは式を平均的ではありません。

しかし、あなたが望むものを手に入れる簡単な方法があります。

あなたの木のジッパーのような構造を考えてください。各ノードには値とサンクがダウン、アップなどを保持します。次のノードに移動すると、正常に移動する（対応するスロットに以前のノード値を配置する）か、忘れてしまう（前の式を評価する式を配置することができます。右スロットのノード）。次に、どれだけの「歴史」に固執するかを制御できます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top