Часть 9.

<При ><реализации ><стратегии ><минимакса ><пометим ><каждый ><уровень ><в ><области ><поиска ><именем ><игрока, ><выполняющего ><очередной ><ход: ><или ><МАХ. ><В ><примере ><на ><рис. ><4.14 ><первый ><ход ><делает ><Каждому ><листовому ><узлу ><присвоим ><значение ><1 ><или ><0, ><в ><>зависимости< ><от ><победителя: ><МАХ ><или ><В ><процессе ><реализации ><процедуры ><минимакса ><эти ><значения ><передаются ><вверх ><по ><графу ><согласно ><следующему ><правилу.>

<Если ><родительское ><состояние ><является ><узлом ><МАХ, ><то ><ему ><присваивают ><>максимальное< ><значение.>

<Если ><родительское ><состояние ><- ><узел ><то ><ему ><присваивают ><минимальное

><значение.>

<Значение, ><связываемое ><таким ><образом ><с ><каждым ><состоянием, ><отражает ><наилучшее ><со><стояние, ><которого ><этот ><игрок ><может ><достичь ><(принимая ><во ><внимание ><действия ><>противника< ><в ><соответствии ><с ><алгоритмом ><минимакса). ><Таким ><образом, ><полученные ><значения ><ис­><пользуются ><для ><того, ><чтобы ><выбрать ><наилучший ><среди ><возможных ><шагов. ><Результат ><применения ><алгоритма ><минимакса ><к ><графу ><пространства ><состояний ><для ><игры ><"ним" ><>показан< ><на ><рис. ><4.14.>

<Значения ><вершинам ><присваиваются ><снизу ><вверх ><на ><основе ><принципа ><минимакса. ><>Поскольку< ><любой ><из ><возможных ><первых ><шагов ><ведет ><к ><вершинам ><со ><значением ><1, ><второй ><игрок, ><МАХ, ><всегда ><может ><победить, ><независимо ><от ><первого ><хода ><может ><побе­><дить ><только ><в ><том ><случае, ><если ><МАХ ><допустит ><ошибку. ><На ><рис. ><4.14 ><видно, ><что ><может ><выбрать ><любой ><из ><возможных ><вариантов ><первого ><хода ><- ><все ><они ><открывают ><возможные ><пути ><победы ><МАХ, ><отмеченные ><на ><рисунке ><полужирными ><линиями ><со ><стрелками.>

<Хотя ><существуют ><игры, ><где ><возможен ><полный ><перебор, ><все ><же ><наиболее ><интересными ><являются ><случаи, ><в ><которых ><он ><неприменим. ><В ><следующем ><разделе ><будет ><рассмотрено ><эвристическое ><приложение ><минимакса.>

<4.3.2. ><Минимакс ><при ><фиксированной ><глубине ><поиска>

