प्रौद्योगिकी साझेदारी

एल्गोरिदम अध्ययन टिप्पणियाँ (8) - गतिशील प्रोग्रामिंग के मूल बातें

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

विषयवस्तुसारणी

मूलभूतसामग्री : १.

गतिशील प्रोग्रामिंग : १.

गतिशीलप्रोग्रामिंगस्य अवगमने समस्याः प्रवर्तन्ते : १.

विश्लेषणम् : (हिंसकः पश्चात्तापः) २.

कोड उदाहरणम् : १.

क्रूर अन्वेषण : १.

Dfs कोड उदाहरणम् : (अन्वेषणम्)

क्रूरबल पुनरावृत्तिद्वारा उत्पन्नः पुनरावृत्तिवृक्षः : १.

कण्ठस्थं अन्वेषणम् : १.

कोड उदाहरणम् : १.

गतिशील प्रोग्रामिंग : १.

कोड उदाहरणम् : (गतिशील प्रोग्रामिंग, लघुतम उपसमस्यायाः आरम्भः)

निष्पादनप्रक्रिया (गतिशीलप्रोग्रामिंग) : १.

विश्लेषणम् : (गतिशील प्रोग्रामिंग) २.

अन्तरिक्ष अनुकूलनम् : १.

कोड उदाहरणम् : १.

आँकलन:


मूलभूतसामग्री : १.

डायनामिक प्रोग्रामिंग् इति किम्, डायनामिक प्रोग्रामिंग् इत्यनेन काः समस्याः साधनरूपेण समाधानं कर्तुं शक्यन्ते, डायनामिक प्रोग्रामिंग् इत्यस्य वर्गीकरणं, विशिष्टानां समस्यानां वर्गीकरणं च यत् विशिष्टवर्गीकरणैः समाधानं कर्तुं शक्यते

गतिशील प्रोग्रामिंग : १.

इदं महत्त्वपूर्णं एल्गोरिदम् प्रतिमानं भवति यत् समस्यां लघु उपसमस्यानां श्रृङ्खलायां विघटयति तथा च उपसमस्यासमाधानं संग्रह्य पुनः पुनः गणनां परिहरति, अतः समयदक्षतायां महतीं सुधारं भवति

गतिशीलप्रोग्रामिंगस्य अवगमने समस्याः प्रवर्तन्ते : १.

सोपानं आरोहणस्य प्रकरणस्य माध्यमेन एषा समस्या प्रवर्तते यत् कुलम् n सोपानं युक्तं सोपानं दत्तं चेत् भवनस्य शिखरं प्रति आरोहणार्थं कति विकल्पाः सन्ति?

विश्लेषणम् : (हिंसकः पश्चात्तापः) २.

अस्य प्रश्नस्य लक्ष्यं समाधानसङ्ख्यां अन्वेष्टुम् अस्ति,वयं पश्चात्तापं कृत्वा सर्वाणि सम्भावनानि सम्पूर्णतया क्षीणं कर्तुं विचारयितुं शक्नुमः . विशेषतः, सोपानं आरोहणं बहुगोलचयनप्रक्रियारूपेण कल्पयन्तु: भूमौ आरभ्य, प्रत्येकं गोलं एकं वा द्वौ वा सोपानौ चयनं कृत्वा, प्रत्येकं सोपानशिखरं प्राप्य विकल्पसङ्ख्यायां १ योजयित्वा, विकल्पानां संख्यां वर्धयितुं च यदा त्वं सोपानस्य शिखरं प्राप्नोषि।

