နည္းလမ္းစဥ္ သရုပ္ခြဲပညာ မိတ္ဆက္

ကမၻာအရပ္ရပ္မွာရွိတဲ့ တကၠသိုလ္ေတြ ၊ သုေတသန ဌာနေတြနဲ႕ ဓာတ္ခြဲခန္းအသီးသီးမွာ နည္းလမ္းစဥ္ (Algorithm) ေတြကုိ ေလ့လာၿပီး အသစ္ေတြ႕ရွိခ်က္ေတြကို အေျပးအလႊား မွတ္ပံုတင္ (Patent လုပ္) ေနၾကပါတယ္ ။ နည္းလမ္းစဥ္ကုိ နည္းပညာ (Technology) တစ္ရပ္အျဖစ္ သတ္မွတ္လာၾကၿပီး Google, Miscosoft နဲ႕ Oracle စတဲ့ နည္းပညာ လုပ္ငန္းႀကီးေတြက နည္းလမ္းစဥ္ သုေတသနေတြမွာ ရင္းႏွီးျမဳပ္ႏွံမႈေတြ လုပ္လာတာေၾကာင့္ နည္းလမ္းစဥ္ သရုပ္ခြဲပညာ (Analysis of Algorithm) ရဲ႕ အေရးပါမႈဟာ က်ယ္ျပန္႕လာပါတယ္ ။ ဒီစာတမ္းငယ္မွာ နည္းလမ္းစဥ္ သရုပ္ခြဲပညာကုိ မိတ္ဆက္ေပးဖုိ႕ ေအာက္ပါပုစၧာေလးကုိ စဥ္းစားၾကည့္ပါမယ္ ။

ပုစၧာ ။ ။ အပင္တစ္ပင္ (Tree) တစ္ခုကုိ ေပးထားပါမယ္ ။ အဆစ္တစ္ခု (Node) တစ္ခုမွာ ကုိင္းခြဲ (Edge) ႏွစ္ခု ရွိပါမယ္ ။ ကပ္လ်က္ အဆစ္ ႏွစ္ခုရဲ႕ ဘယ္ကုိင္းခြဲနဲ႕ ညာကိုင္းခြဲက အဆစ္တစ္ခုထဲမွာ သြားဆံုပါမယ္ ။ အဆစ္တုိင္းမွာ တန္ဖုိးတစ္ခု တြဲလ်က္ရွိပါမယ္ ။ အျမစ္ (Root) ကေနၿပီး အရြက္ (Leaf) တစ္ခုကုိ သြားဖုိ႕ လမ္းတစ္ခုစီ (Path) ရဲ႕ တန္ဖုိးကုိ လမ္းတေလွ်ာက္က အဆစ္ေတြရဲ႕ တန္ဖုိးေတြေပါင္းလဒ္အျဖစ္ အဓိပၸါယ္သတ္မွတ္ပါမယ္ ။ အနက္ - သုိ႕မဟုတ္ အျမင့္ - (Depth) ၂ သုိ႕မဟုတ္ ၂ ထက္ပုိတဲ့ အပင္ေတြမွာ အရြက္ေပါင္းမ်ားစြာ ရွိမွာျဖစ္ၿပီး အရြက္တစ္ရြက္စီကုိ သြားဖုိ႕ လမ္းေၾကာင္းကလဲ ၁ ခု သုိ႕မဟုတ္ ၁ ခုထက္ ပုိမွာျဖစ္ပါတယ္ ။ ပံုကုိ ၾကည့္ပါ ။

ပံုမွာ အေပၚက ေျပာထားတဲ့ အပင္မ်ိဳး တစ္ပင္ကုိ ျပထားပါတယ္ ။ အဆစ္ေတြနဲ႕ အကုိင္းေတြကုိ စက္၀ုိင္းေတြနဲ႕ မ်ဥ္းေၾကာင္းေတြနဲ႕ ျပထားပါတယ္ ။ မ်ဥ္းထူနဲ႕ ျပထားတဲ့ လုိင္းေၾကာင္းက ဒီအပင္ရဲ႕ တန္ဖုိးအျမင့္ဆံုး လမ္းေၾကာင္းပါ ။ ေအာက္က ၂၅ ဆုိတာက အဲဒီ တန္ဖုိးအျမင့္ဆံုး လမ္းေၾကာင္းရဲ႕ တန္ဖုိးပါ ။ အဲဒီတန္ဖုိးကုိ တြက္ထုတ္တဲ့ ပုစၧာကုိ စဥ္းစားၾကည့္ရေအာင္ ။

