ေရႊပြဲလာတုိ႕၏ အားေပးမႈ

၂၀၀၉ ခုႏွစ္ ၾသဂုတ္လ ၁ ရက္ေန႕မွစ၍ လက္မွတ္ေစာင္ေရေပါင္း ေစာင္ တိတိ ေရာင္းခ်ခဲ့ရၿပီး ျဖစ္ပါသည္။

အမာခံ ပရိသတ္တုိ႔အတြက္ ...

Sunday, October 11, 2009

ဥာဏ္စမ္းပေဟဠိမ်ားကုိ ကြန္ပ်ဴတာ အသံုးျပဳ ေျဖရွင္းျခင္း

သခ်ၤာဥာဏ္အေပၚတြင္ အေျခခံေသာ ဥာဏ္စမ္းပေဟဠိ၊ စကားအသြားအလာႏွင့္ ဘာသာစကားလွည့္ကြက္အေပၚတြင္ အေျခခံေသာ ဥာဏ္စမ္းပေဟဠိႏွင့္ အၾကားအျမင္ ဗဟုသုတ အေပၚတြင္ အေျခခံသည့္ ဥာဏ္စမ္းပေဟဠိစသည္ျဖင့္ ဥာဏ္စမ္းပေဟဠိ အမ်ိဳးမ်ိဳး ရွိရာ အခ်ိဳ႕ေသာ ပေဟဠိမ်ားသည္ ထည့္သြင္း စဥ္းစားရမည့္ ျဖစ္ႏုိင္ေသာ အေျဖ အေရအတြက္ အတုိင္းအဆမရွိ မ်ားျပားမႈအေပၚတြင္ အေျခခံေလသည္။ ေရွးက လူအားျဖင့္သာ ဥာဏ္စမ္းပေဟဠိမ်ားကို အေျဖထုတ္ခဲ့ၾကရာတြင္ ျဖစ္ႏုိင္ေသာ အေျဖ အလြန္မ်ားျပားေသာ ပေဟဠိမ်ားမွာ အေျဖကုိ ႀကိဳတင္ မသိသူ ေျဖဆုိသူတုိ႕ လက္ေျမွာက္အရႈံးေပးရသည္သာ မ်ားေသာ္လည္း ယေန႕ကြန္ပ်ဴတာေခတ္တြင္မူ ၄င္းတုိ႕ကုိ အလြယ္တကူ အေျဖထုတ္ႏုိင္ၿပီ ျဖစ္သည္။ ယခုေဆာင္းပါးတြင္ ၄င္းပေဟဠိ ၂ ပုဒ္ကုိ ကြန္ပ်ဴတာ အသံုးျပဳ ေျဖရွင္းပံုကို ေဖာ္ျပမည္ျဖစ္သည္။

ပထမ ပုစၧာမွာ ဤသုိ႕ျဖစ္သည္။ လယ္သမားတစ္ေယာက္သည္ သူ၏ၿခံတြင္ ေမြးျမဴရန္အတြက္ ႏြား၊ ၀က္ႏွင့္ ၾကက္ စုစုေပါင္း အေကာင္ ၁၀၀ ၀ယ္လုိသည္။ ပုိက္ဆံလဲ ၁၀၀ က်ပ္သာရွိသည္။ ၃ မ်ိဳးလံုးလဲ ေမြးလုိေသးသည္။ ႏြားတစ္ေကာင္ ၁၀ က်ပ္၊ ၀က္တစ္ေကာင္ ၃ က်ပ္ႏွင့္ ၾကက္တစ္ေကာင္ ၅ မူး (၀.၅၀ က်ပ္) ျဖစ္ေသာ္ အေကာင္ ၁၀၀ ရေအာင္ ေငြ ၁၀၀ ႏွင့္ ဘယ္လုိ ၀ယ္မည္နည္း။ တနည္းအားျဖင့္ မသိကိန္း ၃ လံုးပါ၊ တၿပိဳင္နက္ ညီမွ်ျခင္း ၂ ေၾကာင္း ပုစၧာျဖစ္သည္။ သီ၀ရီအရ အေျဖ မရွိ၊ တစ္ခုတည္းသာ၊ အမ်ားအျပား ရွိႏုိင္ေသာ ပုစၧာအမ်ိဳးအစားလဲ ျဖစ္သည္။ တၿပိဳင္နက္ ညီမွ်ျခင္း အမ်ားအျပားပါ တၿပိဳင္နက္ ညီမွ်ျခင္း စနစ္ (System of Linear Equations) တစ္ခုကုိ မက္ထရစ္ ညီမွ်ျခင္း တစ္ေၾကာင္းျဖင့္ ေဖၚျပႏုိင္ရာ လွန္မက္ထရစ္ေယာင္ (Pseudo Inverse) ကုိအသံုးျပဳၿပီး ျဖစ္ႏုိင္သည့္ အေျဖမ်ားကုိ အလြယ္တကူ တြက္ထုတ္ႏုိင္ပါသည္။