<При ><использовании ><минимакса ><в ><более ><сложных ><играх ><редко ><удается ><построить ><>полный< ><граф ><пространства ><состояний. ><Обычно ><поиск ><выполняют ><вглубь ><на ><определенное ><число ><уровней, ><которое ><определяется ><располагаемыми ><ресурсами ><времени ><и ><памяти ><>компьютера<. ><Эта ><стратегия ><называется ><прогнозированием ><п-го ><слоя ><(n-ply ><где ><л ><- ><число ><исследуемых ><уровней. ><Такой ><подграф ><не ><отражает ><всех ><состояний ><игры, ><и ><по­><этому ><его ><узлам ><невозможно ><присвоить ><значения, ><отражающие ><победу ><или ><поражение. ><Поэтому ><с ><каждой ><вершиной ><связывают ><значение, ><определяемое ><некоторой ><>эвристической< ><функцией ><оценки. ><Значение, ><которое ><присваивается ><каждой ><из ><л ><вершин ><на ><пути ><от ><корневой ><вершины, ><- ><не ><показатель ><возможности ><достичь ><победы ><(как ><в ><предыдущем ><примере). ><Это ><просто ><эвристическое ><значение ><оптимального ><состояния, ><которое ><может ><быть ><достигнуто ><за ><л ><шагов ><от ><этой ><корневой ><вершины. ><Прогнозирование ><увеличивает ><силу ><эвристики, ><позволяя ><применить ><ее ><на ><большей ><области ><пространства ><состояний. ><Стратегия ><минимакса ><интегрирует ><эти ><отдельные ><оценки ><в ><значение, ><которое ><>присваивается< ><родительскому ><состоянию.>

<><Глава ><4. ><Эвристический ><поиск>< ><171>

><<>

<Рис. ><4.14. ><Принцип ><минимакса ><для ><игры ><"ним". ><Жирные ><линии ><показывают ><пути ><к ><победе ><МАХ. ><Каждому ><узлу ><присвоено ><значение ><0 ><или ><1 ><в ><соответ­><ствии ><с ><процедурой ><минимакса>

<В ><конфликтной ><игре ><каждый ><игрок ><пытается ><переиграть ><другого, ><и ><многие ><игровые ><эвристики ><прямо ><измеряют ><преимущество ><одного ><игрока ><над ><другим. ><В ><шахматах ><очень ><важно ><иметь ><преимущество ><в ><какой-либо ><части ><игровой ><доски, ><так ><что ><простая ><эвристика ><может ><учитывать ><разность ><количества ><частей, ><где ><имеют ><преимущество ><либо ><МАХ, ><либо ><и ><максимизировать ><ее. ><Можно ><применить ><и ><более ><сложную ><стратегию ><- ><>присваивать< ><различные ><значения ><частям ><доски, ><в ><зависимости ><от ><позиции ><фигур ><на ><доске ><(например, ><ферзь ><против ><пешки ><или ><король ><против ><пешки). ><Большинство ><игр ><дают ><без­><граничные ><возможности ><для ><создания ><всевозможных ><эвристик.>

<Графы ><игр ><рассматриваются ><по ><уровням. ><Как ><показано ><на ><рис. ><4.14, ><МАХ ><и ><де><лают ><шаги ><поочередно. ><Каждой ><ход ><игрока ><определяет ><новый ><уровень ><графа. ><Типичная ><игровая ><программа ><предсказывает ><ходы ><до ><определенной ><фиксированной ><глубины, ><>которая< ><определяется ><пространственными ><или ><временными ><ограничениями ><компьютера. ><Со­><стояния ><до ><этой ><глубины ><оцениваются ><эвристикой ><и ><на ><основе ><минимакса ><>распространяются< ><обратно ><к ><начальному ><состоянию. ><Алгоритм ><поиска ><затем ><использует ><эти ><>производные< ><значения, ><чтобы ><выбрать ><наилучший ><среди ><возможных ><ходов.>

<Присвоив ><оценку ><каждому ><состоянию ><выбранного ><слоя, ><программа ><передает ><это ><>значение< ><каждому ><родительскому ><состоянию. ><Если ><родительское ><состояние ><относится ><к ><уровню ><ему ><передается ><минимальное ><из ><состояний ><всех ><его ><потомков. ><Если ><>родительское< ><состояние ><- ><узел ><уровня ><МАХ, ><минимакс ><назначает ><ему ><максимальное ><>значение< ><из ><всех ><его ><потомков.>

<Максимизируя ><значения ><для ><родительских ><узлов ><МАХ ><и ><одновременно ><минимизируя ><их ><для ><алгоритм ><осуществляет ><проход ><по ><графу, ><присваивая ><значения ><потомкам ><те->

<><172>

<Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<кущего ><состояния. ><Затем ><эти ><значения ><используются ><алгоритмом ><для ><выбора ><наилучшего ><потомка ><текущего ><состояния. ><На ><рис. ><4.15 ><алгоритм ><минимакса ><проиллюстрирован ><на ><гипотетическом ><пространстве ><состояний ><с ><четырьмя ><уровнями.>

<Самые ><ранние ><работы ><по ><ИИ ><в ><этой ><области ><- ><это ><программа ><игры ><в ><шашки, ><>созданная< ><Самюэлем ><(Samuel) ><в ><1959 ><году. ><Эта ><программа ><была ><исключением ><для ><того ><време­><ни, ><особенно ><учитывая ><существующие ><ограничения ><для ><компьютеров ><50-х ><годов. ><Мало ><того, ><что ><эта ><программа ><игры ><в ><шашки ><применяла ><эвристический ><поиск, ><в ><ней ><также ><присутствовал ><простой ><алгоритм ><обучения. ><Эта ><программа ><была ><во ><многом ><пионерской, ><и ><ее ><все ><еще ><используют ><при ><создании ><игровых ><и ><обучающихся ><программ.>

<Программа ><Сэмюэля ><оценивала ><состояние ><доски, ><используя ><взвешенную ><сумму ><не><скольких ><различных ><эвристических ><значений>

<>

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

<Программа ><Самюэля ><позволяет ><рассматривать ><необходимое ><число ><уровней ><(обычно ><ограниченное ><возможностями ><компьютера) ><и ><оценивает ><все ><состояния ><на ><данном ><уровне, ><используя ><полиномиальную ><оценку. ><Затем ><с ><помощью ><различных ><вариаций ><алгоритма ><минимакса ><эти ><значения ><распространяются ><по ><графу ><в ><обратном ><направлении. ><После ><этого ><игрок ><может ><делать ><ход ><в ><наилучшее ><состояние ><с ><учетом ><хода ><противника. ><Затем ><весь ><процесс ><повторяется.>

<Если ><в ><процессе ><полиномиального ><оценивания ><некоторые ><ходы ><теряются, ><то ><программа ><настраивает ><коэффициенты, ><чтобы ><повысить ><эффективность. ><Другими ><словами, ><большие ><весовые ><коэффициенты ><уменьшаются ><(поскольку ><они ><вносят ><максимальный ><вклад ><в ><>неправильную< ><оценку), ><а ><меньшие ><веса ><оценок ><увеличиваются, ><чтобы ><усилить ><их ><влияние. ><Если ><программа ><побеждает, ><то ><противник, ><соответственно, ><проигрывает. ><Программа ><обучается, ><играя ><против ><человека ><или ><против ><другой ><версии ><такой ><же ><программы.>

<Таким ><образом, ><программа ><Сэмюэля ><использовала ><алгоритм ><поиска ><экстремума ><для ><обучения, ><пытаясь ><улучшить ><эффективность ><и ><сделать ><локальные ><уточнения ><в ><>полиномиальной< ><оценке. ><Самюэль ><ограничил ><алгоритм ><поиска ><экстремума, ><введя ><проверку ><>эффективности< ><индивидуальных ><взвешенных ><эвристических ><оценок ><и ><удаляя ><наименее ><>эффективные<. ><Программа ><имеет ><некоторые ><интересные ><особенности. ><Например, ><из-за ><>ограниченности< ><глобальной ><стратегии ><она ><чувствительна ><к ><функциям ><оценки, ><приводящим ><к ><ловушкам. ><Модуль ><самообучения ><программы ><уязвим ><в ><случае ><противоречивой ><игры ><оппонента. ><Например, ><если ><противник ><широко ><использовал ><различные ><стратегии ><или ><просто ><играл ><"по-дурацки", ><то ><веса ><в ><полиномиальной ><оценке ><начинали ><принимать ><"случайные" ><значения, ><что ><приводило ><к ><полному ><снижению ><эффективности.>

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

<><Глава ><4. ><Эвристический ><поиск>< ><173>

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

<>

<2 >< >< >< >< >< >< ><359>< >< >< >< >< >< >< >< ><0 >< >< >< >< >< >< >< ><742>< >< >< >< >< >< >< ><156 ><Рис. ><4.15. ><Минимакс ><в ><гипотетическом ><пространстве ><состояний>

<В ><алгоритме ><минимакса ><существует ><и ><другой ><эффект, ><связанный ><с ><эвристическими ><оценками. ><Оценки, ><которые ><находятся ><очень ><глубоко ><в ><пространстве, ><могут ><не ><>приниматься< ><во ><внимание ><из-за ><их ><большой ><глубины ><[Pearl, ><1984]. ><Подобно ><тому, ><как ><среднее ><произведений ><отличается ><от ><произведения ><средних, ><оценка ><минимакса ><(которую ><мы ><хо­><тим ><получить) ><отличается ><от ><минимаксной ><оценки ><(которую ><мы ><получаем). ><В ><этом ><смысле ><обычно ><(хотя ><и ><не ><всегда) ><лучше ><использовать ><более ><глубокий ><поиск ><с ><оценкой ><состояний ><и ><алгоритмом ><минимакса. ><Детальное ><обсуждение ><этой ><проблемы ><и ><средств ><ее ><решения ><можно ><найти ><в ><[Pearl, ><1984].>

<В ><завершение ><обсуждения ><алгоритма ><минимакса ><представим ><его ><приложение ><к ><игре ><в ><"крестики-нолики" ><(раздел ><4.1), ><описанное ><в ><[Nilsson, ><1980]. ><Здесь ><>используется< ><чуть ><более ><сложная ><эвристика, ><позволяющая ><измерить ><конфликт ><в ><игре. ><Эта ><>эвристика< ><состоит ><в ><следующем. ><Выбирается ><состояние, ><которое ><необходимо ><оценить, ><находятся ><все ><победные ><строки ><для ><МАХ, ><а ><затем ><из ><их ><числа ><вычитается ><общее ><>количество< ><победных ><строк ><для ><Алгоритм ><поиска ><пытается ><максимизировать ><эту ><разность. ><Если ><данное ><состояние ><приводит ><к ><победе ><МАХ, ><то ><оно ><оценивается, ><как ><+?; ><а ><если ><оно ><приводит ><к ><победе ><- ><как ><-?. ><На ><рис. ><4.16 ><показано ><применение ><этой ><эвристики ><к ><нескольким ><состояниям.>

<На ><рис. ><4.17, ><4.18 ><и ><4.19 ><показано ><применение ><эвристики, ><представленной ><на ><рис. ><4.16, ><в ><алгоритме ><двухуровневого ><минимакса. ><На ><этих ><рисунках ><>продемонстрирована< ><эвристическая ><оценка, ><возврат ><на ><основе ><минимакса, ><ход ><МАХ, ><а ><также ><>некоторые< ><ограничения ><на ><ходы ><с ><равными ><эвристическими ><значениями ><[Nilsson, ><1971].>

<><174>

<Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<>

<Рис. ><4.16. ><Эвристика, ><учитывающая ><конфликт ><в ><игре ><"крестики-нолики ><">

<4.3.3. ><Процедура ><альфа-бета-усечения>

<Прямой ><алгоритм ><минимакса ><требует ><двух ><проходов ><по ><области ><поиска. ><Первый ><позволяет ><пройти ><вглубь ><области ><поиска ><и ><там ><применить ><эвристику, ><а ><второй ><- ><присвоить ><эвристические ><значения ><состояниям, ><следуя ><вверх ><по ><дереву. ><Минимакс ><рассматривает ><все ><ветви ><в ><пространстве ><поиска, ><включая ><те ><из ><них, ><которые ><могли ><быть ><исключены ><более ><интеллектуальным ><алгоритмом. ><Разработчики ><игровых ><>стратегий< ><в ><конце ><1950-х ><годов ><создали ><алгоритм ><[Newell ><и ><1976], ><который ><>получил< ><название ><альфа-бета-усечения ><и ><позволил ><повысить ><эффективность ><поиска ><в ><играх ><с ><двумя ><участниками ><[Pearl, ><1984].>

<Идея ><альфа-бета-поиска ><проста: ><вместо ><того, ><чтобы ><рассматривать ><все ><состояния ><некоторого ><уровня ><графа, ><алгоритм ><выполняет ><поиск ><в ><глубину. ><В ><процессе ><поиска ><участвуют ><два ><значения, ><называемые ><альфа ><(alpha) ><и ><бета ><(beta). ><Значение ><альфа, ><связанное ><с ><узлами ><МАХ, ><никогда ><не ><уменьшается, ><а ><значение ><бета, ><связанное ><с ><>узлами< ><никогда ><не ><увеличивается. ><Предположим, ><что ><для ><некоторого ><узла ><МАХ ><значение ><альфа ><равно ><6. ><Тогда ><МАХ ><может ><не ><рассматривать ><состояния, ><которые ><связаны ><с ><нижележащими ><узлами ><и ><имеют ><значения ><меньше ><или ><равные ><6. ><Альфа ><- ><самое ><плохое ><значение, ><которое ><может ><принимать ><МАХ, ><если ><будет ><придерживаться ><"наилучшей" ><стратегии. ><Точно ><так ><же, ><если ><значение ><бета ><для ><узла ><равно ><6, ><то ><не ><следует ><рассматривать ><нижележащие ><вершины ><МАХ, ><с ><которыми ><связаны ><значения ><6 ><или ><более.>

<><Глава ><4. ><Эвристический ><поиск>

<175>

><<>

<Рис. ><4.18. ><Двухуровневый ><минимакс ><и ><один ><из ><двух ><возможных ><вторых ><ходов ><МАХ>

<><176>

<Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<Начиная ><альфа-бета-процедуру, ><мы ><опускаемся ><на ><полную ><глубину ><графа, ><используя ><поиск ><в ><глубину, ><и ><вычисляем ><эвристические ><оценки ><для ><всех ><состояний ><этого ><уровня. ><Предположим, ><что ><все ><они ><- ><узлы ><Максимальное ><из ><этих ><значений ><>возвращается< ><родительскому ><состоянию ><(узлу ><МАХ, ><как ><и ><в ><алгоритме ><минимакса). ><Затем ><это ><>значение< ><передается ><прародителям ><узлов ><как ><потенциальное ><граничное ><значение ><бета.>

<Затем ><алгоритм ><опускается ><к ><другим ><потомкам ><потомков ><и ><не ><рассматривает ><их ><>родительские< ><состояния, ><если ><их ><значения ><больше ><или ><равны ><данному ><значению ><бета. ><>Аналогичные< ><процедуры ><можно ><описать ><для ><альфа-отсечения ><по ><потомкам ><второго ><поколения ><вершины ><МАХ.>

<Существуют ><два ><условия ><останова ><алгоритма ><поиска ><на ><основе ><значений ><альфа ><и ><бета.>

<Поиск ><может ><быть ><остановлен ><ниже ><любого ><узла ><значение ><бета ><которого

><меньше ><или ><равно ><значению ><альфа ><любого ><из ><его ><предков ><МАХ.>

<Поиск ><может ><быть ><остановлен ><ниже ><любого ><узла ><МАХ, ><значение ><альфа ><которого

><больше ><или ><равно ><значению ><бета ><любого ><из ><его ><предков >

<>

<Рис. ><4.19. ><Двухуровневый ><минимакс ><применительно ><к ><ходу ><в ><конце ><игры ><[Nilsson, ><1971]>

<Таким ><образом, ><альфа-бета-усечение ><выражает ><отношение ><между ><узлами ><уровней ><п ><и ><При ><этом ><из ><рассмотрения ><могут ><быть ><исключены ><целые ><поддеревья ><с ><корнями ><на ><уровне ><Например, ><на ><рис. ><4.20 ><изображено ><пространство ><поиска ><из ><рис. ><4.15, ><к ><ко><торому ><применен ><алгоритм ><альфа-бета-усечения. ><Заметим, ><что ><результирующее ><возвра­><щаемое ><значение ><идентично ><полученному ><в ><алгоритме ><минимакса, ><но ><при ><этом ><процеду­><ра ><альфа-бета-усечения ><значительно ><экономичнее ><минимакса.>

<При ><удачном ><порядке ><состояний ><в ><области ><поиска ><процедура ><альфа-бета-усечения ><может ><эффективно ><удваивать ><глубину ><поиска ><в ><рассматриваемом ><пространстве ><при ><фиксированных ><пространственно-временных ><характеристиках ><компьютера ><[Nilsson, ><1980]. ><Если ><же ><узлы ><рас><положены ><неудачно, ><процедура ><альфа-бета-усечения ><осуществляет ><поиск ><в ><таком ><же ><про><странстве, ><как ><и ><обычный ><минимакс. ><Однако ><поиск ><проводится ><только ><за ><один ><проход.>

<><Глава ><4. ><Эвристический ><поиск>

<177>

><<4.4. ><Проблемы ><сложности>

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

<Комбинаторный ><рост ><ошеломляет. ><Было ><показано, ><что ><количество ><состояний, ><просматри><ваемых ><при ><полном ><переборе ><в ><пространстве ><возможных ><шахматных ><ходов, ><составляет ><10><120><. ><Это ><не ><просто ><"очень ><большое ><количество" ><- ><это ><число ><сопоставимо ><с ><числом ><молекул ><во ><вселенной ><или ><с ><числом ><наносекунд, ><прошедших ><после ><"большого ><взрыва".>

<>

<Рис. ><4.20. ><Альфа-бета-усечение ><применительно ><к ><пространству ><со­><стояний ><из ><рис. ><4.15. ><Состояния ><без ><числовых ><меток ><не ><оценивались>

<Были ><предложены ><несколько ><метрик ><для ><вычисления ><сложности. ><Одна ><из ><них ><- ><фактор ><ветвления ><пространства. ><Фактор ><ветвления ><определяется ><как ><среднее ><количест­><во ><ветвей ><(потомков), ><выходящих ><из ><любого ><состояния ><в ><пространстве ><поиска. ><Число ><со><стояний ><на ><глубине ><л ><поиска ><равно ><фактору ><ветвления, ><возведенному ><в ><степень. ><По­><сле ><вычисления ><фактора ><ветвления ><можно ><оценить ><стоимость ><поиска ><пути ><любой ><длины. ><На ><рис. ><4.21 ><показана ><зависимость ><между ><фактором ><ветвления ><Б, ><длиной ><пути ><и ><общим ><количеством ><состояний ><Т ><в ><процессе ><поиска ><для ><малых ><значений. ><Графики ><представлены ><в ><логарифмическом ><масштабе, ><поэтому ><- ><не ><прямая ><линия.>

<Несколько ><примеров ><из ><этого ><рисунка ><показывают, ><как ><плохи ><дела ><на ><самом ><деле. ><Ес><ли ><фактор ><ветвления ><равен ><2 ><(например, ><в ><бинарном ><дереве), ><то ><для ><исследования ><всех ><путей ><на ><шесть ><уровней ><вглубь ><области ><поиска ><требуется ><рассмотреть ><приблизительно ><100 ><состояний. ><А ><для ><углубления ><на ><12 ><уровней ><требуется ><рассмотреть ><около ><10000 ><со><стояний. ><Если ><фактор ><ветвления ><может ><быть ><уменьшен ><до ><1,5 ><(с ><помощью ><эвристики ><или>

<><178>

<Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<переформулировки ><задачи), ><то ><при ><том ><же ><количестве ><рассмотренных ><состояний ><длина ><пути ><может ><быть ><удвоена.>

<Математическая ><формула ><зависимости, ><представленной ><на ><рис. ><4.21, ><имеет ><вид>

<Т= ><В ><+ ><В><2>< ><+ ><3>< ><+…+BL>