Способы решения задач искусственного интеллекта

Размещено на http://www.allbest.ru/

Общие способы решения задач

Процесс решения задачи, как правило, включает два этапа: представление задачи и поиск (перебор). Успех решения задачи в значительной мере определяется формой ее представления. Формы представления задачи могут быть различными и зависят как от природы самой задачи, так и от ее решателя.

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

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

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

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

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

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

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

Из изложенного ясно, что представление задачи определяется совокупностью трех составляющих - тройкой (S₀,F,G), где S₀ - множество начальных состояний, F - множество операторов, отображающих одно состояние в другое, G - множество целевых состояний.

Пример. Задача о выборе маршрута, или задача о коммивояжере.

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

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

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

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

Введем понятия теории графов. Графом (или геометрическим графом) называется геометрическая конфигурация, состоящая из множества V точек, взаимосвязанных с множеством E непрерывных, самонепересекающихся кривых. Точки из множества V называются вершинами, кривые из множества E - ребрами. Если на всех ребрах задано направление, то граф называют ориентированным графом, а его ребра - дугами.

Если заданы два графа G₁ и G₂, причем множества вершин и кривых графа G₂ являются подмножествами множеств вершин и кривых G₁, то G₂ называют подграфом графа G₁, G_{1 -} надграфом графа G₂.

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

Вершины V_i порождаются вершиной V. V - родительская вершина, а V_i - дочерние вершины.

Примем, что корень находится на 0 уровне. Вершины, порожденные корнем, - 1 уровень и т.д.

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

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

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

Задача A может быть решена, если будут решены задачи B и C или задача D. Задача B будет решена, если будут решены задачи E или F. Задача C - если решена G. Задача D - если решены задачи H и I.

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

Будем рассматривать только такие деревья редукции.

Структурно граф (дерево) редукции задачи отличается от графа (дерева) состояния тем, что в нем имеются связанные дуги. Связанные вершины называют И-вершинами, несвязанные - ИЛИ-вершинами, а граф называется графом типа И-ИЛИ.

Вершины, соответствующие элементарным задачам называются заключительными.

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

Таким образом, заключительные вершины являются разрешимыми, а тупиковые - неразрешимыми.

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

Очевидно, задача A является разрешимой в том и только в том случае, если вершины H и I являются заключительными или заключительными являются вершины G и F или G и E.

Граф редукции задачи может быть задан в явном виде (на рис. 3.2). Но чаще он, как и граф состояния, задается в неявном виде посредством описания исходной задачи и операторов редукции.

Представление задачи в виде теоремы. Многие задачи (логического типа и другие) могут быть сформулированы как теоремы, подлежащие доказательству. К доказательству теорем могут быть сведены головоломки, игровые задачи, а также ряд практических задач, таких как принятие решений, планирование действий.

Поиск решений в пространстве состояний

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

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

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

Для построения дерева состояния следует, используя операторы из F, применимые к корню дерева (начальное состояние), построить вершины 1-го уровня. Затем, используя операторы из F, применимые к вершинам 1-го уровня, построить вершины 2-го уровня и т.д. Процесс применения операторов к какой-либо вершине дерева для построения всех ее дочерних вершин называется раскрытием вершин. Поэтому операторы преобразования мира (операторы из F) интерпретируются как правила раскрытия вершин. Применение правил раскрытия к начальной вершине порождает совокупность дочерних вершин. Каждая из них соответствует некоторому состоянию мира, в которое он может перейти из начального состояния. Дуги, связывающие начальную вершину с дочерней, идентифицируют как соответствующие операторы преобразования. Для всех дочерних вершин производится проверка, не являются ли они целевыми, т.е. не соответствуют ли целевым состояниям. Если целевая вершина не обнаружена, то выполняется следующий этап порождения вершин путем применения правил раскрытия к каждой вершине, порожденной на предыдущем этапе… Процедура продолжается до обнаружения целевой вершины.

Рассмотрим процедуру построения графа состояний на примере выбора маршрута транспортным роботом, который должен, выйдя из склада (пункт A), обойти обрабатывающие центры (пункты B,C,D) и вернуться в склад. Запрещается, чтобы робот побывал в каком-либо из обрабатывающих центров более одного раза. Схема маршрутов и расстояние между пунктами представим на рис.3.3.

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