कोड उदाहरणम्

  1. # python代码示例
  2. def backrack(choices,state,n,res) :
  3. if state == n :
  4. res[0] += 1
  5. for choice in choices :
  6. if state + choice > n :
  7. continue
  8. backrack(choices,state+choice,n,res)
  9. def climbing_stairs_backrack(n) :
  10. choices = [1,2]
  11. state = 0
  12. res = [0]
  13. backrack(choices,state,n,res)
  14. return res[0]
  15. n = int(input())
  16. print(climbing_stairs_backrack(n))
  1. // c++代码示例
  2. void backrack(vector<int> &choices, int state, int n, vector<int> &res)
  3. {
  4. if (state == n )
  5. {
  6. res[0]++ ;
  7. }
  8. for (auto &choice : choices)
  9. {
  10. if (state + choice > n)
  11. {
  12. continue ;
  13. }
  14. backrack(choices, state + choice, n, res)
  15. }
  16. }
  17. int climbingStairsBackrack(int n)
  18. {
  19. vector<int> choices = {1 , 2 } ;
  20. int state = 0 ;
  21. vector<int> res = [0] ;
  22. backrack(choices, state, n, res) ;
  23. return res[0] ;
  24. }

क्रूर अन्वेषण : १.

पश्चात्ताप-एल्गोरिदम् सामान्यतया समस्यां स्पष्टतया न विच्छिन्दति, परन्तु समस्यां निर्णय-पदार्थानाम् एकां श्रृङ्खलारूपेण व्यवहरति, तथा च अनुमान-विज्ञानस्य, छंटाई-द्वारा च सर्वेषां सम्भाव्यसमाधानानाम् अन्वेषणं करोति

समस्याविघटनस्य दृष्ट्या अस्य प्रश्नस्य विश्लेषणं कर्तुं प्रयत्नः कर्तुं शक्नुमः। कल्पयतु यत् i-तमस्तरं प्रति आरोहणार्थं dp[i] समाधानाः सन्ति, तर्हि dp[i] मूलसमस्या अस्ति, तस्य उपसमस्याः च सन्ति:

दप[इ-१],दप[इ-२],दप[१],दप[२] ।

यतो हि वयं प्रत्येकस्मिन् गोले केवलं १ वा २ सोपानानि एव उपरि गन्तुं शक्नुमः, यदा वयं i-तमे सोपानं तिष्ठामः तदा पूर्वपरिक्रमे केवलं i-१ वा i-२ सोपानेषु एव स्थातुं शक्नुमः अन्येषु शब्देषु वयं केवलं i-1th अथवा i-2th स्तरात् i-th स्तरं प्रति गन्तुं शक्नुमः।

अस्मात् वयं महत्त्वपूर्णं अनुमानं कर्तुं शक्नुमः यत् i-1-स्तरं प्रति आरोहितानां योजनानां संख्या प्लस् i-2-स्तरं प्रति आरोहितानां योजनानां संख्या i-पर्यन्तं आरोहितानां योजनानां संख्यायाः तुल्यम् अस्ति -थ स्तर। सूत्रं यथा---

dp[i] = dp[i-1] + dp[i-2] ।

भवनारोहणसमस्यायां पुनरावर्तनीयः सम्बन्धः अस्ति, उपसमस्यानां समाधानं निर्माय मूलसमस्यायाः समाधानं कर्तुं शक्यते इति तात्पर्यम्

Dfs कोड उदाहरणम् : (अन्वेषणम्)

  1. # python 代码示例
  2. def dfs(i : int) -> int :
  3. if i == 1 or i == 2 :
  4. return i
  5. count = dfs(i - 1) + dfs(i - 2)
  6. return count
  7. def climbing_stairs_dfs(n : int) -> int :
  8. retunr dfs(n)
  1. // c++ 代码示例
  2. int dfs(int i)
  3. {
  4. if (i == 1 || i == 2)
  5. {
  6. return i ;
  7. }
  8. int count = dfs(i - 1) + dfs(i - 2);
  9. return count ;
  10. }
  11. int climbingStairsDFS(int n)
  12. {
  13. retunr dfs(n) ;
  14. }

हिंसकपुनरावृत्तिजन्यः पुनरावर्तनीयः वृक्षः

