Стоимость деревьев типа И-ИЛИ

Для эвристического поиска в деревьях И-ИЛИ вводится понятие стоимости такого дерева. Дерево минимальной стоимости, содержащее дерево решений будем называть оптимальным деревом решений.

Через h(S) обозначим минимальную стоимость дерева решений с корнем в начальной вершине S. Через h(n) обозначим минимальную стоимость поддерева с корнем в вершине n. - стоимость дуги между вершинами и .

Стоимость дерева определяется рекурсивно. Стоимость заключительной вершины равно нулю.1) h(n)=0 - заключительная

2) Для вершин типа ИЛИ. 3) Для вершин типа И. .

Введём оценочную функцию для каждой вершины . Для неё справедливы все 3 соотношения, что и для h(n). определяется из некоторой эвристической информации.

Согласно оценкам на каждом шаге перебора можно посчитать верхнюю часть минимального дерева решений. Эту часть будем называть потенциальным деревом решений и обозначать t ₀. Потенциальное дерево решений можно определить следующим образом:1) Начальная вершина входит в t ₀.2) Если у вершины, принадлежащей t ₀ есть порожденные ИЛИ вершины, то в входит та из них, для которой минимально значение .3) Если у вершины n, принадлежащей t ₀ есть порождённые И вершины, то все они входят в t ₀.

ПРИМЕР:

Будем предполагать, что известно правило, по которому можно определить, какую из концевых вершин дерева t ₀ нужно раскрывать следующей. Цена дуг в данном примере равно единице. Известны оценочные функции для концевых вершин. Изобразим потенциальные деревья решений. Для деревьев И-ИЛИ справедлива следующая теорема.ТЕОРЕМА: Если значение h(n) для любой раскрытой вершины n в ходе поиска и стоимости всех дуг не превосходят некоторую величину d <0, то алгоритм упорядоченного перебора в вершинах И-ИЛИ допустим, т.е. обеспечивает поиск оптимального решения. При этом оптимальность алгоритма не доказана (число шагов не минимально).

8. Алгоритм упорядочения перебора при сведении задач к подзадачам

Алгоритм упорядоченного перебора в деревьях И-ИЛИ:

1) Помещаем начальную вершину в список OPEN и вычисляем значение

2) Получаем дерево t₀ используя значения

3) Выбираем вершину дерева t₀ из OPEN, помещаем её в CLOSED и обозначаем через n.

4) Если n заключительная вершина, то помечаем её, как разрешимую и продолжаем. Иначе переходим к п.9.

5) Применяем к t₀ процедуру разметки разрешимых вершин.

6) Если начальная вершина помечена, как разрешимая, то выход с деревом t₀.

7) Изъять из OPEN все вершины, имеющие предшествующие разрешимые вершины.

8) Перейти к п.2.

9) Построить все порождённые вершины для n. Если порожденных нет, то пометить вершину, как неразрешимую. Иначе перейти к п.14.

10) Применить к t₀ процедуру разметки на неразрешимость.

11) Если начальная вершина неразрешима, то решений нет.

12) Изъять из OPEN все вершины, которые имеют предшествующие неразрешимые вершины.

13) Перейти к п.2.

14) Поместить все порождённые вершины в OPEN и установить указатели на n. Вычислить значения для порождённых вершин и пересчитать для всех предшествующих вершин.

15) Перейти к п.2.

Выбор вершины в t₀ для очередного раскрытия:

Если t₀ на самом деле есть частью дерева с минимальной стоимостью, то безразлично, какую вершину в списке OPEN раскрывать первой, т.к. все они должны быть раскрыты.

Если t₀ не является деревом с минимальной стоимостью, то в первую очередь следует раскрывать ту вершину, которая быстрее обнаружит ошибку. Обычно это вершина с наибольшим .

Для деревьев типа И-ИЛИ нет утверждений, аналогичных пространству состояний. Вместе с тем интуитивно понятно, что чем лучше функция аппроксимирует h (истинную величину), тем потенциальное дерево t₀ будет ближе к дереву минимальной стоимости.

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

9. Особенности поиска решений в игровых задачах

Многие игры, особенно с двумя противниками, можно представить в виде деревьев И-ИЛИ, если ходы игроков чередуются.

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

В сложных играх полный перебор ходов невозможен из-за комбинаторного взрыва. В крестиках-ноликах 3х3 возникает 9! вариантов. В шашках 10⁴⁰, в шахматах 10¹²⁰.

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