Операторы (или правила раскрытия) в данном примере соответствуют выбору того или иного маршрута.

На графе состояний этой задачи начальной вершине (корню дерева) соответствует состояние A. Корень дерева порождает три дочерние вершины, соответствующие состояниям AB,AC,AD. Каждая из вершин, порожденных корнем, порождает по две вершины, и каждая из вершин 2 и 3 уровней - по одной. На дугах указаны расстояния, которые проходит робот при переходе из одного состояния в другое.

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

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

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

Для структурированной записи алгоритмов поиска в пространстве состояний введем понятия списков "открытых" и "закрытых" вершин. Список "закрытых" вершин - это список, где размещаются идентификаторы "раскрытых" и идентификатор вершины, которую предстоит раскрыть, в данный момент. Вершины из списка "закрыт", кроме последней раскрывать нельзя.

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

В структуризованном виде алгоритм полного перебора можно представить следующим образом:

1) поместить начальную вершину в список "открыт";

2) если список "открыт" пуст, то подать сигнал о неудаче поиска, в ином случае перейти к следующему шагу;

3) взять первую вершину из списка "открыт" и перенести ее в список "закрыт"; присвоить вершине идентификатор v;

4) раскрыть вершину v. Поместить все дочерние неповторяющиеся (т.е. не встречающиеся в списке "закрыт") вершины в конец списка "открыт" и построить указатели, ведущие от них к вершине v. Если вершина v не имеет дочерних вершин или имеет только повторяющиеся дочерние вершины, то перейти к шагу 2;

5) проверить, не является ли одна из дочерних вершин v целевой. Если является, то выдать решение; в ином случае перейти к шагу 2.

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

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

Рассмотрим алгоритм перебора в глубину в структуризованном виде:

1) поместить начальную вершину в список "открыт";

2) если список "открыт" пуст, то выдается сообщение о неудаче, в ином случае перейти к шагу 3;

3) взять первую вершину из списка "открыт" и перенести в список "закрыт". Этой вершине присвоить идентификатор v;

4) если глубина вершины v равна граничной глубине, то перейти к 2, в ином случае к 5;

5) раскрыть вершину v. Поместить все дочерние вершины в начало списка "открыт" и построить указатели, идущие от них к вершине v. Если v не имеет дочерних вершин, то перейти к шагу 2;

6) если одна из этих вершин целевая, то на выход выдать решение, получаемое путем просмотра назад в соответствии с указателями, в ином случае перейти к шагу 2;

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

Во всех рассмотренных алгоритмах перебора предполагается, что начальная вершина только одна. Если начальных вершин несколько, то эти алгоритмы изменяются на шаге 1: на шаге 1 в список "открыт" помещаются все начальные вершины.

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

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

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

Пусть g(v) - стоимость кратчайшего (оптимального) пути из любой начальной вершины s₀IS₀ до некоторой вершины v. Стоимость кратчайшего пути из вершины v до ближайшей целевой вершины g₀IG обозначим h(v).

Функция f(v) = g(v) + h(v), очевидно, выражает стоимость кратчайшего (оптимального) пути из начальной вершины в целевую при условии, что он проходит через вершину v. Введем в рассмотрение следующие оценочные функции: g(v) - оценка стоимости кратчайшего пути из начальной вершины в вершину v; h(v) - оценка стоимости кратчайшего пути из вершины v до ближайшей целевой.

Тогда функция:

f?(v) = g(v) + h(v)

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

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

Пусть на шаге 1 поиска раскрыта вершина S₀ и порождены вершины v₁ и v₂ со значениями стоимостей g(v₁)=3, g(v₂)=7.

На шаге 2 раскрывается вершина v₁ и порождается вершина v₃ и снова вершина v₂, причем из v₁ в v₂ ведет путь стоимостью g(v₁)=3. Очевидно, стоимость кратчайшего пути из S₀ в v₂будет g(v₂)=6.

Необходимо заметить, что g(v)?g(v). Это видно и из примера. Эта оценочная функция легко вычисляется в процессе работы алгоритма.