၄င္း သခ်ၤာနည္း၏ အားနည္းခ်က္မွာ ၄င္းနည္းစနစ္သည္ ကိန္းစစ္ ေျမွာက္ေဖာ္ကိန္း (Real Number Coefficients) မ်ားအတြက္ နည္းစနစ္ ျဖစ္ေနသျဖင့္ ကိန္းစစ္ အေျဖတြဲ အမ်ားအျပား ထြက္လာႏုိင္ျခင္းပင္ ျဖစ္သည္။ (Matlab မရွိသျဖင့္ စာေရးသူ မစမ္းၾကည့္ပါ။) ေမြးရန္ ၀ယ္ေသာ ႏြား၊ ၀က္၊ ၾကက္တုိ႕ကုိ တ၀က္၊ တစိတ္ စသျဖင့္ ၀ယ္မရႏိုင္ပါ (တ၀က္၀က္ရင္ ေသကုန္မွာေပါ့)။ တနည္းအားျဖင့္ အေျဖသည္ အေပါင္း ကိန္းျပည့္ ၃ ခု ျဖစ္ရမည္။ ေပါင္းလွ်င္ ၁၀၀ ရေသာ အေပါင္းကိန္းျပည့္ မ်ားစြာရွိရာ ကြန္ပ်ဴတာ အကူအညီမယူေသာ သခ်ၤာသီးသန္႕သမားတုိ႕အတြက္ ခက္ခဲေသာ ပုစၧာျဖစ္သည္။ ကြန္ပ်ဴတာ ပညာရွင္ တစ္ဦးသည္ ဤပုစၧာကို မ်က္ကန္းနည္း (Brute Force Method) အသံုးျပဳျခင္းျဖင့္ အလြယ္တကူ ေျဖရွင္းႏုိင္သည္။ ႏြား အေရအတြက္ အမ်ိဳးမ်ိဳး၊ ၀က္အေရအတြက္ အမ်ိဳးမ်ိဳးႏွင့္ ၾကက္အေရအတြက္ အမ်ိဳးမ်ိဳးတုိ႕အတြက္ အစီအစဥ္ငယ္တစ္ခုကုိ လွ်င္ျမန္စြာေရးသားၿပီး ၄င္းတို႕ ေပါင္းလဒ္၊ ၄င္းတုိ႕၏ က်သင့္ေငြ တုိ႕ကို တြက္ခ်က္ကာ ႏွစ္ခုလံုး ၁၀၀ ျဖစ္ေသာ အေျဖကုိ ထုတ္ေပးရံုသာျဖစ္သည္။ (အေျဖမွာ ႏြား ၅၊ ၀က္ ၁၊ ၾကက္ ၉၄ ျဖစ္သည္။)

မွတ္ခ်က္ ။ ။ ယခု ပုစၧာသာလွ်င္ လြယ္ကူျခင္း ျဖစ္သည္။ ကိန္းျပည့္ မသိကိန္း အမ်ားအျပားႏွင့္ ညီမွ်ျခင္း အေရအတြက္ အနည္းငယ္ (ညီမွ်ျခင္း အေရအတြက္က မသိကိန္းအေရအတြက္ထက္ ပိုနည္းေနေသာ) ပုစၧာပံုစံကြဲတစ္ခုကုိ စစ္ဆင္ေရး သုေတသန (Operation Research) ဘာသာရပ္တြင္ Integer Linear Programming (ILP) အမည္ႏွင့္ေတြ႕ရၿပီး ခက္ခဲေသာ ပုစၧာျဖစ္သည္။