При этом в большинстве случаев перебор не заканчивается решением, а ограничивается в глубину и в ширину.

Лучший ход обычно выбирают исходя из статической оценочной функции, которая оценивает каждую рассмотренную позицию, начиная с концевых вершин.

Для первого игрока оценочная функция считается положительной, для противника - она отрицательна. При оценке лучшего хода применяется минимаксная процедура - лучший ход среди худших.

Для крестиков-ноликов оценочной функцией будем считать разность между числом открытых линий для крестика и числом открытых линий для нолика.

L(P)=K(P)-0(P)

Для выигрышных позиций L(P)= +¥

Для проигрышных позиций L(P)= -¥

При построении порожденных вершин будем учитывать симметрию.

Для поиска лучшего хода применяется минимаксная процедура:

Если первому игроку нужно выбрать лучший ход, то он выбирает тот ход, который соответствует вершине с наибольшей оценкой, следовательно вершинам типа И приписываются оценочные функции, равные максимуму оценок концевых вершин. Если ход выбирает второй игрок, то он выбирает вершину с наименьшей оценкой, т.к. все оценки выбираются с точки зрения первого игрока. Таким образом для вершины типа ИЛИ приписывают минимум оценок концевых вершин, после этого процесс переносится на уровень выше. Такое прослеживание продолжается до вершин, порожденных начальной вершиной. Значения оценочных функций, которые приписываются промежуточным вершинам называются обращёнными величинами. Первый игрок выбирает лучший ход, который соответствует порождённой вершине с наибольшей обращённой величиной.

ПРИМЕР:

Глубина просмотра равна двум.

10. " " процедура в игровых задачах

В минимаксной процедуре процесс перебора отделён от оценок позиций. Оценки производятся только после построения дерева решений. Можно добиться существенного снижения объёма перебора, если оценки вести одновременно с построением дерева решений.

После того, как найден выигрышный ход для второго игрока, процесс перебора в И-вершине можно не продолжать. Можно не продолжать раскрытие и тех И-вершин, для которых текущие оценки меньше уже полученных до этого И-вершин.

Для ИЛИ-вершин статическая оценочная функция не может увеличиваться. Не раскрываются дальше те вершины, для которых оценочная функция больше, чем уже полученная раннее оценочная функция соседней ИЛИ-вершины.

Предварительные оценочные функции для И-вершин называются a -величинами. Для вершин ИЛИ - b -величинами. Прекращение перебора в связи с нарушением неравенства называются, соответственно, a или b отсечениями. Весь процесс- a b -процедурой. Называется обратным усечением дерева решений.

Правила a b -процедуры:

1)Перебор можно прекратить ниже любой ИЛИ-вершины, для которой оценочная величина не больше, чем оценочная величина предшествующей И-вершины.

2) Можно прервать перебор ниже любой И-вершины, оценочная функция которой не меньше, чем оценочная функция предшествующей ИЛИ-вершины.

Минимаксную процедуру можно улучшить, если к обращённым величинам для И-вершин добавить фиксированное значение и эту же фиксированную величину вычесть из обращённых величин ИЛИ-вершин. При этом увеличивают оценки только тех И-вершин, в которых есть несколько хороших вершин, а уменьшают оценки тех ИЛИ-вершин, для которых есть несколько плохих порождённых вершин.

a b -процедура не приводит к потере лучших ходов, т.е. она даёт тот же результат, что и минимаксная процедура.

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

Обычно в играх двух игроков применяют две формы обучения: накопление и обобщение.

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

Обобщение позволяет в процессе игры учитывать статическую оценочную функцию. Сложная статическая функция обычно оценивается аддитивным критерием:

S=k1a1+k2a2+…+knan

Где а1,…,аn - значения критериев; k1,…,kn - весовые коэффициенты.

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

Оценка эффективности ab -отсечения.

Эффективность a b -процедуры оценивается числом отсечённых вершин.

Пусть дерево перебора имеет глубину D, и у каждой вершины есть В порождённых вершин. Тогда дерево будет иметь BD концевых вершин. Предположим, что в a b -процедуре истинных оценок, для ИЛИ-вершин максимальное количество, а в И-вершинах - минимальное. Такой порядок максимизирует число отсечений. Тогда лучший перебор определяется числом порожденных вершин.