ဒါမ်ိဳးပုစၧာအတြက္ဆုိရင္ လူေတာ္ေတာ္မ်ားမ်ားက ေလာဘႀကီးတဲ့ခ်ဥ္းးကပ္နည္း (Greedy approach) ကုိ စဥ္းစားမိတတ္ၾကပါတယ္ ။ ဒီပုစၧာမွာေတာ့ ေလာဘႀကီးတဲ့နည္းနဲ႕ ခ်ဥ္းကပ္လုိ႕ မရပါဘူး ။ ဘာလုိ႕လဲဆုိေတာ့ တတိယေျမာက္ အဆင့္မွာ ၇ တန္ဖုိးရွိတဲ့ အဆစ္ကေန ၃ နဲ႕ ၄ တန္ဖုိးရွိတဲ့ အဆစ္ေတြကုိ ေရြးရာမွာ ေလာဘႀကီးၿပီး တန္ဖိုး ၄ ရွိတဲ့ အဆစ္ကုိ ေရြးလုိက္ရင္ ေအာက္ဆံုး အဆင့္က တန္ဖုိး ၉ ရွိတဲ့ အဆစ္ကုိ လြတ္သြားမွာ ျဖစ္လုိ႕ပါပဲ ။ (ေလာဘႀကီးတဲ့ ခ်ဥ္းကပ္နည္းနဲ႕ စဥ္းစားလုိ႕ရ ၊ မရကုိ သက္ေသျပတာ ၊ စဥ္းစားလုိ႕ ရေအာင္ ႀကိဳးစားၾကတာဟာလဲ နည္းလမ္းစဥ္ သရုပ္ခြဲပညာရဲ႕ အကုိင္းအခက္ တစ္ခုပဲ ျဖစ္ပါတယ္ ။)

စာေရးသူ ၂၀၀၀ ခုႏွစ္တုန္းက ဒီပုစၧာကုိ ရွင္းဖုိ႕ နည္းလမ္းစဥ္ (Algorithm) တစ္ခုကုိ စဥ္းစားဖူးပါတယ္ ။ အပင္ကုိ လွဲ၊ အဆစ္ေတြကို အမွတ္စဥ္တပ္ၿပီး အမွတ္စဥ္ေရတြက္သလုိ လမ္းေၾကာင္းတစ္ခုခ်င္း အျပန္ျပန္၊ အလွန္လွန္ တြက္တဲ့ ပင္ပန္းတဲ့ (Exhaustive) နည္းနဲ႕ပါ ။ ေအာက္ပါပံုမွာ ၾကည့္ပါ ။

တြက္ပံုတြက္နည္းကေတာ့ လက္ရွိေပါင္းၾကည့္မဲ့ လမ္းေၾကာင္းကုိ တေနရာမွာ သိမ္းထားပါတယ္ ။ (၀ ကဘယ္ဘက္ ၁ ကညာဘက္ပါ ။ C/C++ နဲ႕ ဆုိရင္ေတာ့ Integer variable တစ္ခုထဲကုိ ၁ ေပါင္း Shift operation ေတြနဲ႕ ေရႊ႕ယူၿပီး လမ္းေၾကာင္းကို တြက္ထုတ္လုိ႕ရေပမဲ့ Pascal ရဲ႕ ကန္႕သတ္ခ်က္ေတြေၾကာင့္ တစ္ေၾကာင္း ၊ အဲဒီတုန္းက ငယ္ေသးတာက တစ္ေၾကာင္းမုိ႕လုိ႕ ဒီ Permutation with repetition ကုိ ကုိယ့္ဘာသာကုိယ္ ေရးပစ္လုိက္ပါတယ္ ။ )