ဒုတိယ ပုစၧာတြင္မူကား မ်က္ကန္းနည္း အသံုးျပဳရန္ အဆင္မေျပေတာ့ေပ။ ပုစၧာမွာ ဤသို႕ျဖစ္သည္။ ၁ မွ ၉ အထိ ဂဏန္း ၉ လံုး (တစ္လံုးကုိ တစ္ႀကိမ္စီသာပါ၀င္ေသာ) သန္းရာဂဏန္းရွိ ကိန္းတစ္လံုးသည္ ၉ ႏွင့္ စားလုိ႕ ျပတ္သည္။ အဆုိပါ ကိန္းမွ ခုဂဏန္းကုိ ဖယ္ထုတ္လုိက္ေသာ ဂဏန္း ၈ လံုးပါ ကိန္း (၁၀ ႏွင့္စားလွ်င္ ရေသာ ရလဒ္) သည္ ၈ ႏွင့္ စားလုိ႕ ျပတ္သည္။ တဖန္ ထုိကိန္းမွ ခုဂဏန္းကုိ ဖယ္ထုတ္ပါက က်န္ေသာ ကိန္းသည္ ၇ ႏွင့္ စားလုိ႕ ျပတ္သည္။ ေနာက္ဆံုး ၁ လံုးသာ က်န္သည္အထိ ဤနည္းအတုိင္း တစ္လံုးဖယ္တုိင္း က်န္ေသာ ဂဏန္းအေရအတြက္ႏွင့္ စားလုိ႕ ျပတ္ရသည္။ တနည္းအားျဖင့္ ဘယ္ဘက္ဆံုး x လံုးကုိ x ႏွင့္စား၍ ျပတ္သည္။ ထုိကိန္းကို ရွာပါ။ မ်က္ကန္းနည္းႏွင့္ တြက္လွ်င္ သန္းတစ္ရာ (၁၀၀ ၀၀၀ ၀၀၀) မွ ကုိးရာ ကုိးဆယ့္ ကုိးသန္း ကုိးသိန္း ကုိးေသာင္း ကုိးေထာင္ ကုိးရာ ကုိးဆယ့္ ကုိး (၉၉၉ ၉၉၉ ၉၉၉) အထိ ကိန္းေပါင္း သန္း ၉၀၀ နီးပါးကုိ ၁ မွ ၉ အထိ ကိန္းမ်ားျဖင့္ စားလုိ႕ ျပတ္မျပတ္ တြက္ထုတ္ (ဂဏန္းမ်ား ထပ္ေနမေန စစ္) ရမည္ ျဖစ္သျဖင့္ သိပ္အဆင္မေျပေသာ နည္းျဖစ္သည္။ (၁ မွ ၉ အထိ စားျပတ္မျပတ္ တစ္ခါတြက္လွ်င္ ၁ စကၠန္႕၏ တစ္သန္းပံု တစ္ပံုသာ ၾကာသည္ထား … အနည္းဆံုး စကၠန္႕ ၉၀၀ = ၁၅ မိနစ္မွ် ၾကာသြားႏုိင္သည္။ မစမ္းၾကည့္ပါ။)

အမွန္မွာ ၄င္းသည္ ၁ မွ ၉ အထိ ဂဏန္း ၉ လံုးကို ၉ ေနရာတြင္ စီခုိင္းေသာ (စီၿပီးလွ်င္ စစ္ခုိင္းေသာ) အစီ ပုစၧာ (Permutation Problem) သာျဖစ္သည္။ အစီ ပံုေသနည္းအရ ျဖစ္ႏုိင္သည့္ ကိန္းေပါင္း ၉ x ၈ x … x ၁ = ၃၆၂၈၈၀ သာ ရွိသည္။ အကယ္၍ ကုန္က်စရိတ္နည္းေသာ အစီ နည္းလမ္းစဥ္သာ ရွိခဲ့လွ်င္ ပြဲျပတ္ၿပီ ျဖစ္သည္။ (ကံဆုိးသည္မွာ အထူးတည္ေဆာက္ထားေသာ ကြန္ပ်ဴတာမ်ားမွ အပ မရွိ။) သုိ႕ရာတြင္ ၁၅ မိနစ္ထက္ေတာ့ ျမန္မည္မွာ ေသခ်ာပါသည္။ (မစမ္းၾကည့္ပါ။) ၂ နည္းစလံုးသည္ လူအားျဖင့္ တြက္ထုတ္ရန္ မျဖစ္ႏုိင္သည္မွာကား ေသခ်ာေပသည္။

