ഡൈനാമിക് പ്രോഗ്രാമിങ്

‌

അനുകൂലതമത (optimization) തത്ത്വത്തിലധിഷ്ഠിതമായ ഒരു പ്രോഗ്രാമിങ് രീതിയാണ് ഡൈനാമിക് പ്രോഗ്രാമിങ്. അമേരിക്കൻ ഗണിത ശാസ്ത്രജ്ഞൻ റിച്ചാർഡ് ബെൽമാനാണ് ഇതിന്റെ ഉപജ്ഞാതാവ്. ഏത് അവസ്ഥയിൽ നിന്നാരംഭിച്ചാലും പ്രോഗ്രാമിന്റെ ലോജിക് (യുക്തി) അനുകൂലതമ രീതിയിൽ പുരോഗമിക്കണമെന്നു നിഷ്കർഷിക്കുന്ന അൽഗോരിഥമാണ് ഇതിന്റേത്. അതായത് അവസാന നിർധാരണത്തിന് വഴിയൊരുക്കുന്ന എല്ലാ തീരുമാനങ്ങളും പ്രാരംഭിക അവസ്ഥയുമായി അനുകൂലതമമായിരിക്കണം. പരിഹരിക്കേണ്ട സങ്കീർണ പ്രശ്നത്തെ അനവധി മോഡ്യൂളുകളാക്കി വിഭജിച്ച് 'സ്ട്രക്ചേഡ്' രൂപത്തിലാക്കിയശേഷം ഓരോ മോഡ്യൂളിനേയും പടിപടിയായി നിർധരിക്കുന്നു. ഒരു മോഡ്യൂളിനെ നിർധരിക്കാൻ ഒന്നിലധികം രീതി ലഭ്യമാണെങ്കിലും തൊട്ടു മുമ്പത്തെ മോഡ്യൂളിന്റെ നിർധാരണവുമായി അനുകൂലതമമായതു മാത്രമേ സ്വീകരിക്കുകയുള്ളു. ആദ്യ മോഡ്യൂളിൽ തുടങ്ങി അസാനത്തെ മോഡ്യൂൾ വരെയോ അവസാനത്തേതിൽ നിന്ന് ആദ്യത്തേതു വരെയോ നിർധാരണം ആകാവുന്നതാണ്.

Figure 1. ഒപ്റ്റിമൽ സബ്‌സ്ട്രക്ചർ ഉപയോഗിച്ച് ഒരു ഗ്രാഫിലെ ഏറ്റവും ചെറിയ പാത കണ്ടെത്തുന്നു; ഒരു നേർരേഖ ഒരൊറ്റ അറ്റത്തെ സൂചിപ്പിക്കുന്നു; ഒരു തരംഗരേഖ അത് ബന്ധിപ്പിക്കുന്ന രണ്ട് ലംബങ്ങൾക്കിടയിലുള്ള ഏറ്റവും ചെറിയ പാതയെ സൂചിപ്പിക്കുന്നു (മറ്റ് പാതകൾക്കിടയിൽ, കാണിച്ചിട്ടില്ല, ഒരേ രണ്ട് ലംബങ്ങൾ പങ്കിടുന്നു); തുടക്കം മുതൽ ലക്ഷ്യത്തിലേക്കുള്ള ഏറ്റവും ചെറിയ പാതയാണ് ബോൾഡ് ലൈൻ.

