This site is not complete. The work to converting the volumes of സര്‍വ്വവിജ്ഞാനകോശം is on progress. Please bear with us
Please contact webmastersiep@yahoo.com for any queries regarding this website.
Reading Problems? see Enabling Malayalam
ഡൈനാമിക് പ്രോഗ്രാമിങ്
സര്‍വ്വവിജ്ഞാനകോശം സംരംഭത്തില്‍ നിന്ന്
(New page: = ഡൈനാമിക് പ്രോഗ്രാമിങ് = ഉ്യിമാശര ുൃീഴൃമാാശിഴ അനുകൂലതമത (ീുശോശ്വമശീ...) |
|||
| വരി 1: | വരി 1: | ||
= ഡൈനാമിക് പ്രോഗ്രാമിങ് = | = ഡൈനാമിക് പ്രോഗ്രാമിങ് = | ||
| + | Dynamic programming | ||
| - | + | അനുകൂലതമത (optimization) തത്ത്വത്തിലധിഷ്ഠിതമായ ഒരു പ്രോഗ്രാമിങ് രീതി. അമേരിക്കന്‍ ഗണിത ശാസ്ത്രജ്ഞന്‍ റിച്ചാര്‍ഡ് ബെല്‍മാനാണ് ഇതിന്റെ ഉപജ്ഞാതാവ്. ഏത് അവസ്ഥയില്‍ നിന്നാരംഭിച്ചാലും പ്രോഗ്രാമിന്റെ ലോജിക് (യുക്തി) അനുകൂലതമ രീതിയില്‍ പുരോഗമിക്കണമെന്നു നിഷ്കര്‍ഷിക്കുന്ന അല്‍ഗോരിഥമാണ് ഇതിന്റേത്. അതായത് അവസാന നിര്‍ധാരണത്തിന് വഴിയൊരുക്കുന്ന എല്ലാ തീരുമാനങ്ങളും പ്രാരംഭിക അവസ്ഥയുമായി അനുകൂലതമമായിരിക്കണം. പരിഹരിക്കേണ്ട സങ്കീര്‍ണ പ്രശ്നത്തെ അനവധി മോഡ്യൂളുകളാക്കി വിഭജിച്ച് 'സ്ട്രക്ചേഡ്' രൂപത്തിലാക്കിയശേഷം ഓരോ മോഡ്യൂളിനേയും പടിപടിയായി നിര്‍ധരിക്കുന്നു. ഒരു മോഡ്യൂളിനെ നിര്‍ധരിക്കാന്‍ ഒന്നിലധികം രീതി ലഭ്യമാണെങ്കിലും തൊട്ടു മുമ്പത്തെ മോഡ്യൂളിന്റെ നിര്‍ധാരണവുമായി അനുകൂലതമമായതു മാത്രമേ സ്വീകരിക്കുകയുള്ളു. ആദ്യ മോഡ്യൂളില്‍ തുടങ്ങി അസാനത്തെ മോഡ്യൂള്‍ വരെയോ അവസാനത്തേതില്‍ നിന്ന് ആദ്യത്തേതു വരെയോ നിര്‍ധാരണം ആകാവുന്നതാണ്. | |
| - | + | നിര്‍ദിഷ്ട ഡേറ്റയുടെ എല്ലാ വിന്യാസങ്ങളും പടിപടിയായി കണ്ടുപിടിച്ച് അവയോരോന്നും ശരിയായ പ്രശ്നപരിഹാരത്തി നുള്ള നിര്‍ധാരണമാണോ എന്നുറപ്പുവരുത്തി മുന്നേറാവുന്ന പ്രോഗ്രാമിങ് രീതി ഇതു മാത്രമാണ്. എല്ലാ ഡേറ്റാ വിന്യാസങ്ങളേയും അവയുടെ പരിണത ഫലങ്ങളേയും ഒരു പട്ടികയുടെ രൂപത്തില്‍ സംഭരിച്ചുവയ്ക്കുന്നു. അനവധി ഡേറ്റാ വിന്യാസങ്ങള്‍ ഉള്‍ പ്പെട്ടതാണ് പ്രശ്നമെങ്കില്‍ ഡൈനാമിക് പ്രോഗ്രാമിങ് അല്‍ഗോരിഥം പൂര്‍ത്തിയാക്കാന്‍ ധാരാളം കംപ്യൂട്ടര്‍ മെമ്മറിയും സമയവും വേണ്ടിവരുന്നു. എന്നാല്‍ ഏതാനും സ്പഷ്ട വിന്യാസങ്ങള്‍ മാത്രം കൈകാര്യം ചെയ്യേണ്ടിവരുമ്പോള്‍ അവയുടെ ആവര്‍ത്തിച്ചുള്ള നിര്‍ധാരണം ഒഴിവാക്കാന്‍ ഏറ്റവും അനുയോജ്യമായ രീതിയും ഇതുതന്നെയാണ്. | |
| + | ഉദാഹരണമായി, ഫീബനാച്ചി ശ്രേണിയിലെ n പദം (F<sub>n</sub>) കണ്ടു പിടിക്കണമെന്നു കരുതുക. F<sub>0</sub>=0;f<sub>1</sub>=1;....F<sub>n</sub>=F<sub>n-1</sub>+F<sub>n-2</sub>; എന്നീ നിബന്ധനകളാണിവിടെ പാലിക്കേണ്ടത്. ഇതിനായി പ്രതിവര്‍ത്തന രീതിയിലുള്ള ഒരു പ്രോഗ്രാമെഴുതിയാല്‍ പല മൂല്യങ്ങളേയും (F<sub>i</sub>) വീണ്ടും വീണ്ടും കണക്കാക്കേണ്ടിവരും, മാത്രമല്ല, പ്രസ്തുത പ്രതിവര്‍ത്തന പ്രോഗ്രാമിന്റെ സമയ വര്‍ധന ചരഘാതാങ്കമായിരിക്കും (exponential). മറിച്ച്, കണ്ടുപിടിക്കുന്ന മുറയ്ക്ക് F<sub>i</sub>യുടെ മൂല്യം പട്ടിക രൂപത്തില്‍ ശേഖരിച്ചു വയ്ക്കുന്ന ഡൈനാമിക് രീതിയുടെ സമയ വര്‍ധന രേഖീയം മാത്രമായിരിക്കും. | ||
| - | + | അനുകൂലതമ ബൈനറി സേര്‍ച്ച് ട്രീ, അനുകൂലതമ മാട്രിക്സ് വിന്യാസങ്ങള്‍, ആലേഖനത്തിലെ ബിന്ദു ദ്വയങ്ങള്‍ തമ്മിലുള്ള കുറഞ്ഞ അകലം, ബഹുതല ഡിസിഷന്‍ പ്രോസസ്സുകള്‍ (multi-stage decision processes), ഓപ്പറേഷന്‍ റിസേര്‍ച്ചിലെ പ്രശ്നങ്ങള്‍ എന്നിവയുടെ നിര്‍ധാരണത്തിനാണ് ഡൈനാമിക് പ്രോഗ്രാമിങ് കൂടുതലായി പ്രയോജനപ്പെടുത്താറുള്ളത്. | |
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | അനുകൂലതമ ബൈനറി സേര്‍ച്ച് ട്രീ, അനുകൂലതമ മാട്രിക്സ് വിന്യാസങ്ങള്‍, ആലേഖനത്തിലെ ബിന്ദു ദ്വയങ്ങള്‍ തമ്മിലുള്ള കുറഞ്ഞ അകലം, ബഹുതല ഡിസിഷന്‍ പ്രോസസ്സുകള്‍ ( | + | |
Current revision as of 10:39, 11 ജൂണ്‍ 2008
ഡൈനാമിക് പ്രോഗ്രാമിങ്
Dynamic programming
അനുകൂലതമത (optimization) തത്ത്വത്തിലധിഷ്ഠിതമായ ഒരു പ്രോഗ്രാമിങ് രീതി. അമേരിക്കന്‍ ഗണിത ശാസ്ത്രജ്ഞന്‍ റിച്ചാര്‍ഡ് ബെല്‍മാനാണ് ഇതിന്റെ ഉപജ്ഞാതാവ്. ഏത് അവസ്ഥയില്‍ നിന്നാരംഭിച്ചാലും പ്രോഗ്രാമിന്റെ ലോജിക് (യുക്തി) അനുകൂലതമ രീതിയില്‍ പുരോഗമിക്കണമെന്നു നിഷ്കര്‍ഷിക്കുന്ന അല്‍ഗോരിഥമാണ് ഇതിന്റേത്. അതായത് അവസാന നിര്‍ധാരണത്തിന് വഴിയൊരുക്കുന്ന എല്ലാ തീരുമാനങ്ങളും പ്രാരംഭിക അവസ്ഥയുമായി അനുകൂലതമമായിരിക്കണം. പരിഹരിക്കേണ്ട സങ്കീര്‍ണ പ്രശ്നത്തെ അനവധി മോഡ്യൂളുകളാക്കി വിഭജിച്ച് 'സ്ട്രക്ചേഡ്' രൂപത്തിലാക്കിയശേഷം ഓരോ മോഡ്യൂളിനേയും പടിപടിയായി നിര്‍ധരിക്കുന്നു. ഒരു മോഡ്യൂളിനെ നിര്‍ധരിക്കാന്‍ ഒന്നിലധികം രീതി ലഭ്യമാണെങ്കിലും തൊട്ടു മുമ്പത്തെ മോഡ്യൂളിന്റെ നിര്‍ധാരണവുമായി അനുകൂലതമമായതു മാത്രമേ സ്വീകരിക്കുകയുള്ളു. ആദ്യ മോഡ്യൂളില്‍ തുടങ്ങി അസാനത്തെ മോഡ്യൂള്‍ വരെയോ അവസാനത്തേതില്‍ നിന്ന് ആദ്യത്തേതു വരെയോ നിര്‍ധാരണം ആകാവുന്നതാണ്.
നിര്‍ദിഷ്ട ഡേറ്റയുടെ എല്ലാ വിന്യാസങ്ങളും പടിപടിയായി കണ്ടുപിടിച്ച് അവയോരോന്നും ശരിയായ പ്രശ്നപരിഹാരത്തി നുള്ള നിര്‍ധാരണമാണോ എന്നുറപ്പുവരുത്തി മുന്നേറാവുന്ന പ്രോഗ്രാമിങ് രീതി ഇതു മാത്രമാണ്. എല്ലാ ഡേറ്റാ വിന്യാസങ്ങളേയും അവയുടെ പരിണത ഫലങ്ങളേയും ഒരു പട്ടികയുടെ രൂപത്തില്‍ സംഭരിച്ചുവയ്ക്കുന്നു. അനവധി ഡേറ്റാ വിന്യാസങ്ങള്‍ ഉള്‍ പ്പെട്ടതാണ് പ്രശ്നമെങ്കില്‍ ഡൈനാമിക് പ്രോഗ്രാമിങ് അല്‍ഗോരിഥം പൂര്‍ത്തിയാക്കാന്‍ ധാരാളം കംപ്യൂട്ടര്‍ മെമ്മറിയും സമയവും വേണ്ടിവരുന്നു. എന്നാല്‍ ഏതാനും സ്പഷ്ട വിന്യാസങ്ങള്‍ മാത്രം കൈകാര്യം ചെയ്യേണ്ടിവരുമ്പോള്‍ അവയുടെ ആവര്‍ത്തിച്ചുള്ള നിര്‍ധാരണം ഒഴിവാക്കാന്‍ ഏറ്റവും അനുയോജ്യമായ രീതിയും ഇതുതന്നെയാണ്.
ഉദാഹരണമായി, ഫീബനാച്ചി ശ്രേണിയിലെ n പദം (Fn) കണ്ടു പിടിക്കണമെന്നു കരുതുക. F0=0;f1=1;....Fn=Fn-1+Fn-2; എന്നീ നിബന്ധനകളാണിവിടെ പാലിക്കേണ്ടത്. ഇതിനായി പ്രതിവര്‍ത്തന രീതിയിലുള്ള ഒരു പ്രോഗ്രാമെഴുതിയാല്‍ പല മൂല്യങ്ങളേയും (Fi) വീണ്ടും വീണ്ടും കണക്കാക്കേണ്ടിവരും, മാത്രമല്ല, പ്രസ്തുത പ്രതിവര്‍ത്തന പ്രോഗ്രാമിന്റെ സമയ വര്‍ധന ചരഘാതാങ്കമായിരിക്കും (exponential). മറിച്ച്, കണ്ടുപിടിക്കുന്ന മുറയ്ക്ക് Fiയുടെ മൂല്യം പട്ടിക രൂപത്തില്‍ ശേഖരിച്ചു വയ്ക്കുന്ന ഡൈനാമിക് രീതിയുടെ സമയ വര്‍ധന രേഖീയം മാത്രമായിരിക്കും.
അനുകൂലതമ ബൈനറി സേര്‍ച്ച് ട്രീ, അനുകൂലതമ മാട്രിക്സ് വിന്യാസങ്ങള്‍, ആലേഖനത്തിലെ ബിന്ദു ദ്വയങ്ങള്‍ തമ്മിലുള്ള കുറഞ്ഞ അകലം, ബഹുതല ഡിസിഷന്‍ പ്രോസസ്സുകള്‍ (multi-stage decision processes), ഓപ്പറേഷന്‍ റിസേര്‍ച്ചിലെ പ്രശ്നങ്ങള്‍ എന്നിവയുടെ നിര്‍ധാരണത്തിനാണ് ഡൈനാമിക് പ്രോഗ്രാമിങ് കൂടുതലായി പ്രയോജനപ്പെടുത്താറുള്ളത്.