အဆုိပါ ပုစၧာကုိ ျပင္ပ သခ်ၤာဗဟုသုတမ်ားျဖင့္ အားျဖည့္ကာ ပုိမုိေကာင္းမြန္ေသာ အစီအစဥ္ တစ္ရပ္ကုိ ဆြဲသားႏုိင္ပါသည္။ အသံုးျပဳေသာ သခ်ၤာနည္းစနစ္မွာ ကိန္းတစ္လံုးကုိ ၁ မွ ၉ အထိ ဂဏန္းမ်ားႏွင့္ စားလွ်င္ ရမည့္ စားၾကြင္းကုိ ရွာေသာ နည္းလမ္းမ်ားျဖစ္သည္။ အစီအစဥ္ မဆြဲမီ ျဖစ္ႏုိင္ေသာ ကိန္းမ်ားကို ေအာက္ပါအတုိင္း ဆင္ျခင္သည္။ (x ေနရာ = အေျဖကိန္းကုိ ဘယ္ဘက္မွ ေရတြက္လွ်င္ x ေနရာ)

  • ကိန္းတစ္လံုးကုိ ၉ ႏွင့္ စားျပတ္၊ မျပတ္ သိရန္အတြက္ အဆုိပါကိန္းတြင္ ပါ၀င္ေသာ ဂဏန္းမ်ား၏ မူလတန္ဖုိးမ်ားေပါင္းလဒ္ကုိ ၉ ျဖင့္ စားၾကည့္ႏုိင္သည္ (သုိ႕မဟုတ္ ေပါင္းေနရင္း ၉ ျပည့္လွ်င္ ဖယ္ဖယ္ထားခဲ့ႏုိင္သည္။) ပါ၀င္ရမည့္ ဂဏန္းမ်ားမွာ ၁ မွ ၉ အထိ ဂဏန္း ၉ လံုးျဖစ္သည္။ ၁ + ၈ = ၂ + ၇ = ၃ + ၆ = ၄+ ၅ = ၉ ျဖစ္ရာ … ၁ မွ ၉ အထိ ဂဏန္းအားလံုး (တစ္လံုးကုိ တစ္ႀကိမ္စီသာ ပါ၀င္ေသာ) ကိန္းသည္ ၉ ႏွင့္ အလိုအေလ်ာက္ စားလုိ႕ ျပတ္သည္။ ထည့္သြင္းစဥ္းစားရန္မလုိ။ ၁ မွ ၉ အထိ ဂဏန္း ၉ လံုးကုိ ေရွ႕ ၈ ေနရာတြင္သာ ေနရာခ် စမ္းသပ္ၾကည့္ၿပီး ေျပလည္ပါက က်န္ခဲ့ေသာ တစ္လံုးျဖင့္ ၉ ေနရာကို အလြယ္တကူ ျဖည့္ႏုိင္သည္။
  • ကိန္းတစ္လံုးကုိ ၂ (၄ ႏွင့္ ၈) တုိ႕ႏွင့္ စားျပတ္၊ မျပတ္ သိႏုိင္ရန္အတြက္ ညာဘက္ဆံုး ၁ လံုး (၂ လံုးႏွင့္ ၃ လံုး) သည္ ၂ (၄ ႏွင့္ ၈) ျဖင့္ စား၍ ျပတ္ရသည္။ ထုိ႕ေၾကာင့္ ၂ ေနရာတြင္ စံုကိန္းတစ္လံုး (၃၄ ေနရာတြင္ ၄ ႏွင့္စားျပတ္ေသာ ဆယ္ဂဏန္း တစ္လံုး၊ ၆၇၈ ေနရာတြင္ ၈ ႏွင့္ စားျပတ္ေသာ ရာဂဏန္း တစ္လံုး) ကုိ ျဖည့္သြင္းရမည္။
  • ကိန္းတစ္လံုးကုိ ၃ ႏွင့္ စားျပတ္၊ မျပတ္ သိႏုိင္ရန္အတြက္ အဆုိပါကိန္းတြင္ ပါ၀င္ေသာ ဂဏန္းမ်ား၏ မူလတန္ဖုိးမ်ား ေပါင္းလဒ္ကုိ ၃ ျဖင့္ စားၾကည့္ႏိုင္သည္။ ၄င္းကုိ အေျခခံ၍ ၂ ေနရာရွိ ဂဏန္းႏွင့္ ၃ ေနရာရွိဂဏန္းတုိ႕ကို အေျခခံ၍ ၁ ေနရာရွိ ဂဏန္းကို တြက္ခ်က္ႏုိင္သည္။၂ ေနရာတြင္ စံုကိန္းတစ္လံုး ေသခ်ာေပါက္ရွိၿပီး ၃၄ ေနရာတြင္ ၄ ႏွင့္ စားျပတ္ေသာ ဆယ္ဂဏန္း တစ္လံုး ေသခ်ာေပါက္ ရွိမည္ျဖစ္သျဖင့္ ၁၂၃၄ ေနရာရွိ ဂဏန္းမ်ား ျဖစ္ႏုိင္ေျခသည္ ၉ x ၈ x ၇ x ၆ =  ၃၀၂၄ မွ ၃ × သုညမဟုတ္ေသာ ၁၀ ေအာက္ စံုကိန္း (၂၊ ၄၊ ၆၊ ၈) အေရအတြက္ x ၄ ႏွင့္စားျပတ္ေသာ ဆယ္ဂဏန္း အေရအတြက္ (၃ × ၄ x ၂၂ = ၂၆၄) သုိ႕က်ဆင္းသြားမည္။ (စာေရးသူ စမ္းသပ္ရာတြင္ ဤနည္းကို မသံုးပဲ ကိန္း ၉၉၀ လံုးကို ၃ ႏွင့္စားျပတ္၊ မျပတ္ စစ္ထားပါသည္။)
  • ကိန္းတစ္လံုးကုိ ၅ ႏွင့္ စားျပတ္ရန္ အဆုိပါကိန္းသည္ ၀ (သုည) သုိ႕မဟုတ္ ၅ ႏွင့္ ဆံုးရမည္ျဖစ္သည္။ ၀ (သုည) ကုိ ပုစၧာအရ သံုးခြင့္မရွိသျဖင့္ ၅ ေနရာတြင္ ရွိမည့္ ဂဏန္းမွာ ၅ သာလွ်င္ ျဖစ္သည္။

