Құрлы күш әдісі: компьютер ғылымындағы қарапайым, бірақ тиімді алгоритм. Барлық мүмкіндіктерді тексеру арқылы шешім табу. Қолдану шарттары мен шектеулері.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Мәселелерді шешу әдісі және алгоритмдік парадигма компьютерлік ғылымдағы мәселелерді шешу әдісі
Problem solving technique and algorithmic paradigm
the problem solving technique in computer science
Компьютерлік ғылымда, өрескел күшпен іздеу немесе толық іздеу, сондай-ақ генерациялау және тексеру деп аталады, бұл өте жалпы мәселелерді шешу әдісі және алгоритмдік парадигма, ол барлық мүмкін үміткерлерді жүйелі түрде тексеруден тұрады, әрбір үміткер мәселенің шартына сәйкес келе ме, жоқ па, соны анықтау үшін. Табиғи n санының бөлгіштерін табатын өрескел күш алгоритмі 1-ден n-ге дейінгі барлық бүтін сандарды тізімдейді және олардың әрқайсысы n-ді қалдықсыз бөле ме, жоқ па, соны тексереді. Сегіз патшайымның жұмбағына өрескел күшпен қарау 64 шаршы шахмат тақтасындағы 8 фигураның барлық мүмкін орналасуларын қарастырады және әрбір орналасу үшін әрбір (патшайым) фигурасының басқасына шабуыл жасай алатынын тексереді. Өрескел күшпен іздеуді іске асыру оңай және егер шешім болса, оны әрқашан табады, бірақ іске асыру құны үміткер шешімдердің санына пропорционал, ал көптеген практикалық мәселелерде проблеманың мөлшері артқан сайын бұл сан өте жылдам өседі (§Комбинаторлық жарылыс). Сондықтан, өрескел күшпен іздеу әдетте проблеманың мөлшері шектеулі болғанда немесе кандидат шешімдер жиынтығын басқаруға болатын көлемге дейін қысқартуға мүмкіндік беретін проблемаға тән эвристикалар болғанда қолданылады. Бұл әдіс сондай-ақ, іске асырудың қарапайымдылығы өңдеу жылдамдығынан маңыздырақ болған кезде де қолданылады. Мысалы, алгоритмдегі кез келген қате өте ауыр салдарларға әкелетін жағдайларда немесе математикалық теореманы дәлелдеу үшін компьютерді пайдаланғанда осылай болады. Өрескел күшпен іздеу басқа алгоритмдер мен метаэвристикаларды салыстыру кезінде базалық әдіс ретінде де пайдалы. Шындығында, өрескел күшпен іздеуді ең қарапайым метаэвристика деп санауға болады. Өрескел күшпен іздеуді кері іздеумен шатастырмау керек, онда үлкен шешімдер жиынтықтары нақты тізімделмей-ақ жойылуы мүмкін (жоғарыда көрсетілген сегіз патшайымның проблемасын компьютерлік жолмен шешудегідей). Кестедегі элементті табу үшін қолданылатын әдіс, яғни кестенің барлық жазбаларын бірінен соң бірі ретпен тексеру, сызықтық іздеу деп аталады.
In computer science, brute force search or exhaustive search, also known as generate and test, is a very general problem solving technique and algorithmic paradigm that consists of systematically checking all possible candidates for whether or not each candidate satisfies the problem's statement. A brute force algorithm that finds the divisors of a natural number n would enumerate all integers from 1 to n, and check whether each of them divides n without remainder. A brute force approach for the eight queens puzzle would examine all possible arrangements of 8 pieces on the 64 square chessboard and for each arrangement, check whether each (queen) piece can attack any other. While a brute force search is simple to implement and will always find a solution if it exists, implementation costs are proportional to the number of candidate solutionswhich in many practical problems tends to grow very quickly as the size of the problem increases (§Combinatorial explosion). Therefore, brute force search is typically used when the problem size is limited, or when there are problem specific heuristics that can be used to reduce the set of candidate solutions to a manageable size. The method is also used when the simplicity of implementation is more important than processing speed. This is the case, for example, in critical applications where any errors in the algorithm would have very serious consequences or when using a computer to prove a mathematical theorem. Brute force search is also useful as a baseline method when benchmarking other algorithms or metaheuristics. Indeed, brute force search can be viewed as the simplest metaheuristic. Brute force search should not be confused with backtracking, where large sets of solutions can be discarded without being explicitly enumerated (as in the textbook computer solution to the eight queens problem above). The brute force method for finding an item in a tablenamely, check all entries of the latter, sequentiallyis called linear search.
Комбинаторлық жарылыс
Қара күш әдісінің басты кемшілігі – көптеген нақты әлемдегі проблемалар үшін мүмкін болатын жағдайлардың саны тым көп. Мысалы, егер жоғарыда сипатталғандай, бір санның бөлгіштерін іздесек, тексерілген үміткерлердің саны берілген n санына тең болады. Егер n он алты ондық таңбадан тұрса, іздеу үшін кем дегенде 10¹⁵ компьютерлік нұсқау орындалуы керек, бұл әдеттегі компьютерде бірнеше күнге созылуы мүмкін. Егер n кездейсоқ 64 биттік натурал сан болса, онда орташа есеп бойынша ондық таңбадан кейін 19 таңбасы бар, іздеу шамамен 10 жылға созылады. Дерек көлемі ұлғайған сайын, мүмкін болатын жағдайлардың санының күрт өсуі түрлі проблемаларда кездеседі. Мысалы, егер 10 әріптің белгілі бір ретін іздесек, онда 10! = 3 628 800 қарастырылатын жағдай бар, оларды әдеттегі компьютер бір секундтан кем уақытта жасап, тексеруге болады. Алайда, дерек көлемін 10%-ға ғана арттыратын бір әріпті қосу мүмкін болатын жағдайлардың санын 11 есеге көбейтеді, яғни 1000%-ға арттырады. 20 әріп үшін мүмкін болатын жағдайлардың саны 20!, шамамен 2,4×10¹⁸ немесе 2,4 квинтиллионды құрайды; ал іздеу шамамен 10 жылға созылады. Бұл жағымсыз құбылыс комбинаторлық жарылыс немесе өлшемділіктің қарғысы деп аталады. Комбинаторлық күрделілік шешілмейтін жағдайға әкелетін мысалдың бірі – шахматты шешу. Шахмат әлі шешілмеген ойын. 2005 жылы алты немесе одан аз фигуралы шахмат ойындарының барлық аяқталуы шешілді, нәтижесінде әр позицияның ең жақсы ойынмен қандай болатыны көрсетілді. Шахматқа тағы бір фигура қосылып, 7 фигуралы кесте жасау үшін тағы 10 жыл кетті. Шахмат аяғына тағы бір фигураны қосу (осылайша 8 фигуралы кесте жасау) қосымша комбинаторлық күрделілікке байланысты мүмкін емес деп есептеледі.
The main disadvantage of the brute force method is that, for many real world problems, the number of natural candidates is prohibitively large. For instance, if we look for the divisors of a number as described above, the number of candidates tested will be the given number n. So if n has sixteen decimal digits, say, the search will require executing at least 1015 computer instructions, which will take several days on a typical PC. If n is a random 64 bit natural number, which has about 19 decimal digits on the average, the search will take about 10 years. This steep growth in the number of candidates, as the size of the data increases, occurs in all sorts of problems. For instance, if we are seeking a particular rearrangement of 10 letters, then we have 10! = 3,628,800 candidates to consider, which a typical PC can generate and test in less than one second. However, adding one more letterwhich is only a 10% increase in the data sizewill multiply the number of candidates by 11, a 1000% increase. For 20 letters, the number of candidates is 20!, which is about 2.4×1018 or 2.4 quintillion; and the search will take about 10 years. This unwelcome phenomenon is commonly called the combinatorial explosion, or the curse of dimensionality. One example of a case where combinatorial complexity leads to solvability limit is in solving chess. Chess is not a solved game. In 2005, all chess game endings with six pieces or less were solved, showing the result of each position if played perfectly. It took ten more years to complete the tablebase with one more chess piece added, thus completing a 7 piece tablebase. Adding one more piece to a chess ending (thus making an 8 piece tablebase) is considered intractable due to the added combinatorial complexity.
Қатаң іздестіруді жеделдету
Ашық күш алгоритмін жылдамдатудың бір жолы – іздеу кеңістігін, яғни кандидаттық шешімдер жиынтығын, проблема класына тән эвристикаларды қолдану арқылы азайту. Мысалы, сегіз патшайым мәселесінде стандартты шахмат тақтасына сегіз патшайымды орналастыру керек, осылайша ешбір патшайым екіншісіне шабуыл жасамауы тиіс. Әрбір патшайымды 64 шаршының кез келгеніне орналастыруға болатындықтан, принципінде 64⁸ = 281,474,976,710,656 мүмкіндік қарастырылуы керек. Дегенмен, патшайымдардың барлығы бір-біріне ұқсас болғандықтан және екі патшайымды бір шаршыға орналастыруға болмайтындықтан, кандидаттар – барлық 64 шаршыдан 8 шаршыны таңдаудың барлық мүмкін жолдары; яғни ⁶⁴C₈ = 64!/(56!*8!) = 4,426,165,368 кандидаттық шешім, бұл бұрынғы бағалаудың шамамен 1/60,000 бөлігі. Бұдан әрі, бір қатарда немесе бір бағанда екі патшайым орналасқан ешқандай жағдай шешім бола алмайды. Сондықтан, кандидаттар жиынтығын осы жағдайлармен шектеуге болады. Осы мысал көрсеткендей, шамалы талдау кандидаттық шешімдердің санын күрт азайтуға алып келеді және шешілмейтін мәселені тривиальды мәселеге айналдыруы мүмкін. Кейбір жағдайларда талдау кандидаттарды барлық жарамды шешімдер жиынтығына дейін азайтуы мүмкін; яғни, ол барлық қажетті шешімдерді тікелей санап шығаратын алгоритмді (немесе қажет болған жағдайда бір шешімді табады), сынақтармен және жарамсыз кандидаттарды жасаумен уақытты ысырап етпейді. Мысалы, "1-ден 1,000,000-ға дейінгі 417-ге қалдықсыз бөлінетін барлық бүтін сандарды табу" мәселесі үшін, қарапайым ашық күш шешімі диапазондағы барлық бүтін сандарды жасайды және олардың әрқайсысын бөлінуге тексереді. Алайда, бұл мәселені 417-ден бастап, сан 1,000,000-нан асып кеткенше 417-ні қайта-қайта қосу арқылы әлдеқайда тиімдірек шешуге болады, бұл тек 2398 (= 1,000,000 ÷ 417) қадамды қажет етеді және ешқандай сынақтарды қажет етпейді.
One way to speed up a brute force algorithm is to reduce the search space, that is, the set of candidate solutions, by using heuristics specific to the problem class. For example, in the eight queens problem the challenge is to place eight queens on a standard chessboard so that no queen attacks any other. Since each queen can be placed in any of the 64 squares, in principle there are 648 = 281,474,976,710,656 possibilities to consider. However, because the queens are all alike, and that no two queens can be placed on the same square, the candidates are all possible ways of choosing of a set of 8 squares from the set all 64 squares; which means 64 choose 8 = 64!/(56!*8!) = 4,426,165,368 candidate solutionsabout 1/60,000 of the previous estimate. Further, no arrangement with two queens on the same row or the same column can be a solution. Therefore, we can further restrict the set of candidates to those arrangements. As this example shows, a little bit of analysis will often lead to dramatic reductions in the number of candidate solutions, and may turn an intractable problem into a trivial one. In some cases, the analysis may reduce the candidates to the set of all valid solutions; that is, it may yield an algorithm that directly enumerates all the desired solutions (or finds one solution, as appropriate), without wasting time with tests and the generation of invalid candidates. For example, for the problem "find all integers between 1 and 1,000,000 that are evenly divisible by 417" a naive brute force solution would generate all integers in the range, testing each of them for divisibility. However, that problem can be solved much more efficiently by starting with 417 and repeatedly adding 417 until the number exceeds 1,000,000which takes only 2398 (= 1,000,000 ÷ 417) steps, and no tests.
Іздеу кеңістігін қайта реттеу
Барлық шешімдерді емес, тек бір шешімді қажет ететін қолданбаларда, күшпен іздеудің күтілетін жұмыс уақыты көбінесе үміткерлерді тексеру ретіне байланысты болады. Жалпы ереже бойынша, ең перспективті үміткерлерді алдымен тексеру керек. Мысалы, кездейсоқ сан n-нің дұрыс бөлгішін іздегенде, кандидат бөлгіштерді 2-ден n-1 дейін өсу ретімен санау жақсырақ, себебі n-нің c-ға бөліну ықтималдығы 1/c-ға тең. Сонымен қатар, үміткердің жарамды болу ықтималдығына бұрынғы сәтсіз әрекеттер жиі әсер етеді. Мысалы, берілген 1000 биттік P жолында 1 бит табу мәселесін қарастырайық. Бұл жағдайда кандидат шешімдері 1 мен 1000 арасындағы индекстер болып табылады, ал кандидат c жарамды болады, егер P[c] = 1 болса. Енді, егер P-нің бірінші биті 0 немесе 1 болуы мүмкін болса, бірақ одан кейінгі әр бит 90% ықтималдықпен алдыңғысына тең болса, не болады? Егер үміткерлер 1-ден 1000-ға дейін өсу ретімен саналса, сәттілікке дейін тексерілген t үміткерлердің саны орташа есеппен шамамен 6-ға жетеді. Ал егер үміткерлер 1, 11, 21, 31, 991, 2, 12, 22, 32 және т.б. ретімен саналса, t-ның күтілетін мәні 2-ден сәл ғана артық болады. Жалпы алғанда, іздеу кеңістігі сондай етіп санау керек, келесі үміткердің жарамды болуы мүмкін, егер бұрынғы әрекеттер жарамсыз болған болса. Сондықтан, егер жарамды шешімдер белгілі бір мағынада "жинақталған" болса, онда әрбір жаңа үміткер алдыңғыларынан мүмкіндігінше алыс болуы керек. Әрине, егер шешімдер күтпеген жерден біркелкі таралып жатса, онда керісінше болады.
In applications that require only one solution, rather than all solutions, the expected running time of a brute force search will often depend on the order in which the candidates are tested. As a general rule, one should test the most promising candidates first. For example, when searching for a proper divisor of a random number n, it is better to enumerate the candidate divisors in increasing order, from 2 to n − 1, than the other way aroundbecause the probability that n is divisible by c is 1/c. Moreover, the probability of a candidate being valid is often affected by the previous failed trials. For example, consider the problem of finding a 1 bit in a given 1000 bit string P. In this case, the candidate solutions are the indices 1 to 1000, and a candidate c is valid if P[c] = 1. Now, suppose that the first bit of P is equally likely to be 0 or 1, but each bit thereafter is equal to the previous one with 90% probability. If the candidates are enumerated in increasing order, 1 to 1000, the number t of candidates examined before success will be about 6, on the average. On the other hand, if the candidates are enumerated in the order 1,11,21,31 991,2,12,22,32 etc., the expected value of t will be only a little more than 2. More generally, the search space should be enumerated in such a way that the next candidate is most likely to be valid, given that the previous trials were not. So if the valid solutions are likely to be "clustered" in some sense, then each new candidate should be as far as possible from the previous ones, in that same sense. The converse holds, of course, if the solutions are likely to be spread out more uniformly than expected by chance.
Қатаң іздеудің баламалары
Басқа да көптеген іздеу әдістері немесе метаэвристикалар бар, олар шешім туралы әртүрлі жартылай білімді пайдалану үшін жасалған. Эвристикалар іздеудің кейбір бөліктерін ертерек тоқтату үшін де қолданылуы мүмкін. Мұның бір мысалы – ойын ағаштарын іздеу үшін қолданылатын минимакс принципі, ол іздеудің бастапқы кезеңінде көптеген тармақтарды жояды. Тілдік талдау сияқты салаларда, мысалы, кестелік талдау сияқты әдістер, мәселедегі шектеулерді пайдаланып, экспоненциалды күрделілікті полиномиалды күрделілікке дейін азайтуға мүмкіндік береді. Көптеген жағдайларда, мысалы, шектеулерді қанағаттандыру мәселелерінде, шектеулерді тарату арқылы іздеу кеңістігін күрт қысқартуға болады, бұл шектеулік бағдарламалау тілдерінде тиімді іске асырылады. Іздеу кеңістігін қысқарту үшін мәселенің толық нұсқасын жеңілдетілген нұсқамен алмастыруға да болады. Мысалы, компьютерлік шахматта, ойынның қалған бөлігі үшін барлық мүмкін қимылдардың толық минимакс ағашын есептеудің орнына, минимакс мүмкіндіктерінің шектеулі ағашы есептеледі, ағаш белгілі бір мөлшердегі қимылдарда қысқарылады, ал ағаштың қалған бөлігі статикалық бағалау функциясымен жуықталады.
There are many other search methods, or metaheuristics, which are designed to take advantage of various kinds of partial knowledge one may have about the solution. Heuristics can also be used to make an early cutoff of parts of the search. One example of this is the minimax principle for searching game trees, that eliminates many subtrees at an early stage in the search. In certain fields, such as language parsing, techniques such as chart parsing can exploit constraints in the problem to reduce an exponential complexity problem into a polynomial complexity problem. In many cases, such as in Constraint Satisfaction Problems, one can dramatically reduce the search space by means of Constraint propagation, that is efficiently implemented in Constraint programming languages. The search space for problems can also be reduced by replacing the full problem with a simplified version. For example, in computer chess, rather than computing the full minimax tree of all possible moves for the remainder of the game, a more limited tree of minimax possibilities is computed, with the tree being pruned at a certain number of moves, and the remainder of the tree being approximated by a static evaluation function.
Криптографияда
Криптографияда, күшпен сынау шабуылы дұрыс кілт табылғанға дейін барлық мүмкін кілттерді жүйелі түрде тексеруден тұрады. Бұл стратегия теориялық тұрғыдан кез келген шифрланған деректерге (бір реттік блоктан басқа) қарсы қолданылуы мүмкін, егер шабуылшы шифрлау жүйесіндегі әлсіздіктерді пайдалана алмай, өз жұмысын жеңілдете алмайтын жағдайда. Шифрлауда қолданылатын кілттің ұзындығы күшпен сынау шабуылын жүргізудің практикалық мүмкіндігін анықтайды, ұзын кілттерді қысқа кілттерге қарағанда экспоненциалды түрде бұзу қиынырақ. Күшпен сынау шабуылдары кодталатын деректерді жасыру арқылы тиімсіздетілуі мүмкін, бұл шабуылшыға кодты бұзған кезде оны тануды қиындатады. Шифрлау жүйесінің беріктігін бағалаудың бір өлшемі – шабуылшыға оған қарсы күшпен сынау шабуылын сәтті жүргізу үшін қанша уақыт керек болатыны.
In cryptography, a brute force attack involves systematically checking all possible keys until the correct key is found. This strategy can in theory be used against any encrypted data (except a one time pad) by an attacker who is unable to take advantage of any weakness in an encryption system that would otherwise make his or her task easier. The key length used in the encryption determines the practical feasibility of performing a brute force attack, with longer keys exponentially more difficult to crack than shorter ones. Brute force attacks can be made less effective by obfuscating the data to be encoded, something that makes it more difficult for an attacker to recognise when he has cracked the code. One of the measures of the strength of an encryption system is how long it would theoretically take an attacker to mount a successful brute force attack against it.