നിർദിഷ്ട ഡേറ്റയുടെ എല്ലാ വിന്യാസങ്ങളും പടിപടിയായി കണ്ടുപിടിച്ച് അവയോരോന്നും ശരിയായ പ്രശ്നപരിഹാരത്തി നുള്ള നിർധാരണമാണോ എന്നുറപ്പുവരുത്തി മുന്നേറാവുന്ന പ്രോഗ്രാമിങ് രീതി ഇതു മാത്രമാണ്. എല്ലാ ഡേറ്റാ വിന്യാസങ്ങളേയും അവയുടെ പരിണത ഫലങ്ങളേയും ഒരു പട്ടികയുടെ രൂപത്തിൽ സംഭരിച്ചുവയ്ക്കുന്നു. അനവധി ഡേറ്റാ വിന്യാസങ്ങൾ ഉൾ പ്പെട്ടതാണ് പ്രശ്നമെങ്കിൽ ഡൈനാമിക് പ്രോഗ്രാമിങ് അൽഗോരിഥം പൂർത്തിയാക്കാൻ ധാരാളം കംപ്യൂട്ടർ മെമ്മറിയും സമയവും വേണ്ടിവരുന്നു. എന്നാൽ ഏതാനും സ്പഷ്ട വിന്യാസങ്ങൾ മാത്രം കൈകാര്യം ചെയ്യേണ്ടിവരുമ്പോൾ അവയുടെ ആവർത്തിച്ചുള്ള നിർധാരണം ഒഴിവാക്കാൻ ഏറ്റവും അനുയോജ്യമായ രീതിയും ഇതുതന്നെയാണ്.

ഉദാഹരണമായി, ഫീബനാച്ചി ശ്രേണിയിലെ n പദം (Fn) കണ്ടു പിടിക്കണമെന്നു കരുതുക. F0=0;f1=1;....Fn=Fn-1+Fn-2; എന്നീ നിബന്ധനകളാണിവിടെ പാലിക്കേണ്ടത്. ഇതിനായി പ്രതിവർത്തന രീതിയിലുള്ള ഒരു പ്രോഗ്രാമെഴുതിയാൽ പല മൂല്യങ്ങളേയും (Fi) വീണ്ടും വീണ്ടും കണക്കാക്കേണ്ടിവരും, മാത്രമല്ല, പ്രസ്തുത പ്രതിവർത്തന പ്രോഗ്രാമിന്റെ സമയ വർധന ചരഘാതാങ്കമായിരിക്കും (exponential). മറിച്ച്, കണ്ടുപിടിക്കുന്ന മുറയ്ക്ക് Fiയുടെ മൂല്യം പട്ടിക രൂപത്തിൽ ശേഖരിച്ചു വയ്ക്കുന്ന ഡൈനാമിക് രീതിയുടെ സമയ വർധന രേഖീയം മാത്രമായിരിക്കും.

അനുകൂലതമ ബൈനറി സേർച്ച് ട്രീ, അനുകൂലതമ മാട്രിക്സ് വിന്യാസങ്ങൾ, ആലേഖനത്തിലെ ബിന്ദു ദ്വയങ്ങൾ തമ്മിലുള്ള കുറഞ്ഞ അകലം, ബഹുതല ഡിസിഷൻ പ്രോസസ്സുകൾ (multi-stage decision processes), ഓപ്പറേഷൻ റിസേർച്ചിലെ പ്രശ്നങ്ങൾ എന്നിവയുടെ നിർധാരണത്തിനാണ് ഡൈനാമിക് പ്രോഗ്രാമിങ് കൂടുതലായി പ്രയോജനപ്പെടുത്താറുള്ളത്.

കടപ്പാട്: കേരള സർക്കാർ ഗ്നൂ സ്വതന്ത്ര പ്രസിദ്ധീകരണാനുമതി പ്രകാരം ഓൺലൈനിൽ പ്രസിദ്ധീകരിച്ച മലയാളം സർ‌വ്വവിജ്ഞാനകോശത്തിലെ ഡൈനാമിക്_പ്രോഗ്രാമിങ് എന്ന ലേഖനത്തിന്റെ ഉള്ളടക്കം ഈ ലേഖനത്തിൽ ഉപയോഗിക്കുന്നുണ്ട്. വിക്കിപീഡിയയിലേക്ക് പകർത്തിയതിന് ശേഷം പ്രസ്തുത ഉള്ളടക്കത്തിന് സാരമായ മാറ്റങ്ങൾ വന്നിട്ടുണ്ടാകാം.