Определение оценочной функции h(v) является более сложной задачей. При ее построении опираются на любую эвристическую информацию о решаемой задаче, поэтому h(v) называют эвристической функцией. Очевидно, если h(v)=0, то алгоритм перебора сводится к алгоритму равных цен, что соответствует полному отсутствию эвристической информации. Не существует каких-либо конструктивных рекомендаций к способам определения этой функции, поэтому рассмотрим ее смысл на примере. Конкретизируем задачу преобразования сцен (задачу о манипуляции предметами) следующим образом.

Пример. Пусть состояние, или, как принято говорить, мир задачи включает некоторое число площадок с расположенными на них кубиками (в реальной задаче вместо кубиков могут рассматриваться детали, из которых необходимо собрать изделие), а также робот манипулятор, перемещающий кубики с одной площадки на другую и устанавливающий их друг на друга. Текущее состояние такого мира можно интерпретировать как текущее расположение кубиков на площадках и положение манипулятора. Совокупность всех возможных состояний образует множество S. Очевидно, способы перемещения кубиков роботом, т.е. переход от одного состояния к другому, должны быть подчинены некоторым требованиям. Так, может быть ограничено число кубиков на конкретной площадке. Для перемещения естественно выбирать кубики, лежащие сверху и т.д. На основе таких требований строится множество F допустимых операторов преобразования мира, которые фактически являются совокупностью разрешенных действий робота. Желаемое расположение кубиков на площадках есть целевое состояние мира, решением задачи является последовательность действий робота (цепочка операторов F₁, …, F₂), с помощью которой можно переставить кубики из некоторого начального расположения (начальное состояние мира) в желаемое, т.е. целевое состояние.

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

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

Граф решения задачи с помощью алгоритма упорядоченного перебора при указанной эвристической функции приведен на рис 3.5.

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

f?(v)=g(v)+h(v).

Они являются гарантирующими, если для всех вершин v выполняется условие h(v)?h(v) и стоимости всех дуг превосходят некоторое минимальное число.

Для сравнения эффективности алгоритмов перебора используется понятие эвристической силы. Пусть A₁ и A₂ - произвольные гарантирующие алгоритмы перебора, а

f₁ = g(v)+h₁(v) и

f₂ = g(v)+h₂(v)

- используемые ими оценочные функции. Алгоритм A₁ называют эвристически более сильным, чем алгоритм A₂, если на всех вершинах, кроме целевой, выполняется неравенство h₁(v)>h₂(v). Эвристически более сильный алгоритм A₁ раскрывает меньшее число вершин при поиске минимального пути, чем алгоритм A₂.

Обозначим B множество гарантирующих алгоритмов, которые можно использовать для решения данной задачи. Алгоритм A^*IB называется оптимальным, если он не раскрывает большее число вершин, чем любой другой алгоритм AIB. решение задача пространство состояние

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

Поиск решений при сведении задач к подзадачам

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

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

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

Вершина неразрешима, если она является тупиковой или если неразрешимы все ее дочерние вершины, когда они связаны отношением ИЛИ, или хотя бы одна из дочерних вершин, когда они связаны отношением И. Редукция (раскрытие вершин) заканчивается, если устанавливается разрешимость или неразрешимость начальной вершины.

Как и при поиске в пространстве состояний различают методы слепого и упорядоченного перебора на графе редукции [26,28].

Алгоритм полного перебора. В методе полного перебора вершины раскрываются в том порядке, в котором они строятся. Алгоритм полного перебора при поиске решающего графа имеет специфику, обусловленную процедурами проверок, являются ли вершины разрешимыми или неразрешимыми. Он формируется следующим образом:

1) поместить начальную вершину S₀ в список ОТК;

2) взять первую вершину из списка ОТК и поместить ее в список ЗКР; обозначить эту вершину через v;

3) раскрыть вершину v и поместить все ее дочерние вершины в конец списка ОТК и провести от них указатели к вершине v. Если дочерних вершин не оказалось, то поместить вершину как неразрешимую и перейти к следующему шагу; в ином случае перейти к шагу 7;

4) применить к дереву поиска процедуру разметки неразрешимых вершин;

1) если начальная вершина помечена как неразрешимая, то выдать результат о неудаче; в ином случае перейти к следующему шагу;

2) изъять из списка ОТК все вершины, имеющие неразрешимые предшествующие им вершины, и перейти к шагу 2;

3) если дочерние вершины являются связанными, то перейти к следующему шагу; в ином случае перейти к шагу 9;