Эффективность a b - отсечений оценивается параметром n:

где N - общее число раскрытых вершин для одного хода.

11. Системы искусственного интеллекта на основе решателей задач

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

Впервые такая система возникла в 70-е годы.

Основные компоненты решателя:

- формализованный язык описания проблемы;

- формализованная база знаний – правила описания действий;

- методика решения задач.

GPS (General Problems Solver). Авторы - Ньюэл и Саймон.

В основу программы положены 2 основных принципа:

1) Анализ цели и средства.

2) Рекурсивное решение задач.

Алгоритм решения:

1) анализ текущей ситуации;

2) сравнение с целевой;

3) выбрать среди множества операторов оператор для уменьшения разницы между текущим и целевым состоянием;

4) применить оператор;

5) перейти к началу.

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

В процессе решения возникают 3 задачи:

1) Преобразование объекта А в объект В вследствие применения оператора.

2) Уменьшение различий между объектами А и В.

3) Применение оператора к некоторому объекту.

Существует разбиение исходной задачи на подзадачи. Программа позволяет решать следующие проблемы:

1) Символьное вычисление интегралов.

2) Задачи логического вывода.

3) Решение игровых задач для двух игроков с противоположными целями.

4) Грамматический разбор предложений.

STRIPS (Stanford Research Institute Problem Solver) Авторы - Файке, Харт, Нильсон.

Генерирует план решения задачи методами усечения дерева решений и путём обобщения уже решённых задач.

Программа является частью управляющих программ для самоходного робота. Вся система включает 4 составляющие:

1) Аппарат перемещения.

2) Сенсорная система: телекамера и детектор касания.

3) Компьютер для анализа сигналов.

4) Систему управления (под действием компьютерных команд).

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

Развитием системы стала система ABSTRIPS, которая отличается иерархическим планированием решения - разбиение на подзадачи. Концевыми задами являются накопленные планы решения.

Система ПРИЗ (Программа Решения Интеллектуальных Задач).

Автоматически генерирует головную программу для решения вычислительных задач из готовых программных модулей.

Для описания задачи применяется декларативный язык УТОПИСТ. Автор – Тыугу

12. Решение задач, как док-во теорем, теоремы ограничений на доказательство.

Формальные системы - это совокупность абстрактных объектов в которой представлены правила оперирования множеством символов синтаксической трактовки без учёта семантики, т.е. смысла. Формальная система считается заданной, если известны следующие составляющие:1) Задан некоторый конечный алфавит (множество символов), или словарь.2) Определена процедура построения формул системы - слова и фразы.3) Задано некоторое множество формул, которые являются аксиомами.

4) Задано конечное множество правил вывода, которое позволяет из одного множества формул получит получить другое множество формул. U_1Ù U₂ Ù …Ù U_n ® W_1Ù W₂ Ù …Ù W_n

Формальную систему иногда называют формальной теорией.Алфавит иногда называют словарем.

Различают константы, переменные и операторы. Например в алгебре константы 1,2,3,4,...; переменные x, y, z,...; операторы +, -, =,

Способ построения формул называется грамматикой.

Формальным доказательством называется конечная последовательность формул, такая, что каждая формула либо есть аксиомой, либо получена из предшествующей формулы путём применения правила вывода.

Формула t называется теоремой, если существует доказательство, в котором она является последней.

Всякая аксиома есть теорема.Теорема обозначается ├ (читается "по t").{Теорема}Ì {Формула}Ì {Цепочка символов}

Правила вывода позволяют определить, является ли данная формула теоремой.Существует 2 типа правил вывода:

1) Правила продукции. Применяется к формулам в целом.

2) Правила переписывания. Применяются к любой части формулы.

Правила продукции обозначаются значком ® (читается "влечёт")x< yÙ y< z ® x< z

Правила переписывания обозначаются a x-x a 0

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

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

Интерпретацией называется распространение утверждений формальной системы на реальный мир.

В случае, когда положения теоремы интерпретируются, говорят об их истинности либо ложности.

Одна и та же формальная система может служить интерпретацией для различных процессов. Т - теорема.NT - не теорема.V - истина.F - ложь. Наиболее сложным случаем является третий. Второй исключается из системы. Первый - интерпретация существует. Четвёртый - доказано, что утверждение не теорема - выражение важное и полезное, но не всегда возможное.

Поиск по сайту: