ទឹកជំនន់^©

ការណែនាំសម្រាប់ការលេងហ្គេម Floodfill

បញ្ហា​នៃ​ការ​ប្រើ​ពណ៌​ចំនួន​តិច​បំផុត​ដើម្បី​ដាក់​ពណ៌​ផែនទី​មាន​ប្រវត្តិ​យូរ​អង្វែង​ដូច​ដែល​បាន​ពន្យល់​ជា​ឧទាហរណ៍​ក្នុង អត្ថបទ​វិគីភីឌា​នេះ។ ទ្រឹស្តីបទដែលពណ៌ចំនួន 4 តែងតែគ្រប់គ្រាន់សម្រាប់ដាក់ពណ៌ផែនទីយន្តហោះបានល្បីថាជាទ្រឹស្តីបទគណិតវិទ្យាដ៏ធំដំបូងគេដែលអាចបញ្ជាក់បានតែដោយកុំព្យូទ័រប៉ុណ្ណោះ មិនមែនតាមរយៈភស្តុតាង "គណិតវិទ្យា" ដែលផលិតដោយមនុស្សនោះទេ។

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

ប្រសិនបើគេត្រូវបានអនុញ្ញាតឱ្យប្រើ ៥ ឬ ៦ ពណ៌ ឬប្រសិនបើផែនទីត្រូវការតែ ២ ពណ៌ នោះក្បួនដោះស្រាយដែលមានប្រសិទ្ធភាពនឹងត្រូវបានគេដឹង។

ឱកាសមួយទៀតដើម្បីទទួលបានវិធីសាស្ត្រមានប្រសិទ្ធភាពគឺត្រូវពិភាក្សានិងអនុវត្តតាមក្បួនដោះស្រាយដ៏មានប្រសិទ្ធិភាពមួយ។ វិធីសាស្រ្ត (ជាការណែនាំ) ដែលមានប្រសិទ្ធភាពលើករណីជាច្រើននឹងត្រូវពិភាក្សាដូចខាងក្រោម៖

សំណួរ៖ តើតំបន់ណាដែលត្រូវលាបពណ៌មុនគេ?

សំណួរ៖ តើជម្រើសពណ៌មួយណាដែលរើសបានតាមចិត្ត?

សំណួរ៖ តើត្រូវដាក់ពណ៌តំបន់ណាបន្ទាប់?