300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa MelayuFloodfill©
ការណែនាំសម្រាប់ការលេងហ្គេម Floodfill
បញ្ហានៃការប្រើចំនួនពណ៌តិចបំផុតដើម្បីដាក់ពណ៌លើផែនទី មានប្រវត្តិយូរយារណាស់មកហើយដូចដែលបានពន្យល់ ជាឧទាហរណ៍នៅក្នុងអត្ថបទវិគីភីឌា ទ្រឹស្តីបទដែលថា ៤ ពណ៌គឺគ្រប់គ្រាន់សម្រាប់ដាក់ពណ៌ប្លង់ផែនទីបានក្លាយជាល្បីល្បាញដោយសារជាទ្រឹស្តីបទគណិតវិទ្យាធំដំបូងគេបង្អស់ដែលអាចស្រាយបញ្ជាក់បានតែតាមរយៈកុំព្យូទ័រប៉ុណ្ណោះ មិនមែនតាមរយៈសម្រាយបញ្ជាក់គណិតវិទ្យាដែលមនុស្សផលិតឡើយ។
គេមិនទាន់ដឹងក្បួនដោះស្រាយច្បាស់លាស់ដើម្បីដាក់ពណ៌ផែនទីប្រកបដោយប្រសិទ្ធភាពនៅឡើយទេ។ ជាមួយពាក្យ 'ប្រកបដោយប្រសិទ្ធភាព' យើងមានន័យថា ប្រសិនបើចំនួនតំបន់ N មានទំហំធំខ្លាំងនោះចំនួននៃការព្យាយាមលាបពណ៌ចាំបាច់នឹងកើនឡើងដូច Nk ដែល k គឺ ជាចំនួនដែលមិនអាស្រ័យលើ N។ និយាយម្យ៉ាងទៀត សម្រាប់ក្បួនដោះស្រាយដែលមានប្រសិទ្ធភាព ចំនួននៃការប៉ុនប៉ងមានចំនួនកើនឡើងតាមពហុធានៃ N។ ជាងនេះទៅទៀត ក្បួនដោះស្រាយការដាក់ពណ៌ត្រូវបានគេហៅថា exponential complexity ជាឧទាហរណ៍ ចំនួននៃការព្យាយាមអាស្រ័យលើ N ឧទាហរណ៍ដូចជា 4N ។
ប្រសិនបើគេត្រូវបានអនុញ្ញាតឱ្យប្រើ ៥ ឬ ៦ ពណ៌ ឬប្រសិនបើផែនទីត្រូវការតែ ២ ពណ៌ នោះក្បួនដោះស្រាយដែលមានប្រសិទ្ធភាពនឹងត្រូវបានគេដឹង។
ឱកាសមួយទៀតដើម្បីទទួលបានវិធីសាស្ត្រមានប្រសិទ្ធភាពគឺត្រូវពិភាក្សានិងអនុវត្តតាមក្បួនដោះស្រាយដ៏មានប្រសិទ្ធិភាពមួយ។ វិធីសាស្រ្ត (ជាការណែនាំ) ដែលមានប្រសិទ្ធភាពលើករណីជាច្រើននឹងត្រូវពិភាក្សាដូចខាងក្រោម៖
- វាមានប្រយោជន៍ក្នុងការលាបពណ៌តំបន់ដែលមានអ្នកជិតខាងច្រើនតាមដែលអាចធ្វើទៅបានពីព្រោះប្រសិនបើតំបន់នោះទទួលបានពណ៌ A នោះអ្នកជិតខាងទាំងអស់នឹងមិនអាចដាក់ពណ៌ A បានទេ. វិធីនេះជួយកាត់បន្ថយចំនួនជម្រើសពណ៌សម្រាប់តំបន់ជិតខាងទាំងនេះហើយដូច្នេះ កាត់បន្ថយចំនួននៃការព្យាយាមពេលក្រោយប្រសិនបើចុងក្រោយមានពណ៌ដូចគ្នានៅជាប់គ្នា។
- ពណ៌ដែលដាក់ដំបូងៗគេគឹអាចរើសបានតាមចិត្តបាន។
- លើកទីមួយដែលពណ៌ទីពីរត្រូវបានប្រើដើម្បីដាក់ពណ៌តំបន់មួយ ជម្រើសពណ៌នេះគឺដាក់បានតាមចិត្តប្រសិនបើតំបន់នេះប៉ះជាមួយតំបន់ដែលបានដាក់ពណ៌ទីមួយ។
- ជាលើកដំបូងដែលពណ៌ទីបីត្រូវបានប្រើដើម្បីដាក់ពណ៌តំបន់ជម្រើសពណ៌នេះមិនគិតថ្លៃទេប្រសិនបើតំបន់នេះប៉ះតំបន់ដែលមានពណ៌ទីមួយនិងតំបន់ដែលមានពណ៌ទីពីរពោលគឺប្រសិនបើពណ៌ទីបីគឺចាំបាច់។
- តំបន់បន្ទាប់ដែលយើងគួរដាក់ពណ៌គឺតំបន់ដែលនៅសល់ពណ៌តែមួយពណ៌គត់ដែលអាចដាក់បាន ដូចនេះយើងមិនត្រូវមានកំហុសក្នុងការដាក់ពណ៌តំបន់នេះទេ។ .
- ចំនួននៃការប៉ុនប៉ងដាក់ពណ៌គឺពិតជាតិចជាង 4N (បើសាកល្បងដាក់ពណ៌ទាំង ៤ សម្រាប់តំបន់ N នីមួយៗ)។ ដូច្នេះចំនួននៃការប៉ុនប៉ងលាបពណ៌នេះពឹងផ្អែកយ៉ាងសំខាន់ទៅលើចំនួនតំបន់ N។ ហេតុដូច្នេះ វាមានប្រយោជន៍ប្រសិនបើតំបន់ដែលដាក់ពណ៌ញែកតំបន់ពណ៌ស (មិនទាន់ដាក់ពណ៌) ជាផែ្នកផ្សេងៗដែលមិនជាប់គ្នា ដែលធ្វើឲ្យតំបន់ពណ៌សនោះអាចត្រូវបានដាក់ពណ៌ដោយខ្លួនឯង។
- ប្រសិនបើអ្នកចង់រកចំនួនពណ៌តិចបំផុតដែលអាចដាក់ពណ៌លើផែនទីដែលឲ្យ នោះដំបូងអ្នកត្រូវពិនិត្យមើលចំនួន ២ ពណ៌ជាការគ្រប់គ្រាន់។ នេះអាចត្រូវបានធ្វើយ៉ាងមានប្រសិទ្ធិភាព។
ប្រសិនបើមានតែពីរពណ៌ A និង B ដែលត្រូវដាក់ តែតំបន់នោះមានពណ៌រួចហើយខុសពីពណ៌ដែលត្រូវដាក់ នោះគេត្រូវជួសជុល(ដាក់ពណ៌សារថ្មី)ចាប់ផ្តើមចេញពីជុំវិញចំនុចប្រសព្វ៖
វិធាននេះក៏មានប្រយោជន៍ចំពោះផែនទីដែលត្រូវប្រើ ៣ ពណ៌ ឬ ៤ ពណ៌ ដែរ ។ ឧទាហរណ៍ ប្រសិនបើតំបន់ទី ១ ខាងក្រោមបានដាក់ពណ៌ A នោះតំបន់ទី ២ និង ទី៤ ត្រូវតែដាក់ពណ៌ផ្សេង ហើយយើងមិនទាន់ដឹងថាត្រូវដាក់ពណ៌ណានៅឡើយទេ ប៉ុន្តែយើងដឹងថាការដាក់ពណ៌ A លើតំបន់ទី ៣ មិនបង្កលក្ខខណ្ឌបន្ថែមលើការដាក់ពណ៌តំបន់ទី ២ និងទី ៤ ទេ ពីព្រោះពួកវាសុទ្ធតែមានតំបន់ជិតខាងដែលមានពណ៌ A រួចហើយ។
រូបភាពទី ៣ បង្ហាញតែផ្នែកតូចមួយនៃផែនទីប៉ុណ្ណោះ ប៉ុន្តែវាអាចធ្វើឱ្យយល់ច្បាស់ដែលអាចយកទៅអនុវត្តសម្រាប់ផែនទីផ្សេងជាច្រើនទៀត។ ប្រសិនបើតំបន់ជិតខាងទាំងអស់នៃតំបន់ទី ៣ (តំបន់ទី ២ និងទី ៤ ក្នុងរូបភាពទី ៣) ក្នុងចំណោមនេះបើវាមានតំបន់ជិតខាងយ់ាងតិចមួយដែលមានពណ៌A (តំបន់ ១ នៅក្នុងរូបភាពទី ៣) នោះការដាក់ពណ៌ A លើតំបន់ទីដែរ មិនអាចជាកំហុសទេ។ មូលហេតុគឺថា ការដាក់ពណ៌ A លើតំបន់ពណ៌ទី ៣ មិនបង្កើតការរឹតត្បិតថ្មីលើតំបន់ជិតខាងទេពីព្រោះពួកគេត្រូវបានហាមឃាត់មិនឱ្យមានពណ៌ A រួចទៅហើយ។ ដូច្នេះ ប្រសិនបើនៅក្នុងដំណើរការដាក់ពណ៌បន្តបន្ទាប់ទៀត បង្ហាញឲ្យឃើញថាមានកំហុស (ដោយសារពណ៌ដែលត្រូវដាក់ជាន់ជាមួយពណ៌នៃតំបន់ជិតខាង) នោះគេត្រូវសាកល្បងដាក់ពណ៌ផ្សេងលើតំបន់ទី ៣ ជំនួសពណ៌ A វិញ។ - ចុះបើតំបន់ទី ៣ ខាងលើក៏ជាតំបន់ជិតខាងតាមទិសអង្កត់ទ្រូងទៅនឹងតំបន់ផ្សេងទៀតដែរ ឧទាហរណ៍តំបន់ទី ៩ ដែលមានពណ៌ផ្សេងរួចទៅហើយ ឧទាហរណ៍ដូចជាពណ៌ B នោះតើតំបន់ទី ៣ គួរតែដាក់ពណ៌ A ឬ ពណ៌B? ដូចគ្នានេះដែរ គេត្រូវពិនិត្យមើលតំបន់ជិតខាងទាំងអស់របស់តំបន់ទី ៣ ថាតើពួកគេត្រូវបានហាមឃាត់មិនឱ្យដាក់ពណ៌ A ឬក៏ហាមឃាត់មិនឱ្យមានពណ៌ B ។ ប្រសិនបើមិនចូលករណីណាមួយនោះទេ ការដាក់ពណ៌លើតំបន់ទី៣ អាចត្រូវរង់ចាំសិន (ដាក់ពណ៌កន្លែងផ្សេងសិន) ។
Follow or subscribe for updates: