Комбинаторлық іздеу алгоритмдері және олардың қолданылуы
Combinatorial search
Күрделі проблемаларды шешу үшін қолданылатын комбинаторлық іздеу алгоритмдері, тиімділіктері, ең жақсы шешім табу әдістері туралы мақала. AI, ойындар, жүйелік талдау.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Компьютерлік ғылым мен жасанды интеллектте комбинаторлық іздеу – жалпы алғанда қиын деп саналатын проблемалардың мысалдары үшін алгоритмдерді іздеуді зерттейді, осы мысалдардың әдетте үлкен шешім кеңістігін тиімді зерттеу арқылы. Комбинаторлық іздеу алгоритмдері іздеу кеңістігінің нақты көлемін азайту арқылы немесе эвристика қолдану арқылы осы тиімділікке қол жеткізеді. Кейбір алгоритмдер оңтайлы шешімді табуға кепілдік береді, ал басқалары күй кеңістігінің зерттелген бөлігінде табылған ең жақсы шешімді ғана қайтарады. Классикалық комбинаторлық іздеу мәселелеріне сегіз патшайымның жұмбағын шешу немесе үлкен ойын ағашы бар ойындардағы, мысалы, реверси немесе шахматтағы қимылдарды бағалау кіреді. Есептеу күрделілігі теориясын зерттеу комбинаторлық іздеуді дамытуға көмектеседі. Комбинаторлық іздеу алгоритмдері көбінесе NP-қиын проблемалармен айналысады. Мұндай проблемалардың жалпы жағдайда тиімді шешілуі мүмкін емес деп есептеледі. Дегенмен, күрделілік теориясының әртүрлі жуықтамалары осы проблемалардың кейбір мысалдарының (мысалы, "кішкентай" мысалдардың) тиімді шешілуі мүмкін екенін ұсынады. Бұл шындығында солай, және мұндай мысалдардың маңызды практикалық салдары бар.
In computer science and artificial intelligence, combinatorial search studies search algorithms for solving instances of problems that are believed to be hard in general, by efficiently exploring the usually large solution space of these instances. Combinatorial search algorithms achieve this efficiency by reducing the effective size of the search space or employing heuristics. Some algorithms are guaranteed to find the optimal solution, while others may only return the best solution found in the part of the state space that was explored. Classic combinatorial search problems include solving the eight queens puzzle or evaluating moves in games with a large game tree, such as reversi or chess. A study of computational complexity theory helps to motivate combinatorial search. Combinatorial search algorithms are typically concerned with problems that are NP hard. Such problems are not believed to be efficiently solvable in general. However, the various approximations of complexity theory suggest that some instances (e. g. "small" instances) of these problems could be efficiently solved. This is indeed the case, and such instances often have important practical ramifications.
Көруші
Көру алды – комбинаторлық іздеудің маңызды құралы, ол проблеманы көрсететін графтың қаншалықты терең зерттелетінін шамамен анықтайды. Көру алдының нақты шегіне қажеттілік, компьютерлік шахмат және компьютерлік Го сияқты көптеген қолданыстардағы үлкен проблемалық графтардан туындайды. Мұндай графтарды қарапайым ендік бойынша іздеу (breadth-first search) кез келген заманауи компьютердің жадын тез толықтырып жіберуі мүмкін. Көру алды шегін белгілеу арқылы алгоритмнің жұмыс уақытын бақылауға болады; көру алды шегі артқан сайын оның уақыты экспоненциалды түрде өседі. Альфа-бета қию сияқты жетілдірілген іздеу техникалары іздеу ағашының толық тармақтарын қарастырудан шығаруға мүмкіндік береді. Бұл техникалар қолданылғанда, көру алды нақты сан ретінде емес, ізделген ең терең деңгей немесе орташа мән ретінде қарастырылады.
Lookahead is an important component of combinatorial search, which specifies, roughly, how deeply the graph representing the problem is explored. The need for a specific limit on lookahead comes from the large problem graphs in many applications, such as computer chess and computer Go. A naive breadth first search of these graphs would quickly consume all the memory of any modern computer. By setting a specific lookahead limit, the algorithm's time can be carefully controlled; its time increases exponentially as the lookahead limit increases. More sophisticated search techniques such as alpha–beta pruning are able to eliminate entire subtrees of the search tree from consideration. When these techniques are used, lookahead is not a precisely defined quantity, but instead either the maximum depth searched or some type of average.