အထက္ေဖာ္ျပပါ ထုိးထြင္းသိမ်ားျဖင့္ အစီအစဥ္တစ္ရပ္ကုိ အျမန္ ဆြဲသား တြက္ခ်က္ခဲ့ရာ ဂဏန္းတြဲ အေရအတြက္ ၂၄၁၉၂၀ ကုိသာ စိစစ္ခဲ့ၿပီး (၃၆၂၈၈၀ ႏွင့္ႏိႈင္းစာလွ်င္ ၃ ပံု ၂ ပံုခန္႕) ၆ ေနရာ၊ ၇ ေနရာတုိ႕တြင္ ၀ (သုည) ပါ၀င္ႏုိင္ၿပီး ဂဏန္း တစ္မ်ိဳးစီကုိ တစ္ႀကိမ္ထက္ ပိုမုိပါ၀င္ႏုိင္ေသာ္လည္း ဘယ္ဘက္ဆံုး x လံုးကုိ x ႏွင့္စား၍ ျပတ္ေသာ ကိန္း ၄၆၃ လံုးကုိ ရရွိခဲ့သည္။ ၄င္းတုိ႕ကုိ ပါ၀င္ေသာ ဂဏန္းမ်ား ၀ (သုည) ျဖစ္၊ မျဖစ္ႏွင့္ ထပ္၊ မထပ္ စစ္ေဆး စစ္ထုတ္ျခင္းျဖင့္ အေျဖကို ရေလေတာ့သည္။ (အေျဖမွာ ၃၈၁ ၆၅၄ ၇၂၉ ျဖစ္သည္။)

ေရႊပြဲလာအေပါင္း ျဖစ္ႏုိင္ေျခ ေထာင္ေသာင္းခ်ီသည့္ ပုစၧာမ်ားကို အလြယ္တကူ အေျဖထုတ္ႏုိင္ၾကပါေစ။

စာေရးသူ စမ္းသပ္ ေရးသားထားေသာ အစီအစဥ္မ်ားကုိ ရယူရန္

No comments: