បញ្ហា (The Problem)៖ និក្ខេបបទនេះដោះស្រាយពីភាពមិនមានប្រសិទ្ធភាពក្នុងការគណនានៃវិធីសាស្ត្រ Markov Chain Monte Carlo (MCMC) ស្តង់ដារ នៅពេលត្រូវដោះស្រាយបញ្ហាកំណត់ដ៏ធំ និងស្មុគស្មាញដូចជាបញ្ហា Traveling Salesman Problem (TSP)។ ការស្វែងរកដំណោះស្រាយដោយប្រើជម្រើសចៃដន្យតែងតែទាមទារពេលវេលា និងចំនួនជុំ (iterations) ច្រើនជ្រុល។
វិធីសាស្ត្រ (The Methodology)៖ ការសិក្សានេះបានបង្កើត និងសាកល្បងក្បួនដោះស្រាយ Metropolis-Hastings ដែលបានកែប្រែដោយប្រើប្រាស់ការចែកចាយសំណើផ្តល់ព័ត៌មានមូលដ្ឋាន (Locally-informed proposals) ដើម្បីធ្វើឱ្យប្រសើរឡើងនូវការជ្រើសរើសបេក្ខជនក្នុងដំណើរការស្វែងរកដំណោះស្រាយល្អបំផុត។
លទ្ធផលសំខាន់ៗ (The Verdict)៖
| វិធីសាស្ត្រ (Method) | គុណសម្បត្តិ (Pros) | គុណវិបត្តិ (Cons) | លទ្ធផលគន្លឹះ (Key Result) |
|---|---|---|---|
| Random Neighbours (RN) in Metropolis-Hastings ការជ្រើសរើសអ្នកជិតខាងដោយចៃដន្យ (RN) |
មានភាពសាមញ្ញក្នុងការអនុវត្ត និងមានល្បឿនលឿនខ្លាំងក្នុងការគណនាក្នុងមួយជំហាន ព្រោះមិនទាមទារការគណនាស្មុគស្មាញច្រើន។ | ទាមទារចំនួនជុំ (iterations) ច្រើនខ្លាំងណាស់ ដើម្បីឈានទៅរកដំណោះស្រាយល្អបំផុត ដែលធ្វើឱ្យខាតពេលវេលាក្នុងការស្វែងរកជម្រើសល្អ។ | ត្រូវការរហូតដល់ ២០០០០ ជំហានទើបអាចទទួលបានចម្ងាយសរុបប្រហាក់ប្រហែលនឹងការប្រើវិធី LIP ប៉ុន្តែចំណាយពេលគណនាសរុបតិចបំផុត (ឧ. ១.៥ វិនាទីសម្រាប់ទិន្នន័យ dsj1000)។ |
| Locally-Informed Proposals (LIP) ការផ្តល់សំណើដោយផ្អែកលើព័ត៌មានមូលដ្ឋាន (LIP) |
កាត់បន្ថយចំនួនជុំយ៉ាងច្រើនសន្ធឹកសន្ធាប់ក្នុងការស្វែងរកចម្លើយ ដោយជ្រើសរើសអ្នកជិតខាងដែលមានសក្តានុពលខ្ពស់មុនគេ។ | មានភាពស្មុគស្មាញក្នុងការគណនាខ្ពស់ក្នុងមួយជំហានៗ ដែលធ្វើឱ្យការអនុវត្តជាក់ស្តែងប្រើពេលវេលាយូរខ្លាំង ប្រសិនបើមិនមានការបំបែកការគណនា។ | អាចឈានដល់ដំណោះស្រាយល្អបំផុតដោយប្រើត្រឹមតែ ២៧ ទៅ ២៥៦ ជំហានប៉ុណ្ណោះ អាស្រ័យលើទំហំទិន្នន័យ តែចំណាយពេលរហូតដល់ជាង ៨០ វិនាទី ឬដល់រាប់ម៉ោងសម្រាប់ទិន្នន័យធំៗ។ |
ការចំណាយលើធនធាន (Resource Cost)៖ ការអនុវត្តក្បួនដោះស្រាយនេះទាមទារធនធានកុំព្យូទ័រជាមូលដ្ឋានសម្រាប់ការសាកល្បងខ្នាតតូច ប៉ុន្តែត្រូវការថាមពលគណនាខ្ពស់ ឬការធ្វើទំនើបកម្មកូដកម្រិតខ្ពស់សម្រាប់ទិន្នន័យជាក់ស្តែងធំៗ។
ការសិក្សានេះប្រើប្រាស់ទិន្នន័យគំរូស្តង់ដារពី TSPLIB ដែលតំណាងឱ្យទីក្រុងនៅប្រទេសអាល្លឺម៉ង់ សហរដ្ឋអាមេរិក និងទិន្នន័យបង្កើតដោយចៃដន្យ។ ទោះបីជាវាមិនមែនជាទិន្នន័យនៃទីតាំងក្នុងប្រទេសកម្ពុជាផ្ទាល់ក៏ដោយ លក្ខណៈនៃបញ្ហា Traveling Salesman Problem (TSP) គឺមានលក្ខណៈសកល ហើយការសន្និដ្ឋានពីល្បឿននិងចំនួនជុំរបស់ក្បួនដោះស្រាយនេះ អាចយកមកអនុវត្តដោយផ្ទាល់លើបណ្តាញផ្លូវនៅក្នុងប្រទេសកម្ពុជាបាន។
ក្បួនដោះស្រាយនេះមានសារៈសំខាន់ខ្លាំងណាស់ក្នុងការជួយដោះស្រាយបញ្ហាដឹកជញ្ជូន និងបណ្តាញចែកចាយ ដែលកំពុងមានតម្រូវការខ្ពស់ក្នុងប្រទេសកម្ពុជា។
ជារួម បច្ចេកទេសនេះគឺជាមូលដ្ឋានគ្រឹះដ៏មានសក្តានុពលក្នុងការបង្កើនប្រសិទ្ធភាពប្រតិបត្តិការដែលមានការពាក់ព័ន្ធនឹងបណ្តាញផ្លូវ និងទីតាំងច្រើនក្នុងប្រទេសកម្ពុជា ប្រសិនបើត្រូវបានគួបផ្សំជាមួយបច្ចេកវិទ្យាគណនាស្របគ្នា (Concurrent Computing) ដើម្បីដោះស្រាយបញ្ហាយឺតយ៉ាវ។
ដើម្បីអនុវត្តតាមការសិក្សានេះ និស្សិតគួរអនុវត្តតាមជំហានខាងក្រោម៖
| ពាក្យបច្ចេកទេស | ការពន្យល់ជាខេមរភាសា (Khmer Explanation) | និយមន័យសាមញ្ញ (Simple Definition) |
|---|---|---|
| Markov Chain Monte Carlo (MCMC) | ជាក្រុមនៃក្បួនដោះស្រាយតាមបែបស្ថិតិដែលប្រើប្រាស់ដំណើរការម៉ាកូវ (Markov Chain) ដើម្បីបង្កើតគំរូចៃដន្យសម្រាប់ប៉ាន់ស្មានលទ្ធផលចេញពីបំណែងចែកប្រូបាប៊ីលីតេដ៏ស្មុគស្មាញ ដែលមិនអាចគណនាដោយផ្ទាល់បាន។ | ដូចជាការដើររុករកក្នុងព្រៃដ៏ធំមួយដោយបោះកាក់រាល់ជំហាន ដើម្បីស្វែងរកកន្លែងដែលមានផ្លែឈើច្រើនជាងគេ ដោយមិនចាំបាច់ដើរសព្វគ្រប់កន្លែងទាំងអស់នោះទេ។ |
| Metropolis-Hastings algorithm | ជាក្បួនដោះស្រាយចម្បងមួយនៅក្នុងវិធីសាស្ត្រ MCMC ដែលសម្រេចថាតើត្រូវទទួលយក ឬបដិសេធ "អ្នកជិតខាង" (ជម្រើសថ្មី) ដោយផ្អែកលើការប្រៀបធៀបប្រូបាប៊ីលីតេរវាងជម្រើសចាស់ និងជម្រើសថ្មី ដើម្បីធានាថាដំណើរការនេះឈានទៅរកលទ្ធផលល្អបំផុត។ | ដូចជាការសម្រេចចិត្តប្តូរទីតាំងតូបលក់អីវ៉ាន់នៅផ្សារ៖ បើតូបថ្មីមានភ្ញៀវច្រើនជាង យើងដូរទៅភ្លាម តែបើតូបថ្មីមានភ្ញៀវតិចជាង យើងអាចនៅកន្លែងចាស់ ឬប្តូរទៅល្បងមើលសិនក្នុងឱកាសណាមួយ។ |
| Traveling Salesman Problem (TSP) | ជាបញ្ហាបែបគណិតវិទ្យា និងវិទ្យាសាស្ត្រកុំព្យូទ័រ (ប្រភេទ NP-hard) ដែលទាមទារការស្វែងរកផ្លូវធ្វើដំណើរដែលខ្លីបំផុត កាត់តាមទីតាំងទាំងអស់ដែលបានកំណត់តែម្តងគត់ រួចត្រលប់មកចំណុចដើមវិញ។ | ដូចជាអ្នកដឹកជញ្ជូនរៀបចំផែនការជិះម៉ូតូផ្ញើអីវ៉ាន់ឱ្យអតិថិជន១០នាក់នៅតាមផ្ទះផ្សេងៗគ្នា ដោយធ្វើយ៉ាងណាឱ្យចំណាយសាំង និងពេលវេលាតិចបំផុតមុនពេលត្រលប់មកឃ្លាំងវិញ។ |
| Locally-informed proposals (LIP) | ជាការកែច្នៃរបៀបជ្រើសរើសជម្រើសថ្មីនៅក្នុងក្បួន MCMC ដោយមិនជ្រើសរើសដោយចៃដន្យទាំងស្រុងនោះទេ តែប្រើប្រាស់ព័ត៌មាននៃទម្ងន់ឬចម្ងាយរបស់អ្នកជិតខាង ដើម្បីផ្តល់អាទិភាពដល់ជម្រើសណាដែលមានសក្តានុពលខ្ពស់ជាងគេមុន។ | ជំនួសឱ្យការបិទភ្នែកដើររើសផ្លូវដោយចៃដន្យ វាប្រៀបដូចជាការប្រើពិលបញ្ចាំងមើលផ្លូវនៅក្បែរៗខ្លួនជាមុនសិន រួចទើបសម្រេចចិត្តដើរទៅរកផ្លូវណាដែលមើលទៅស្រឡះល្អជាងគេ។ |
| Simulated annealing | ជាបច្ចេកទេសបន្ធូរបន្ថយ (Optimization) ដែលអនុញ្ញាតឱ្យក្បួនដោះស្រាយអាចទទួលយកជម្រើសអាក្រក់នៅដំណាក់កាលដំបូងៗ (សីតុណ្ហភាពខ្ពស់) ដើម្បីចៀសវាងការជាប់គាំងនៅត្រឹមដំណោះស្រាយល្អត្រឹមតំបន់តូចមួយ (Local Minima) រួចសឹមបង្រួមការស្វែងរកដើម្បីយកតែជម្រើសល្អនៅពេលក្រោយ (សីតុណ្ហភាពទាប)។ | ដូចជាការសិតលោហៈធាតុក្តៅ៖ ដំបូងគេប្រើកម្តៅខ្លាំងដើម្បីឱ្យវារលាយអាចពត់ពេនបានស្រួលទៅគ្រប់ទម្រង់ បន្ទាប់មកទើបគេបន្ថយកម្តៅបន្តិចម្តងៗដើម្បីឱ្យវាកកិតរឹងមាំទៅជារូបរាងដ៏ល្អឥតខ្ចោះ។ |
| NP-hard problem | ជាចំណាត់ថ្នាក់នៃបញ្ហាក្នុងទ្រឹស្តីកុំព្យូទ័រ ដែលការរកដំណោះស្រាយល្អដាច់ខាត ទាមទារពេលវេលាគណនាកើនឡើងយ៉ាងគំហុក (Exponential time) នៅពេលទំហំទិន្នន័យកាន់តែធំ ដែលធ្វើឱ្យកុំព្យូទ័រធម្មតាមិនអាចដោះស្រាយវាបានក្នុងពេលជាក់ស្តែង។ | ដូចជាការទាយលេខសម្ងាត់ (Password) របស់ទូដែក ដែលបើអ្នកថែមតែលេខមួយខ្ទង់ទៀត ចំនួនជម្រើសក្នុងការសាកល្បងនឹងកើនឡើងយ៉ាងច្រើនរហូតកុំព្យូទ័រប្រើពេលរាប់ពាន់ឆ្នាំទើបរកឃើញ។ |
| Detailed balance | ជាលក្ខខណ្ឌមួយនៅក្នុងទ្រឹស្តីម៉ាកូវ ដែលធានាថាអត្រានៃការផ្លាស់ប្តូរពីស្ថានភាព A ទៅស្ថានភាព B គឺស្មើគ្នានឹងអត្រានៃការផ្លាស់ប្តូរត្រលប់ពីស្ថានភាព B មកស្ថានភាព A វិញ ដែលជួយឱ្យប្រព័ន្ធរក្សាបាននូវលំនឹងចែកចាយ (Stationary distribution)។ | ដូចជាចំនួនមនុស្សដើរចេញពីបន្ទប់ A ចូលបន្ទប់ B ស្មើគ្នាបេះបិទនឹងចំនួនមនុស្សដើរចេញពីបន្ទប់ B ចូលបន្ទប់ A ក្នុងពេលតែមួយ ដែលធ្វើឱ្យចំនួនមនុស្សសរុបក្នុងបន្ទប់នីមួយៗនៅថេរដដែល។ |
| Ergodicity | ជាលក្ខណៈនៃដំណើរការម៉ាកូវ ដែលរាល់ស្ថានភាពទាំងអស់ (States) អាចត្រូវបានឈានទៅដល់បានដោយមិនខ្វល់ថាចាប់ផ្តើមពីទីតាំងណាមួយនោះទេ ហើយការអនុវត្តរយៈពេលយូរនឹងអាចគ្របដណ្តប់ប្រព័ន្ធទាំងមូលដោយមិនជាប់គាំង។ | ដូចជាការលាយទឹកស៊ីរ៉ូក្នុងកែវទឹក៖ បើអ្នកកូរវាយូរគ្រប់គ្រាន់ ម៉ូលេគុលស៊ីរ៉ូនឹងសាយភាយទៅដល់គ្រប់កន្លែងនៃទឹកនោះ ដោយមិននៅដុំកកកុញតែមួយកន្លែងឡើយ។ |
អត្ថបទដែលបានបោះពុម្ពនៅលើ KhmerResearch ដែលទាក់ទងនឹងប្រធានបទនេះ៖
ប្រធានបទ និងសំណួរស្រាវជ្រាវដែលទាក់ទងនឹងឯកសារនេះ ដែលអ្នកអាចស្វែងរកបន្ថែម៖