ဒီအပင္ကုိ ႀတိဂံပံု ေမးထရစ္ မွာသိမ္းထားတယ္လုိ႕ ျမင္ရင္ ေပါင္းရမဲ့တန္ဖုိး (အဆစ္) ေတြရဲ႕ တည္ေနရာကုိ current_level တန္း၊ column_of_previous_level + path_value_of_current_level တုိင္ မွာ ရွာေတြ႕ႏုိင္ပါတယ္ ။ အဲဒီအဆစ္ေတြရဲ႕ တန္ဖုိးေတြ ေပါင္းလုိက္ရင္ လက္ရွိလမ္းေၾကာင္းရဲ႕ တန္ဖုိးကုိ ရပါၿပီ ။ ဒီတန္ဖုိးေတြကုိ အႀကီးဆံုးကိန္းရွာတဲ့ နည္းလမ္းစဥ္ထဲ ထည့္လုိက္ရင္ အႀကီးဆံုးလမ္းေၾကာင္းတန္ဖုိးကုိ ရၿပီေပါ့ ။ ဒါေပမဲ့ Borland’s Turbo Pascal 7.0 Compiler နဲ႕ Compile လုပ္ထားတဲ့ ပရုိဂရမ္ကုိ Pentium MMX 166 MHz, 32 MB RAM ပါတဲ့စက္နဲ႕ အနက္ ၃၀ ရွိတဲ့ အပင္ကုိ မနက္ ၁၀ နာရီကေန စတြက္တာ ညေန ၅ နာရီအထိ အေျဖမထြက္ႏုိင္ေသးပဲ တြက္ေကာင္းတုန္း ျဖစ္ေနပါတယ္ ။ (အခု Intel Core 2 Duo E6550 2.33GHz, 2 x 2MB L2 Cache, 1066 MHz FSB, 4 x 1GB DDR2 667MHz RAM နဲ႕ တြက္ခုိင္းၾကည့္တာ ၃၂ စကၠန္႕ၾကာျမင့္ပါတယ္ ။ )

ဘာမွားသြားလဲ အေျဖရွာမၾကည့္ခင္မွာ ကၽြန္ေတာ့္ဆရာေပးတဲ့ နည္းလမ္းစဥ္က ၁ မိနစ္အတြင္း တြက္လုိ႕ၿပီးတယ္ဆုိတာကုိ ျဖည့္ေျပာခ်င္ပါတယ္ ။ သူသံုးတဲ့နည္းလမ္းကေတာ့ Recursive with table lookup လုိ႕ေခၚတဲ့ ေပါင္းစပ္ အစီအစဥ္ဆြဲနည္း (Dynamic programming) ျဖစ္ပါတယ္ ။ (ေပါင္းစပ္အစီအစဥ္ဆြဲနည္းဟာလဲ ေလာဘႀကီးတဲ့ ခ်ဥ္းကပ္နည္းလုိပဲ အေရးပါတဲ့ နည္းလမ္းတစ္ခုပါ ။ ) သူက အေျဖကုိ ဒီလုိ ပံုစံထုတ္ပါတယ္ ။ အရြက္မဟုတ္တဲ့ အဆစ္တစ္ခု (အဆစ္ ဆ) ကေန အရြက္ေတြဆီသြားတဲ့ တန္ဖုိးအျမင့္ဆံုး လမ္းေၾကာင္းဟာ အဲဒီအဆစ္ရဲ႕ ဘယ္ဘက္ ညာဘက္ အဆစ္ (ဆ ရဲ႕ ဘယ္ဘက္ အဆစ္ သုိ႕မဟုတ္ ညာဘက္အဆစ္) ေတြကေန အရြက္ေတြဆီသြားတဲ့ တန္ဖုိးအျမင့္ဆံုး လမ္းေၾကာင္း ၂ ခုထဲက ပုိမ်ားတဲ့ လမ္းေၾကာင္းရဲ႕ တန္ဖုိးကုိ အဲဒီ အဆစ္ (ဆ) ရဲ႕ တန္ဖုိး ေပါင္းထည့္ထားတာျဖစ္ၿပီး အရြက္ေတြရဲ႕ အျမင့္ဆံုးလမ္းေၾကာင္း တန္ဖုိးကေတာ့ သူတုိ႕ကုိယ္တုိင္ရဲ႕ တန္ဖုိးပဲ ျဖစ္ပါတယ္ ။

ဟုိး … စာဖတ္သူ … ဟုိး … ဒီအတုိင္း Recursive နဲ႕ ေရးလုိက္တဲ့ အစီအစဥ္ (program) ဟာလဲ အေပၚက ပင္ပန္းတဲ့နည္းလုိပဲ နာရီေပါင္းမ်ားစြာ ၾကာျမင့္သြားႏုိင္ပါတယ္ ။ ဘာလုိ႕လဲဆုိေတာ့ အနက္ ၂ မွာရွိတဲ့ အဆစ္ ၀ နဲ႕ အဆစ္ ၁ တုိ႕ရဲ႕ အေျဖဟာ သူတုိ႕ ၂ ခုရဲ႕ ဘံုဆက္ခံသူ အနက္ ၃ ၊ အဆစ္ ၁ ရဲ႕ အေျဖေပၚမူတည္ေနလုိ႕ ျဖစ္ပါတယ္ ။ တကယ္လုိ႕သာ ရုိးရုိး Recursive နဲ႕ ေရးလုိက္မယ္ဆုိရင္ အဲဒီအေျဖကုိ ၂ ခါျပန္တြက္ရမွာ ျဖစ္ပါတယ္ ။ အဲဒါေၾကာင့္မုိ႕လုိ႕ အဲဒီ အပင္နဲ႕ အရြယ္အစားတူ အပင္တစ္ပင္ထပ္စုိက္ … အဲ အဲ တည္ေဆာက္ၿပီး တြက္ၿပီးသား ရလဒ္ေတြကုိ သိမ္းထားပါမယ္ ။ ေနာက္တခါ တြက္ဖုိ႕ လုိအပ္လာတုိင္းမွာ အဲဒီရလဒ္ေတြကုိ ျပန္ၾကည့္ၿပီး တြက္ၿပီးသားဆုိရင္ ဒီတုိင္းယူသံုးလုိက္မွ အဆင္ေျပပါလိမ့္မယ္ ။