पुनरावर्तनीयवृक्षे उपर्युक्तस्य द्वितीयकसमस्यायाः समाधानार्थं स्मृतिसन्धानपद्धत्या पुनः पुनः निर्मितानाम् समानानां उपवृक्षाणां बहूनां संख्यां दूरीकर्तुं शक्यते, तस्मात् गणनादक्षतायां सुधारः भवति (आच्छादिताः उपसमस्याः

कण्ठस्थं अन्वेषणम् : १.

केवलं एकवारं सर्वाणि अतिव्याप्त-उप-समस्यानां गणनां कर्तुं, प्रत्येकस्य उप-समस्यायाः समाधानं अभिलेखयितुम् एकं सरणी nem घोषयितुं, अन्वेषणप्रक्रियायाः समये च आच्छादित-उप-समस्यानां छंटनी करणीयम्

  1. यदा प्रथमवारं dp[i] गण्यते तदा अनन्तरं उपयोगाय nem[i] इत्यत्र अभिलेख्यते ।
  2. यदा पुनः dp[i] गण्यते तदा उपसमस्यानां पुनः पुनः गणनां न कर्तुं परिणामः प्रत्यक्षतया nem[i] इत्यत्र प्राप्यते ।

कोड उदाहरणम् : १.

  1. # python 代码示例
  2. def dfs(i : int, mem : list[int]) -> int :
  3. if i == 1 or i == 2 :
  4. return i
  5. if mem[i] != -1 :
  6. return mem[i]
  7. count = dfs(i - 1, mem) + dfs(i - 2, mem)
  8. # 记录dfs(i)
  9. mem[i] = count
  10. return count
  11. def climbing_stairs_dfs_mem(n : int) -> int :
  12. mem = [-1] * (n + 1)
  13. return dfs(n, mem)
  1. // c++ 代码示例
  2. int dfs(int i, vector<int> &mem)
  3. {
  4. if (i == 1 || i == 2)
  5. {
  6. return i ;
  7. }
  8. if (mem != -1)
  9. {
  10. return mem[i] ;
  11. }
  12. int count = dfs(i - 1, mem) + dfs(i - 2, mem) ;
  13. mem[i] = count ;
  14. return count ;
  15. }
  16. int climbingStairsDFSMem(int n)
  17. {
  18. vector<int> mem(n + 1, -1) ;
  19. return dfs(n, mem) ;
  20. }

मेमोाइजेशनस्य अनन्तरं सर्वाणि अतिव्याप्ताः उपसमस्याः एकवारमेव गण्यन्ते, तथा च समयजटिलता O(n) यावत् अनुकूलितं भवति ।

गतिशील प्रोग्रामिंग : १.

कण्ठस्थं अन्वेषणं "ऊर्ध्वतः अधः" पद्धतिः अस्ति वयं मूलसमस्यायाः (मूलनोड्) आरभामः तथा च पुनरावर्तनीयरूपेण बृहत्तराणि उपसमस्यानि लघु उपसमस्यासु विघटनं कुर्मः यावत् वयं लघुतमं ज्ञातां उपसमस्यां (पत्रनोड् ) न समाधानं कुर्मः । . तदनन्तरं उपसमस्यानां समाधानं मूलसमस्यायाः समाधानं निर्मातुं पश्चात्तापद्वारा स्तरं स्तरं एकत्रितं भवति ।

तस्य विपरीतम्, गतिशीलप्रोग्रामिंग् "तलतः उपरि" इति दृष्टिकोणः अस्ति: लघुतमस्य उपसमस्यायाः समाधानेन आरभ्य पुनरावर्तनीयरूपेण बृहत्तरानां उपसमस्यानां समाधानं निर्मातुं यावत् मूलसमस्यायाः समाधानं न प्राप्यते

यतः डायनामिक प्रोग्रामिंग् इत्यत्र बैकट्रैकिंग् प्रक्रिया न भवति, तस्मात् केवलं रिकर्सन् इत्यस्य उपयोगं विना लूप् इटरेशन इत्यस्य उपयोगेन एव कार्यान्वितुं आवश्यकम् ।

कोड उदाहरणम् : (गतिशील प्रोग्रामिंग, लघुतम उपसमस्यायाः आरम्भः)

  1. # python 代码示例
  2. def clibing_stairs_dp(n) :
  3. if n == 1 or n == 2 :
  4. return n
  5. dp = [0] * (n + 1)
  6. dp[1], dp[2] = 1, 2
  7. for i in range(3,n + 1) :
  8. dp[i] = dp[i-1] + dp[i- 2]
  9. return dp[n]
  1. // c++ 代码示例
  2. int climbingStairsDP(int n)
  3. {
  4. if (n == 1 || n == 2)
  5. {
  6. retunr n ;
  7. }
  8. vector<int> dp(n + 1, -1) ;
  9. dp[1] = 1 ;
  10. dp[2] = 2 ;
  11. for (int i = 3 ; i <= n ; i++)
  12. {
  13. dp[i] = dp[i - 1] + dp[i- 2] ;
  14. }
  15. return dp[n] ;
  16. }

निष्पादनप्रक्रिया (गतिशीलप्रोग्रामिंग) : १.

विश्लेषणम् : (गतिशील प्रोग्रामिंग) २.

बैकट्रैकिंग् एल्गोरिदम् इत्यस्य सदृशं डायनामिक प्रोग्रामिंग् अपि समस्यानिराकरणस्य विशिष्टं चरणं प्रतिनिधितुं "स्टेट्" इत्यस्य अवधारणायाः उपयोगं करोति । उदाहरणम् : सोपान-आरोहण-समस्यायाः स्थितिः वर्तमान-सोपानस्य i क्रमः इति परिभाषिता अस्ति ।

उपर्युक्तानां आधारेण वयं गतिशीलपदानां सामान्यपदानां सारांशं दातुं शक्नुमः :

  1. dp इति सरणी {dp table} इति उच्यते, dp[i] i अवस्थायाः अनुरूपस्य उपसमस्यायाः समाधानं प्रतिनिधियति
  2. न्यूनतम उपसमस्यायाः (प्रथमद्वितीयसोपानस्य) अनुरूपा अवस्था प्रारम्भिकावस्था इति कथ्यते
  3. पुनरावर्तनीयसूत्रं dp[i] = dp[i-1] + dp[i-2] इति अवस्थासमीकरणम् इति कथ्यते

अन्तरिक्ष अनुकूलनम् : १.

dp[i] केवलं dp[i-1] तथा dp[i-2] इत्यनेन सह सम्बद्धः अस्ति ।

सर्वेषां उपसमस्यानां समाधानं संग्रहीतुं सरणीयाः उपयोगस्य स्थाने अग्रे स्क्रॉल कर्तुं केवलं द्वौ चरौ आवश्यकौ भवतः ।

कोड उदाहरणम् : १.

  1. # python 代码示例
  2. def clibing_stairs_dp_comp(n) :
  3. if n == 1 or n == 2 :
  4. return n
  5. a, b = 1, 2
  6. for _ in range(3, n + 1) :
  7. a, b = b , a + b
  8. return b
  1. // c++ 代码示例
  2. int climbingStairsComp(int n)
  3. {
  4. if (n == 1 || n == 2)
  5. {
  6. return n ;
  7. }
  8. int a = 1 , b = 2 ;
  9. for (int i = 3 ; i <= n ; i++)
  10. {
  11. int temp = b ;
  12. b = a + b ;
  13. a = temp ;
  14. }
  15. return b ;
  16. }

आँकलन:

सरणी dp द्वारा आक्रान्तं स्थानं लोप्यते, स्थानजटिलता च O(n) तः O(1) पर्यन्तं न्यूनीकृता भवति ।

गतिशीलप्रोग्रामिंगसमस्यासु वर्तमानस्थितिः केवलं पूर्वस्थितीनां सीमितसङ्ख्यायाः सह सम्बद्धा भवति अस्मिन् समये वयं केवलं आवश्यकानि अवस्थानि धारयितुं शक्नुमः तथा च "आयामी न्यूनीकरणस्य" माध्यमेन स्मृतिस्थानं रक्षितुं शक्नुमः । . इयं स्पेस अनुकूलनप्रविधिः "rolling variables" अथवा "rolling arrays" इति कथ्यते ।