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

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

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

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

Примеры

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

Смотреть вперед

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

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

Смотрите также

Рекомендации