एफ #

Question

में गतिशील प्रोग्रामिंग problems with overlapping subproblems को हल करने वाले गतिशील प्रोग्रामिंग एल्गोरिदम को लागू करने का सबसे शानदार तरीका क्या है? अनिवार्य प्रोग्रामिंग में आमतौर पर समस्या के आकार से अनुक्रमित एक सरणी (कम से कम एक आयाम) बनाते हैं, और फिर एल्गोरिदम सबसे सरल समस्याओं से शुरू होता है और पहले से गणना किए गए परिणामों का उपयोग करके एक बार जटिल हो जाता है।

सबसे सरल उदाहरण मैं की वां फिबोनैकी संख्या की गणना कर रहा है लगता है कर सकते हैं:

int Fibonacci(int N) 
{ 
    var F = new int[N+1]; 
    F[0]=1; 
    F[1]=1; 
    for(int i=2; i<=N; i++) 
    { 
     F[i]=F[i-1]+F[i-2]; 
    } 
    return F[N]; 
} 

मुझे पता है तुम एफ # में एक ही बात लागू कर सकते हैं, लेकिन मैं एक अच्छा कार्यात्मक समाधान के लिए देख रहा हूँ (जो हे है (एन) साथ ही स्पष्ट रूप से)।

Answer 1

एक तकनीक है कि गतिशील प्रोग्रामिंग के लिए काफी उपयोगी है Memoization कहा जाता है। अधिक जानकारी के लिए, उदाहरण के लिए देखें blog post by Don Syme या introduction by Matthew Podwysocki।

विचार यह है कि आप (एक बेवकूफ) रिकर्सिव फ़ंक्शन लिखते हैं और फिर पिछले परिणामों को संग्रहीत करने वाले कैश को जोड़ते हैं। यह आपको फ़ंक्शन को सामान्य कार्यात्मक शैली में लिखने देता है, लेकिन गतिशील प्रोग्रामिंग का उपयोग करके कार्यान्वित एल्गोरिदम का प्रदर्शन प्राप्त करता है।

उदाहरण के लिए, फिबोनैकी संख्या की गणना के लिए एक अनुभवहीन (अक्षम) समारोह इस तरह दिखता है:

let rec fibs n = 
    if n < 1 then 1 else 
    (fibs (n - 1)) + (fibs (n - 2)) 

यह अक्षम है, क्योंकि जब आप fibs 3 कहते हैं, यह fibs 1 तीन बार (और कई और अधिक बार अगर कॉल करेंगे आप कॉल करते हैं, उदाहरण के लिए, fibs 6)। ज्ञापन के पीछे विचार यह है कि हम एक कैश लिखते हैं जो fib 1 और fib 2 के परिणाम संग्रहीत करता है, और इसी तरह, इसलिए दोहराए गए कॉल केवल कैश से पूर्व-गणना मूल्य चुनेंगे।

एक सामान्य समारोह Memoization इस तरह लिखा जा सकता है करता है कि:

open System.Collections.Generic 

let memoize(f) =  
    // Create (mutable) cache that is used for storing results of 
    // for function arguments that were already calculated. 
    let cache = new Dictionary<_, _>() 
    (fun x -> 
     // The returned function first performs a cache lookup 
     let succ, v = cache.TryGetValue(x) 
     if succ then v else 
     // If value was not found, calculate & cache it 
     let v = f(x) 
     cache.Add(x, v) 
     v) 

अधिक कुशल फाइबोनैचि समारोह लिखने के लिए, हम अब memoize फोन और यह समारोह है कि एक तर्क के रूप गणना करता है दे सकते हैं:

let rec fibs = memoize (fun n -> 
    if n < 1 then 1 else 
    (fibs (n - 1)) + (fibs (n - 2))) 

ध्यान दें कि यह एक पुनरावर्ती मूल्य है - फ़ंक्शन का बॉडी ज्ञात fibs फ़ंक्शन को याद करता है।

Answer 2

टॉमस का उत्तर एक अच्छा सामान्य दृष्टिकोण है। अधिक विशिष्ट परिस्थितियों में, अन्य तकनीकें हो सकती हैं जो अच्छी तरह से काम करती हैं - उदाहरण के लिए, आपके फाइबोनैकी मामले में आपको वास्तव में केवल एक सीमित राशि की स्थिति (पिछली 2 संख्याएं) की आवश्यकता होती है, न कि पहले की गणना की गई सभी मान। यह अक्सर एक memoized (पुनरावर्ती) को पढ़ने के लिए एक बहुत आसान है

let fib = 
    let rec loop i j = function 
    | 0 -> i 
    | n -> loop j (i+j) (n-1) 
    loop 1 1 

Answer 3

let fibs = 
    (1I,1I) 
    |> Seq.unfold (fun (n0, n1) -> Some (n0 , (n1, n0 + n1))) 
    |> Seq.cache