4) если все дочерние вершины являются заключительными, то поместить v как разрешимую и перейти к 10, в ином случае - как неразрешимую и идти к шагу 4;

5) если хотя бы одна дочерняя вершина является заключительной, то поместить как разрешимую, и идти к 10, иначе - как неразрешимую и перейти к 4;

6) произвести разметку разрешимых вершин;

7) если дочерние вершины являются связанными, то перейти к следующему шагу; в ином случае перейти к шагу 9;

8) если все дочерние вершины являются заключительными, то поместить v как разрешимую и перейти к 10, в ином случае - как неразрешимую и идти к шагу 4;

9) если хотя бы одна дочерняя вершина является заключительной, то поместить как разрешимую и идти к 10, иначе - как неразрешимую и перейти к 4;

10) произвести разметку разрешимых вершин;

11) если начальная вершина помечена как разрешимая, то выдать дерево решения; в ином случае перейти к следующему шагу;

12) изъять из списка ОТК все вершины, являющиеся разрешимыми или имеющие разрешимые предшествующие им вершины, и перейти к шагу 2.

Рис. 3.6 - это пример поискового дерева редукции задачи, на вершинах которого приведены цифры, указывающие последовательность раскрытия вершин при использовании алгоритма полного перебора. Заключительные вершины помечены буквой Z. Дерево решения выделено жирной линией. Вершины A и B не раскрыты, т.к. являются тупиковыми. Вершины C и D могут быть не тупиковыми и не заключительными, но они не раскрыты, т.к. после раскрытия вершины 10 найдено решающее дерево и алгоритм полного перебора прекращает работу.

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

1) поместить начальную вершину S₀ в список ОТК;

2) взять первую вершину из списка ОТК и поместить ее в список ЗКР; обозначить эту вершину через v;

3) если глубина вершины v равна граничной глубине, то отметить вершину v как неразрешимую и перейти к шагу 5; в ином случае перейти к следующему шагу;

4) раскрыть вершину v. Поместить все дочерние вершины (в произвольном порядке) в начало списка ОТК и провести от них указатели к вершине v. Если дочерних вершин не оказалось, то пометить вершину v как неразрешимую и перейти к следующему шагу, в ином случае перейти к 8;

5) применить к дереву поиска процедуру разметки неразрешимых вершин;

6) если начальная вершина помечена, как неразрешимая, то выдать результат о неудаче; в ином случае перейти к следующему шагу;

7) изъять из списка ОТК все вершины, имеющие неразрешимые предшествующие им вершины. Перейти к шагу 2;

8) если все дочерние вершины являются связанными, то перейти к следующему шагу; в ином случае перейти к шагу 10;

9) если все дочерние вершины являются заключительными, то пометить v как разрешимую и перейти к 11, иначе - как неразрешимую и идти к 5;

10) если хотя бы одна дочерняя вершина является заключительной, то пометить v как разрешимую, и идти к 11, иначе - как неразрешимую и перейти к 5;

11) применить к дереву перебора процедуру разметки разрешимых вершин;

12) если начальная вершина помечена как разрешимая, то выдается дерево решения; в ином случае перейти к следующему шагу;

13) изъять из списка ОТК все вершины, являющиеся разрешимыми или имеющие разрешимые предшествующие им вершины и перейти к шагу 2.

На рис 3.7 приведено поисковое дерево редукции задачи, которое строится при переборе в глубину с граничной глубиной, равной 4. Жирной линией выделено решающее дерево. Цифры на вершинах указывают на последовательность, в которой раскрываются вершины. Вершина F не раскрыта, хотя она не является ни тупиковой, ни заключительной и не достигла граничной глубины, т.к. до наступления момента ее раскрытия становится известным, что предшествующая ей вершина 2 разрешима и в соответствии с шагом 11 она изымается из списка ОТК. Вершина G не раскрыта, т.к. решающее дерево найдено.

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

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

Эвристические методы поиска (перебора). Для упорядочивания раскрываемых вершин на дереве типа И-ИЛИ используется так называемое оптимальное потенциальное дерево решения, для выделения которого применяется эвристическая функция. При поиске решения в пространстве состояний эвристическая функция определялась как оценка стоимости оптимального пути от заданной вершины до целевой. В деревьях типа И-ИЛИ для ее определения используется оценка стоимости дерева решения.

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

