Метод перебора и задачи, решаемые при помощи этого метода

Применение методов искусственного интеллекта в переборных алгоритмах

Перед специалистами самых различных областей часто встает задача нахождения элемента конечного множества, обладающего заданными свойствами (если такой элемент существует). Эта задача в принципе может быть решена с помощью перебора. Есть мнение, что такая принципиальная возможность имеет только теоретическое значение, так как трудоемкость перебора слишком велика. Между тем, любой общий метод, в том числе и метод перебора, может оказаться как хорошим, так и плохим. Все зависит от конкретной задачи и способов реализации. При этом реализация данного метода очень зависима от достижений вычислительной техники, а она в свою очередь не перестает делать все большие и большие успехи. Так что если сегодня что-то мы еще не можем пересчитать, не исключено, что это станет возможным уже завтра.

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

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

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

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

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

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

Одна из областей применения методов, используемых в исследовании нард, - экономика. Именно на эту область ориентирована проведенная и планируемая в дальнейшем работа. Автором работы, в соавторстве с научным руководителем, была сделана публикация основных тезисов об использовании выработанных методов в экономике в сборнике материалов II международной конференции "Математические методы и компьютеры в экономике", проходившей в Пензе в мае этого года. В качестве примера недетерминированной игры в экономике приведена биржевая спекуляция опционами (Stock Option Betting).

Кроме того, что исследование нард - это важная область применения известных методов сокращения перебора, уже сейчас существуют новые подходы, появившиеся в результате работы над программой-игроком в нарды. Одним таким подходом является эвристическая функция риска, результаты использования которой изложены в "Б.Ф.Мельников, А.Н.Радионов. О выборе стратегии в недетерминированных антагонистических играх. - Программирование (РАН), 1998, N5, с.98-99", а некоторое теоретическое обоснование в главе 5 данной работы. Неизбежно возникновение еще большего количества новых методик в исследованиях недетерминированных игр, так как их свойства во многом отличны от свойств детерминированных игр. Эти различия обусловлены присутствием стохастического фактора в виде бросания кубиков, тасовки карт, рыночной конъюнктуры и так далее. Иногда этот фактор может рассматриваться как присутствие некоторой третьей силы в игре, чьи действия описываются вероятностно. Отсюда можно провести параллели с такими областями теории игр, как игра нескольких игроков и игра с непротивоположными интересами. Так как исследование этих областей также находится в начальной стадии, результаты, полученные для недетерминированных игр, могут быть в них использованы.

А.В.Мосеев, underwood.narod.ru, 1999 год