Комбинаторный поиск

В информатике и искусственном интеллекте комбинаторный поиск изучает алгоритмы поиска для решения экземпляров задач, которые в целом считаются сложными, путем эффективного исследования обычно большого пространства решений этих экземпляров. Алгоритмы комбинаторного поиска достигают этой эффективности за счет уменьшения эффективного размера пространства поиска или использования эвристики. Некоторые алгоритмы гарантированно найдут оптимальное решение, в то время как другие могут возвращать только лучшее решение, найденное в той части пространства состояний, которая была исследована.

Классические задачи комбинаторного поиска включают решение головоломки с восемью ферзями или оценку ходов в играх с большим деревом игры , таких как реверси или шахматы .

Изучение теории сложности вычислений помогает мотивировать комбинаторный поиск. Алгоритмы комбинаторного поиска обычно связаны с задачами, которые являются NP-трудными . В целом такие проблемы не считаются эффективно решаемыми. Однако различные приближения теории сложности предполагают, что некоторые случаи (например, «маленькие» случаи) этих проблем могут быть эффективно решены. Это действительно так, и подобные случаи часто имеют важные практические последствия.

Примеры

Общие алгоритмы решения задач комбинаторного поиска включают:

просмотр вперед

Упреждающий просмотр — важный компонент комбинаторного поиска, который примерно определяет, насколько глубоко исследуется граф , представляющий проблему. Необходимость определенного ограничения на просмотр вперед возникает из-за больших графов задач во многих приложениях, таких как компьютерные шахматы и компьютерное го . Наивный поиск этих графов в ширину быстро занял бы всю память любого современного компьютера. Установив определенный предел просмотра вперед, можно тщательно контролировать время работы алгоритма; его время увеличивается экспоненциально по мере увеличения предела просмотра вперед.

Более сложные методы поиска, такие как альфа-бета-отсечение, позволяют исключить из рассмотрения целые поддеревья дерева поиска. Когда используются эти методы, просмотр вперед не является точно определенной величиной, а представляет собой либо максимальную глубину поиска, либо какое-то среднее значение.

См. также

Ссылки

Рассел и Норвиг. Искусственный интеллект: современный подход .