Если стоимость дуг равна единице, то суммарная стоимость равна числу дуг в дереве решения, а максимальная стоимость - числу дуг в пути между двумя самыми отдаленными вершинами дерева решения.

Дерево решения, имеющее минимальную стоимость (суммарную или максимальную в зависимости от того, какая из них принята за критерий оптимальности), называется оптимальным.

Обозначим h(S₀) - стоимость оптимального дерева решения с корнем в начальной вершине S₀, а h(v) - минимальную стоимость дерева решения (поддерева дерева решения) с вершиной в точке v. Стоимость h(v) можно определить следующим образом (рекурсивное определение):

1) если v - заключительная вершина, то h(v)=0;

2) если v - не заключительная вершина и имеет несвязанные дочерние вершины (вершины типа ИЛИ) v₁,v₂,…,v_k, то, где c(v,v_i) - стоимость дуги между вершинами v и v_i .

Если v - не заключительная вершина и имеет связанные дочерние вершины v₁,…,v_k, то суммарная и максимальная стоимости определяются соответственно формулами.

Эвристическая функция. Так называется функция, являющаяся оценкой минимальной стоимости. Рассмотрим, как может быть построена эвристическая функция. Дерево поиска, которое строится в ходе процесса перебора, на каждом этапе задачи, пока не закончено построение дерева редукции, обладает вершинами, не имеющими построенных дочерних вершин. Такие вершины называются концевыми. Они могут быть заключительными, тупиковыми и нераскрытыми, т.е. вершинами, для которых на рассматриваемом этапе еще не построены дочерние вершины. Если для концевых вершин v - заключительная вершина, то =0; если v - нераскрытая вершина, то строится как оценка функции h(v) на основе эвристической информации, связанной с исходной задачей.

Для не концевых вершин эвристическая функция строится так:

- если v имеет несвязанные дочерние вершины v₁,…,v_k, то,

- если v имеет связанные дочерние вершины v₁,…,v_k, то эвристические функции для суммарной и максимальной стоимостей определяются соответственно формулами:

Эвристический алгоритм упорядоченного перебора. В дереве поиска содержится множество поддеревьев с корнем в начальной точке, каждое из которых могло бы быть начальной частью дерева решения. Эти поддеревья называют потенциальными деревьями решения. Потенциальное дерево решений D₀ назовем оптимальным в том случае, когда оно обладает следующим свойством: если у вершины v, входящей в дерево D₀, в дереве перебора имеются связанные дочерние вершины, то все они входят в дерево D₀; если у этой вершины в дереве перебора имеются несвязанные дочерние вершины v_i (i=1,…,k), то в дерево D₀ входит та из них, для которой значение минимально.

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

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

Поместить начальную вершину в список ОТК и вычислить (S₀).

Выделить оптимальное потенциальное дерево решений D_0.

Выбрать некоторую концевую вершину дерева D_0, которое имеется в списке ОТК, и поместить в список ЗКР. Обозначить эту вершину через v.

Если v - заключительная вершина, то пометить ее как разрешимую и перейти к следующему шагу. В ином случае перейти к шагу 8.

Применить к дереву D₀ процедуру разметки разрешимых вершин.

Если начальная вершина помечена как разрешимая, то выдать дерево D₀ в качестве дерева решения; иначе перейти к следующему шагу.

Изъять из списка ОТК все вершины, имеющие разрешимые предшествующие им вершины, и перейти к шагу 2.

Раскрыть вершину v. Если дочерних вершин она не имеет, то пометить ее как неразрешимую и перейти к следующему шагу; в ином случае перейти к шагу 12.

Применить к дереву D₀ процедуру разметки неразрешимых вершин.

10. Если начальная вершина помечена как неразрешимая, то выдать результат о неудаче; в ином случае перейти к следующему шагу.

11. Изъять из списка ОТК все вершины, имеющие неразрешимые предшествующие им вершины, и перейти к шагу 2.

12. Поместить все дочерние вершины в список ОТК и провести от них указатели назад к вершине S. Вычислить величины для этих вершин. Пересчитать величины для вершины v и для предшествующих ей вершин.

13. Перейти к шагу 2.

Размещено на Allbest.ru

...