ေပါင္းစပ္ အစီအစဥ္ဆြဲျခင္း စစ္စစ္ကေတာ့ ေအာက္ဆံုးအဆင့္ကေန အထက္ကုိ ျဖည္းျဖည္းခ်င္း အေျဖတြက္လာတဲ့ နည္းျဖစ္ၿပီး ခုနက နည္းထက္ နည္းနည္းပုိျမန္းပါတယ္ ။ ဘာလုိ႕လဲဆုိေတာ့ မွီခ်က္ေတြကုိ ေခၚတဲ့အခါ (Function calls) ၀န္ပုိ (Overhead) နည္းနည္း ရွိတတ္လုိ႕ ျဖစ္ပါတယ္ ။ (အခု Intel Core 2 Duo E6550 2.33GHz, 2 x 2MB L2 Cache, 1066 MHz FSB, 4 x 1GB DDR2 667MHz RAM နဲ႕ တြက္ၾကည့္တာ ၂ နည္းစလံုး ၁ စကၠန္႕ေအာက္သာၾကာျမင့္ပါတယ္ ။ )

နည္းလမ္းစဥ္ သရုပ္ခြဲပညာမွာ အေရးပါတဲ့ အစိတ္အပုိင္း ၃ ခုရွိပါတယ္ ။ ပထမတစ္ခုက နည္းလမ္းစဥ္ရဲ႕ မွန္ကန္မႈ (Correctness of the Algorithm) ျဖစ္ပါတယ္ ။ အေပၚက ဥပမာမွာ နည္းလမ္းစဥ္အားလံုး မွန္ကန္ၾကပါတယ္ ။ ဒုတိယတစ္ခုက အခ်ိန္ၾကာျမင့္မႈ (Time Complexity) ျဖစ္ၿပီး ေနာက္ဆံုးတစ္ခုက သိမ္းဆည္းမႈ လုိအပ္ခ်က္ (Space Complexity) ျဖစ္ပါတယ္ ။ ပင္ပန္းတဲ့နည္းက အခ်ိန္ပုိၾကာေပမဲ့ သိမ္းဆည္းမႈ လုိအပ္ခ်က္ နိမ့္ပါတယ္ ။ အေျဖေတြကုိ ေပါင္းစပ္တဲ့နည္းက အခ်ိန္မၾကာေပမဲ့ သိမ္းဆည္းမႈ လုိအပ္ခ်က္ ျမင့္တယ္လုိ႕ ေကာက္ခ်က္ခ်ႏုိင္ပါတယ္ ။ ပုစၧာတစ္ရပ္အတြက္ နည္းလမ္းစဥ္အမ်ိဳးမ်ိဳး ရွိေနတတ္တာမုိ႕ နည္းလမ္းစဥ္ သရုပ္ခြဲပညာကုိ ဒီလုိေလ့လာမႈမ်ိဳးလုပ္ဖုိ႕အတြက္ အသံုးျပဳႏုိင္ပါတယ္လုိ႕ တင္ျပရင္း မိတ္ဆက္စာတမ္းငယ္ကုိ နိဂံုးခ်ဳပ္အပ္ပါတယ္ ။ ယခုလက္ရွိမွာေတာ့ ကြန္ပ်ဴတာသိပၸံမွ ျပႆနာမ်ား စာတမ္းကုိ ေရႊပြဲလာမ်ား ဖတ္ရႈဖုိ႕ ေရးသားေနပါတယ္ခင္ဗ်ာ ။

စာေရးသူေရးစမ္းထားတဲ့ အစီအစဥ္ေတြကုိ ဒီေနရာမွာ ရယူႏုိင္ပါတယ္။