ការសរសេរកម្មវិធីថាមវន្ត, គោលការណ៍ជាមូលដ្ឋាន

ដើម្បីជ្រើសជាដំណោះស្រាយល្អបំផុតនៅពេលដែលសម្តែងភារកិច្ចសរសេរកម្មវិធីពេលខ្លះត្រូវបានទាមទារដើម្បីតម្រៀបបរិមាណធំនៃបន្សំទិន្នន័យដែលផ្ទុកសតិនៃកុំព្យូទ័រផ្ទាល់ខ្លួន។ វិធីសាស្រ្តបែបនេះរួមមាន, ឧទាហរណ៍, វិធីសាស្រ្តសរសេរកម្មវិធីនៃ "ការបែងចែកនិងច្បាប់»។ ក្នុងករណីនេះក្បួនដោះស្រាយបញ្ហាការបំបែកចូលទៅក្នុងការផ្តល់ជូននូវទំហំតូចភារកិច្ចរងដោយឡែកពីគ្នា។ វិធីសាស្រ្តនេះគឺអនុវត្តបានតែនៅក្នុងករណីទាំងនោះដែលជាកន្លែងដែលតូចភារកិច្ចរងឯករាជ្យទៅវិញទៅមក។ ដើម្បីជៀសវាងការធ្វើការងារដែលមិនចាំបាច់ប្រសិនបើការសម្តែងអនុអាស្រ័យគ្នាទៅវិញទៅភារកិច្ចដែលបានប្រើប្រាស់វិធីសាស្រ្តសរសេរកម្មវិធីថាមវន្តដែលបានស្នើអាមេរិច R.Bellmanom ក្នុង 50 ឆ្នាំនេះ។

វិធីសាស្រ្តនេះ

សរសេរកម្មវិធីថាមវន្តគឺជាដំណោះស្រាយល្អបំផុតដើម្បីកំណត់បញ្ហា n វិមាត្រដែលបានចែករំលែកដំណាក់កាលដាច់ដោយឡែក n នាង។ គ្នានៃពួកគេគឺជាភារកិច្ចអនុដោយគោរពទៅនឹងអថេរមួយ។

អត្ថប្រយោជន៍សំខាន់នៃវិធីសាស្រ្តនេះអាចត្រូវបានចាត់ទុកថាការអភិវឌ្ឍន៍ចូលរួមនៅក្នុងការបង្កើនប្រសិទ្ធិភាពមួយបញ្ហាវិមាត្រ subtasks ជំនួសឱ្យបញ្ហា n វិមាត្រមួយនិងគោលបំណងចម្បងរបស់យើងនឹងត្រូវបាន«បាតឡើង "។

វាគឺជាទីប្រឹក្សាដើម្បីអនុវត្តការសរសេរកម្មវិធីថាមវន្តនៅក្នុងករណីទាំងនោះដែលជាកន្លែងដែលភារកិច្ចរងនេះទាក់ទងពោលគឺ ចែករំលែកនូវម៉ូឌុលរួម។ ក្បួនដោះស្រាយនេះបានផ្តល់នូវការសម្រេចចិត្តរបស់គ្នានៃភារកិច្ចរងនេះម្តង, និងការឆ្លើយតបសន្សំត្រូវបានអនុវត្តក្នុងតារាងពិសេស។ នេះធ្វើឱ្យវាអាចធ្វើទៅបានមិនមែនដើម្បីគណនាចម្លើយមួយនៅពេលដែលពួកគេបានជួបជាថ្មីម្តងទៀតជាមួយនឹងការអនុភារកិច្ចដូចគ្នា។

ភារកិច្ចសរសេរកម្មវិធីថាមវន្ត ដោះស្រាយបញ្ហា នៃការបង្កើនប្រសិទ្ធិភាព។ អ្នកនិពន្ធនៃវិធីសាស្រ្តនេះត្រូវបានបង្កើតឡើងដោយអ័រ Bellman គោលការណ៍បង្កើនប្រសិទ្ធិភាព: អ្វីដែលមានស្ថានភាពដំបូងនៃគ្នានៃជំហាននេះនិងដំណោះស្រាយដែលបានកំណត់នៅក្នុងជំហាននេះទាំងអស់ខាងក្រោមដើម្បីជ្រើសរើសយកល្អប្រសើរបំផុតក្នុងការទាក់ទងទៅនឹងរដ្ឋនេះដែលទទួលបានប្រព័ន្ធនេះនៅចុងបញ្ចប់នៃជំហាននេះ។

វិធីសាស្រ្តនេះធ្វើអោយប្រសើរឡើងនូវការអនុវត្តនៃភារកិច្ចដោះស្រាយបានដោយមធ្យោបាយនៃការវ៉ារ្យ៉ង់ឬហៅខ្លួនឯងនោះ។

អគារក្បួនដោះស្រាយភារកិច្ច

