បញ្ហា (The Problem)៖ ការបែងចែកប្រាក់ចំណេញ ឬការចំណាយនៅក្នុងហ្គេមសហប្រតិបត្តិការ (Cooperative games) ជាពិសេសនៅក្នុងហ្គេម Multidimensional Integer Knapsack Games (MIKG) ជួបប្រទះនឹងបញ្ហាស្មុគស្មាញ និងចំណាយពេលយូរយ៉ាងខ្លាំងក្នុងការគណនាតម្លៃ Shapley (Shapley value) ដោយសារតែរចនាសម្ព័ន្ធដ៏ស្មុគស្មាញនៃកម្មវិធីចំនួនគត់។
វិធីសាស្ត្រ (The Methodology)៖ ការសិក្សានេះស្នើឡើងនូវអភិក្រមពីជគណិត (Algebraic approach) ផ្អែកលើមូលដ្ឋាន Gröbner រួមផ្សំជាមួយបច្ចេកទេសយកគំរូ (Sampling) ដើម្បីដោះស្រាយ និងប៉ាន់ស្មានតម្លៃ Shapley សម្រាប់ហ្គេមខ្នាតធំ។
លទ្ធផលសំខាន់ៗ (The Verdict)៖
| វិធីសាស្ត្រ (Method) | គុណសម្បត្តិ (Pros) | គុណវិបត្តិ (Cons) | លទ្ធផលគន្លឹះ (Key Result) |
|---|---|---|---|
| Algebraic Gröbner Approach (Exact & Sampling) អភិក្រមពីជគណិតផ្អែកលើមូលដ្ឋាន Gröbner (ការគណនាពិតប្រាកដ និងការយកគំរូ) |
មានល្បឿនលឿនជាងវិធីសាស្ត្រធម្មតាដល់ទៅ ៥ ដងសម្រាប់ការគណនាហ្គេមខ្នាតធំ។ កាត់បន្ថយពេលវេលាគណនាយ៉ាងច្រើនតាមរយៈការកាត់បន្ថយចំណាយអថេរ (Variable cost) ក្នុងការដោះស្រាយកម្មវិធីចំនួនគត់។ | ទាមទារពេលវេលាដំបូង (Fixed cost) ដើម្បីគណនាមូលដ្ឋាន Gröbner។ ទំហំនៃមូលដ្ឋាន Gröbner អាចកើនឡើងយ៉ាងឆាប់រហ័ស និងប្រើប្រាស់អង្គចងចាំច្រើនសម្រាប់បញ្ហាដែលមានទំហំវិមាត្រធំៗ។ | ប្រើពេលត្រឹមតែ ១៦.៣៩ វិនាទី (ធៀបនឹង CPLEX ១០៤.២៧ វិនាទី) សម្រាប់ឧទាហរណ៍តូច និងរក្សាកំហុស MAPE ឱ្យនៅក្រោម ១% សម្រាប់ហ្គេមដែលមានអ្នកលេង ១០០ នាក់ ក្នុងរយៈពេលកំណត់ ១ ម៉ោង។ |
| CPLEX Solver (Baseline) កម្មវិធីដោះស្រាយ CPLEX (ក្បួនដោះស្រាយគោល) |
ជាកម្មវិធីស្តង់ដារឧស្សាហកម្មដែលមានភាពរឹងមាំ និងមានស្ថេរភាពខ្ពស់សម្រាប់ការដោះស្រាយបញ្ហាកម្មវិធីចំនួនគត់ (Integer Programming)។ | ចំណាយពេលយូរខ្លាំង (Exponential time) នៅពេលចំនួនអ្នកលេងកើនឡើង ព្រោះវាត្រូវដោះស្រាយបញ្ហាបង្កើនប្រសិទ្ធភាព (Optimization) ឡើងវិញម្តងមួយៗសម្រាប់រាល់ការផ្លាស់ប្តូរតម្លៃ។ | ដំណើរការយឺតជាងអភិក្រម Gröbner រហូតដល់ ៥ ដង ក្នុងការប៉ាន់ស្មានតម្លៃ Shapley សម្រាប់ហ្គេមខ្នាតធំ (អ្នកលេងចាប់ពី ២០ ដល់ ១០០ នាក់)។ |
ការចំណាយលើធនធាន (Resource Cost)៖ ការអនុវត្តក្បួនដោះស្រាយនេះមិនទាមទារកុំព្យូទ័រដែលមានសមត្ថភាពខ្ពស់ខ្លាំង (Supercomputer) នោះទេ ប៉ុន្តែតម្រូវឱ្យមានការប្រើប្រាស់កម្មវិធីកុំព្យូទ័រជំនាញ ដើម្បីទាញយកលទ្ធផលប្រសើរបំផុត។
ការសិក្សានេះពឹងផ្អែកទាំងស្រុងទៅលើទិន្នន័យដែលបង្កើតឡើងដោយកុំព្យូទ័រ (Randomly generated instances) ជាជាងការប្រើប្រាស់ទិន្នន័យជាក់ស្តែងពីក្រុមហ៊ុន ឬស្ថាប័នណាមួយ។ សម្រាប់បរិបទប្រទេសកម្ពុជា ការខ្វះខាតការធ្វើតេស្តលើទិន្នន័យជាក់ស្តែង (Real-world data) គឺតម្រូវឱ្យមានការផ្ទៀងផ្ទាត់បន្ថែម (Validation step) មុននឹងយកទៅអនុវត្តលើគម្រោងពិតប្រាកដដូចជាការបែងចែកថវិកាជាតិ ឬការគ្រប់គ្រងខ្សែសង្វាក់ផ្គត់ផ្គង់ ដើម្បីធានាថាវាឆ្លើយតបនឹងស្ថានភាពជាក់ស្តែង។
វិធីសាស្ត្រនេះមានសក្តានុពលខ្ពស់សម្រាប់ស្ថាប័ននៅកម្ពុជា ក្នុងការធ្វើឱ្យប្រសើរឡើងនូវការសម្រេចចិត្តពហុភាគី និងការបែងចែកធនធានប្រកបដោយតម្លាភាព។
ជារួម ការអនុវត្តអភិក្រមពីជគណិតនេះ នឹងជួយដោះស្រាយបញ្ហានៃការចែកចាយផលប្រយោជន៍ និងការគ្រប់គ្រងធនធានរួមនៅកម្ពុជាឱ្យកាន់តែមានភាពយុត្តិធម៌ និងមានប្រសិទ្ធភាពខ្ពស់។
ដើម្បីអនុវត្តតាមការសិក្សានេះ និស្សិតគួរអនុវត្តតាមជំហានខាងក្រោម៖
| ពាក្យបច្ចេកទេស | ការពន្យល់ជាខេមរភាសា (Khmer Explanation) | និយមន័យសាមញ្ញ (Simple Definition) |
|---|---|---|
| Shapley value | វិធីសាស្ត្រមួយក្នុងទ្រឹស្តីហ្គេមសម្រាប់បែងចែកប្រាក់ចំណេញ ឬការចំណាយដល់អ្នកចូលរួមម្នាក់ៗ ដោយផ្អែកលើទំហំនៃការរួមចំណែកនិងឥទ្ធិពលជាក់ស្តែងរបស់ពួកគេនៅក្នុងក្រុម។ | ដូចជាការបែងចែកនំខេកយុត្តិធម៌ឱ្យមិត្តភក្តិ ទៅតាមចំនួនលុយ និងកម្លាំងពលកម្មដែលពួកគេម្នាក់ៗបានចូលរួមក្នុងការធ្វើនំនោះ។ |
| Multidimensional Integer Knapsack Games | ជាប្រភេទហ្គេមសហប្រតិបត្តិការដែលក្រុមនីមួយៗត្រូវសម្រេចចិត្តជ្រើសរើសទំនិញចំនួនគត់ដាក់ក្នុងកាបូប ដោយមានកម្រិតទម្ងន់ឬធនធានច្រើនប្រភេទ (ពហុវិមាត្រ) ដើម្បីទទួលបានតម្លៃខ្ពស់បំផុត។ | ដូចជាក្រុមមនុស្សដែលរួមលុយនិងទំហំកាបូបគ្នា ដើម្បីទៅទិញឥវ៉ាន់លក់រាយដែលផ្តល់ចំណេញច្រើនបំផុត ដោយប្រយ័ត្នមិនឱ្យលើសទម្ងន់ដែលពួកគេអាចយួរបាន។ |
| Gröbner bases | ជាឧបករណ៍ ឬសញ្ញាណគណិតវិទ្យា (ពីជគណិត) ដែលត្រូវបានប្រើប្រាស់សម្រាប់បំប្លែងប្រព័ន្ធសមីការស្មុគស្មាញ ឱ្យទៅជាទម្រង់មួយដែលងាយស្រួលរកចម្លើយ ជាពិសេសក្នុងការដោះស្រាយបញ្ហាកម្មវិធីចំនួនគត់។ | ដូចជាការប្រើប្រាស់ពុម្ពឬសោរមេ ដែលអាចជួយដោះសោររាល់បញ្ហាគណិតវិទ្យាដែលជាប់គន្លឹះស្មុគស្មាញបានយ៉ាងងាយស្រួល។ |
| Characteristic function | អនុគមន៍គណិតវិទ្យាដែលកំណត់ពីតម្លៃសរុប ឬផលចំណេញអតិបរមាដែលក្រុមអ្នកលេងណាមួយ (Coalition) អាចទទួលបាននៅពេលពួកគេសហការគ្នា។ | ដូចជាតារាងតម្លៃប្រាក់ខែដែលបញ្ជាក់ថា តើអ្នកនឹងទទួលបានប្រាក់ចំណូលប៉ុន្មានបើអ្នកចាប់ដៃគូជាមួយមិត្ត A ធៀបនឹងការចាប់ដៃគូជាមួយមិត្ត B។ |
| Integer Linear Program | ជាទម្រង់នៃបញ្ហាបង្កើនប្រសិទ្ធភាពដែលគោលបំណង និងលក្ខខណ្ឌកំណត់ត្រូវបានតំណាងដោយសមីការលីនេអ៊ែរ ហើយចម្លើយទាមទារឱ្យមានតម្លៃជាចំនួនគត់ពិតប្រាកដតែប៉ុណ្ណោះ (គ្មានទសភាគ)។ | ដូចជាការគណនារកចំនួនកៅអីនិងតុដែលត្រូវផលិតដើម្បីចំណេញបំផុត ដែលអ្នកមិនអាចផលិតកៅអីកន្លះ (០.៥) ឬតុមួយចំហៀងនោះទេ។ |
| Augmentation algorithm | ជាក្បួនដោះស្រាយដែលចាប់ផ្តើមពីចម្លើយដែលអាចទទួលយកបានមួយ ហើយបន្តស្វែងរកទិសដៅដើម្បីកែតម្រូវ និងធ្វើឱ្យចម្លើយនោះប្រសើរឡើងបន្តិចម្តងៗ រហូតដល់រកឃើញចម្លើយដែលល្អបំផុត។ | ដូចជាការដើរឡើងភ្នំ ដែលអ្នកបន្តឈានជើងទៅរកទីតាំងដែលខ្ពស់ជាងមុនជានិច្ច រហូតទាល់តែទៅដល់កំពូលភ្នំខ្ពស់បំផុត។ |
| Monte Carlo sampling | ជាបច្ចេកទេសប្រើប្រាស់ការចាប់យកគំរូដោយចៃដន្យជាច្រើនដង ដើម្បីធ្វើការប៉ាន់ស្មានលទ្ធផលនៃបញ្ហាគណិតវិទ្យាដែលស្មុគស្មាញ ឬមានទំហំធំពេកដែលកុំព្យូទ័រមិនអាចគណនាអស់។ | ដូចជាការភ្លក់សម្លមួយស្លាបព្រាដើម្បីដឹងពីរសជាតិសម្លទាំងមូល ដោយមិនចាំបាច់ផឹកសម្លនោះអស់មួយឆ្នាំងនោះទេ។ |
| Super-additive property | លក្ខណៈនៃហ្គេមដែលធានាថា ផលចំណេញនៃការរួមបញ្ចូលគ្នារវាងក្រុមពីរដែលដាច់ដោយឡែកពីគ្នា តែងតែផ្តល់តម្លៃធំជាង ឬយ៉ាងហោចណាស់ស្មើនឹងផលចំណេញដែលពួកគេធ្វើដោយឡែកពីគ្នា។ | ដូចជាពាក្យចាស់ពោលថា "ចង្កឹះមួយបាច់កាច់មិនបាក់" ពោលគឺការរួមសាមគ្គីគ្នាបង្កើតកម្លាំងនិងផលប្រយោជន៍ធំជាងមនុស្សម្នាក់ៗបូកបញ្ចូលគ្នា។ |
អត្ថបទដែលបានបោះពុម្ពនៅលើ KhmerResearch ដែលទាក់ទងនឹងប្រធានបទនេះ៖
ប្រធានបទ និងសំណួរស្រាវជ្រាវដែលទាក់ទងនឹងឯកសារនេះ ដែលអ្នកអាចស្វែងរកបន្ថែម៖
