Комбинаторный поиск: алгоритмы и стратегии исследования пространства решений.
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.
Главная фигура
Прогнозирование (или глубина поиска) — важный компонент комбинаторного поиска, который определяет, насколько глубоко исследуется граф, представляющий задачу. Необходимость в установке конкретного ограничения на глубину поиска обусловлена большими графами задач во многих приложениях, таких как компьютерные шахматы и го. Наивный поиск в ширину по таким графам быстро исчерпает всю память любого современного компьютера. Устанавливая определенный предел глубины поиска, можно точно контролировать время работы алгоритма; время его работы экспоненциально возрастает с увеличением этого предела. Более сложные методы поиска, такие как альфа-бета отсечение, позволяют исключать из рассмотрения целые поддеревья дерева поиска. При использовании этих методов, глубина поиска не является строго определенной величиной, а представляет собой либо максимальную глубину поиска, либо некий вид среднего значения.
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.