ក្បួនដោះស្រាយការសរសេរកម្មវិធីថាមវន្តជាប់ពាក់ព័ន្ធនឹងការសាងសង់ភារកិច្ចដូចដែលកិច្ចការនេះដូច្នេះត្រូវបានបំបែកទៅពីរឬច្រើនភារកិច្ចរងជាដំណោះស្រាយរបស់វាត្រូវទៅនឹងសមាសភាពនៃដំណោះស្រាយល្អប្រសើរបំផុតដើម្បីភារកិច្ចរងទាំងអស់, វារួមបញ្ចូល។ លើសពីនេះទៀត, វាគឺជាការចាំបាច់ដើម្បីសរសេរទាក់ទងនឹងកើតឡើងវិញនិងការគណនាតម្លៃប៉ារ៉ាម៉ែត្រល្អបំផុតសម្រាប់ភារកិច្ចទាំងមូល។

ពេលខ្លះនៅលើជំហានទី 3 នេះគឺដើម្បីទន្ទេញចាំពផ្ទៃខាងក្រោយមួយចំនួនបន្ថែមទៀតនៅលើការរីកចំរើននៃកិច្ចការនីមួយ។ នេះត្រូវបានហៅត្រឡប់មកវិញដាច់សរសៃឈាមខួរក្បាល។

វិធីសាស្រ្តក្នុងការដាក់ពាក្យស្នើសុំ

ការសរសេរកម្មវិធីថាមវន្តត្រូវបានអនុវត្តនៅពេលដែលមានលក្ខណៈពិសេសលក្ខណៈពីរ:

• ល្អប្រសើរបំផុតសម្រាប់ភារកិច្ចរង;
• វត្តមាននៅក្នុងបញ្ហានៃការ subproblems ត្រួតគ្នានៃ។

ដោះស្រាយបញ្ហានេះដោយការសរសេរកម្មវិធីបង្កើនប្រសិទ្ធិភាពថាមវន្តដំបូងអ្នកត្រូវការរៀបរាប់ពីរចនាសម្ព័ន្ធនៃដំណោះស្រាយនេះ។ ភារកិច្ចត្រូវតែល្អប្រសើរបំផុតប្រសិនបើដំណោះស្រាយត្រូវបានផ្សំឡើងនៃការសម្រេចចិត្តរបស់ខ្លួនភារកិច្ចរងល្អបំផុត។ ក្នុងករណីនេះវាគឺជាទីប្រឹក្សាដើម្បីប្រើការសរសេរកម្មវិធីថាមវន្ត។

លក្ខណៈសម្បត្តិទីពីរនៃបញ្ហានេះមានសារៈសំខាន់ក្នុងការវិធីសាស្រ្តនេះ - មួយចំនួនតូចមួយនៃភារកិច្ចរង។ ជាដំណោះស្រាយហៅខ្លួនឯងនៃបញ្ហាដោយប្រើអនុដូចគ្នាបញ្ហាត្រួតគ្នាចំនួនដែលអាស្រ័យទៅលើទំហំនៃការពដំបូង។ ចម្លើយគឺត្រូវបានទុកនៅក្នុងតារាងពិសេសមួយ, កម្មវិធីនេះរក្សាទុកពេលវេលាដោយប្រើទិន្នន័យនេះ។

ប្រសិទ្ធិភាពជាពិសេសគឺការប្រើប្រាស់នៃការសរសេរកម្មវិធីថាមវន្តនៅពេលដែលភារកិច្ចត្រូវបានត្រូវការដើម្បីធ្វើការសម្រេចចិត្តសំខាន់ក្នុងដំណាក់កាលនេះ។ ឧទាហរណ៍ពិចារណាឧទាហរណ៍ធម្មតានៃបញ្ហានៃការជំនួសនិងជួសជុលឧបករណ៍។ ចូរនិយាយថានៅលើម៉ាស៊ីនសម្ដែងរោងចក្រផលិតសំបកកង់សម្រាប់នៅពេលដូចគ្នានេះធ្វើឱ្យសំបកកង់នេះនៅក្នុងសំណុំបែបបទពីរផ្សេងគ្នា។ នៅក្នុងព្រឹត្តិការណ៍ដែលផ្នែកមួយនៃទម្រង់បរាជ័យនេះវាគឺជាការចាំបាច់ដើម្បីដោះរុះរើម៉ាស៊ីន។ វាគឺជាការយល់ថាពេលខ្លះផលចំណេញច្រើនជាងដើម្បីជំនួសនិងជាទម្រង់លើកទីពីរក្នុងគោលបំណងដើម្បីដោះរុះរើម៉ាស៊ីននៅក្នុងករណីនិងទម្រង់នេះនឹងត្រូវបាន unworkable នៅក្នុងដំណាក់កាលបន្ទាប់។ ជាពិសេសចាប់តាំងពីវាជាការងាយស្រួលដើម្បីជំនួសរូបរាងមុនពេលពួកគេទាំងពីរបានធ្វើការចាប់ផ្តើមបរាជ័យ។ វិធីសាស្រ្តក្នុងការសរសេរកម្មវិធីថាមវន្តកំណត់យុទ្ធសាស្រ្តល្អបំផុតនៅក្នុងបញ្ហានៃការជំនួសនៃទម្រង់ទាំងនេះយកទៅក្នុងគណនីកត្តាទាំងអស់នេះ: អត្ថប្រយោជន៍នៃការបន្តនៃការកេងប្រវ័ញ្ចទម្រង់, ការបាត់បង់នៃពេលវេលារងចាំម៉ាស៊ីន, តម្លៃនៃសំបកកង់បានបោះបង់ចោលនិងច្រើនជាងនេះ។