Clever Geek Handbook

動的プログラミングと遅延計算

動的プログラミングは、タスクをサブタスクに分割し、これらのサブタスクが他のいくつかのサブタスクの一部である場合でも、これらのサブタスクを一度解決することに基づいて、多くの複雑な問題を解決する上でかなり重要なアプローチです。 関数型プログラミングを習得し始めたばかりの人にとっては、「 変数を使用して結果を保存しない場合にサブタスクの解決を回避する方法は？ 」 という疑問がしばしば発生します。 「。 この問題では、関数型プログラミングの1つの機能（変数の欠如）により、サブタスクを解決した結果をキャッシュするのが難しくなりますが、別の機能（遅延計算）が役立ちます。



集水域を見つける問題を考慮してください。

エリアのマップが表示され、高さの長方形のマトリックス（整数など）で表されます。 次の場合、水は各セルから最も低い高さで隣接するセル（北、東、南、西）のいずれかに流れます。

特定のセルの高さよりも小さい。 それ以外の場合、このセルはドレインと呼ばれます。 マップのすべてのセルを等しくマークする必要があります。そこから水は同じ溝に流れ込みます。



したがって、1つのセルの排水を見つけるには、その隣の排水を見つける必要があります（排水自体ではない場合）。複数の異なるセルからの水が収集され、同じルートに沿って1つの排水に流れ込むことは明らかです。

かなり単純な再帰アルゴリズムが思い浮かびます： 

 drainOf cell = 
  のケースのminimumNeighbourOfセル
    なし→セル
    ちょうどnb→drainOf nb


ただし、この場合、各セルのドレインは何回も計算されます。

この場合、遅延計算が役立ちます。その本質は、結果が他の場所で必要になるまで式が評価されず、計算後に必要に応じて結果が再利用されることです。

これが必要です！

問題は、Haskellですべての（ほぼ）計算が遅延している場合、上記のコードが中間結果をキャッシュしないのはなぜですか？

問題は、次のコードでは式が異なり、関数が2回呼び出されることです。 

印刷（drainOfセル）
印刷（drainOfセル）


ただし、次のコードでは、関数は1回だけ呼び出されます。 

 let drain = drainOf cell
プリントドレイン
プリントドレイン


つまり どういうわけか同じ式を意味することを示す必要があります。そうすれば、遅延計算が機能します。 

セル=（（1,1）、（幅、高さ））

高度::（Int、Int）→Int

 -ここに、すべてのセルのドレインの配列があります！ しかし、それは遅延計算されます
 -つまり これはdrainOfの呼び出しのリストに過ぎず、その結果ではありません
 drains =配列セル[（cell、drainOf cell）| セル←範囲セル]
  
 drainOf cell = 
  のケースのminimumNeighbourOfセル
    なし→セル
    ただnb→ドレイン！  nb-ストック配列の要素へのアクセス
     -ここで最初の呼び出しで、drainOfの計算が行われます。
     -そして2番目-キャッシュされた結果の戻り

 minimumNeighbourOf（x、y）=
   let neighbors = filter（inRange cells）[ 
                         （x、y-1）、（x + 1、y）、（x、y + 1）、（x-1、y）]
      最低= minimumBy（高度を比較）近隣
  で
      最低高度≥高度（x、y）の場合
            それから何も
            他の最も低い


それだけです。レイジーコンピューティングとは何かを理解してください。



UPD：根拠がないように、完全なプログラムとその出力を追加することにしました。 

インポートData.Array
 Debug.Traceのインポート（トレース）
 Control.Monadのインポート（forM_）
 Data.Listのインポート（最小値、転置）
インポートData.Function（オン）

 -シンプルなデータ-

セル=（（1,1）、（3,3））

高度= listArrayセル$ concat $ transpose [
     [10、8、10]、
     [15、3、15]、
     [20、25、20]]

 -一般的な機能-

高度::（Int、Int）→Int
高度セル=高度！ セル

 minimumNeighbourOf（x、y）=
   let neighbors = filter（inRange cells）[ 
                         （x、y-1）、（x + 1、y）、（x、y + 1）、（x-1、y）]
      最低= minimumBy（高度を比較）近隣
  で
      最低高度≥高度（x、y）の場合
            それから何も
            他の最も低い

 printArray arr =
     let（（sx、sy）、（ex、ey））= bounds arr
         printRow y = forM_ [sx..ex]（λx→putStr（show（arr！（x、y））++ "\ t"））
    で
         forM_ [sy..ey]（λy→printRow y»putStrLn ""）

メイン= 
   printArray高度を行う
      putStrLn "-ドレイン-------------"
      printArrayドレイン
      putStrLn "-drains ′------------"
      printArrayドレイン ′

 -単純な再帰-

 drains =配列セル[（cell、drainOf cell）| セル←範囲セル]

 drainOfセル|  trace（ "drainOf" ++セルを表示）False =未定義
 drainOf cell = 
  のケースのminimumNeighbourOfセル
    なし→セル
    ちょうどnb→drainOf nb

 -遅延キャッシュ-

 drains ′=配列セル[（cell、drainOf′ cell）| セル←範囲セル]

 drainOf ′セル|  trace（ "drainOf ′" ++セルを表示）False =未定義
 drainOf ′cell = 
  のケースのminimumNeighbourOfセル
    なし→セル
    ただnb→ドレイン '！  NB


結果： 

 10 8 10	
 15 3 15	
 20 25 20	
 -排水溝-------------
 drainOf（1,1）
 drainOf（2.1）
 drainOf（2.2）
 drainOf（2.1）
 drainOf（2.2）
 drainOf（3.1）
 drainOf（2.1）
 drainOf（2.2）
 （2.2）（2.2）（2.2）	
 drainOf（1,2）
 drainOf（2.2）
 drainOf（2.2）
 drainOf（3.2）
 drainOf（2.2）
 （2.2）（2.2）（2.2）	
 drainOf（1.3）
 drainOf（1,2）
 drainOf（2.2）
 drainOf（2,3）
 drainOf（2.2）
 drainOf（3.3）
 drainOf（3.2）
 drainOf（2.2）
 （2.2）（2.2）（2.2）	
 -排水管------------
 drainOf '（1,1）
 drainOf '（2.1）
 drainOf '（2,2）
 drainOf '（3.1）
 （2.2）（2.2）（2.2）	
 drainOf '（1,2）
 drainOf '（3.2）
 （2.2）（2.2）（2.2）	
 drainOf '（1,3）
 drainOf '（2,3）
 drainOf '（3.3）
 （2.2）（2.2）（2.2）


ご覧のとおり、最初のオプションは各セルのストックを何度も計算しましたが、2番目のオプションは一度だけ計算しました。


More articles:


All Articles