Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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

Определение функций в clips

Использование шаблонов.

Наблюдение за процессом интерпретации.

Определение правил.

Правила имеют следующий формат:

(defrule <имя правила>

<необязательный комментарий>

<необязательное объявление>

<предпосылка 1>

….

<предпосылка m>

=>

<действие1>

<действиеn>

)

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

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

Переменные обозначают с префиксом?X

Введем в текстовый файл правило, а затем загрузим этот файл в среду clips.

(defrule start

(Initial-fact)

=>

(printout t “hello, world” crlf)

)

CLIPS>(run)

Если в меню execution-> watch установлен флажок Rules, или в командной строке была введена команда watch rules, то на экране появится результат трассировки процесса выполнения.

CLIPS>(run)

FIRE 1 start: f-0

Hello, world

f-0 имя факта, который удовлетворил условию в этом правиле, команда watch позволяет организовать несколько разных режимов трассировки.

 

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

(deftemplate student “a student record”

(slot name (type STRING))

(slot age (type NUMBER)(default 18)))

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

(deffacts students

(student (name fred)

(student (name freda) (age 19))

)

(deffunction <имяфункции> (<арг1>…<аргn>)

<выражение 1>

<выражение n>

)

(Deffunction hypotenuse (?a?b)

Sqrt(+ (*?a?a)(*?b?b))

)

 

 


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

1. Задание начальных состояний задачи.

2. Задание конечных (целевых) состояний задачи.

3. Задание операторов, преобразующих одни состояния задачи в другие.

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

Достоинством методов слепого поиска является простота алгоритмической реализации и гарантированность получения решения, если оно существует.

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

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

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

В рассматриваемых ниже алгоритмах используются два списка: список открытых вершин (open) и список закрытых вершин (closed). В списке открытых вершин open находятся идентификаторы (имена вершин), подлежащих раскрытию. В списке закрытых вершин (closed) находятся имена вершин, раскрытых к данному моменту и имя вершины, раскрываемой на текущем шаге работы алгоритма.

Методы слепого поиска.

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

Процедура случайного поиска на псевдоязыке:

Procedure Random_Search

Begin

n:=’начальная вершина’;

while n<>’целевая вершина’ do

begin

выбрать случайно оператор, применимый к n;

применить данный оператор к n;

и получить новую вершину n_new;

n:=n_new;

end;

end;

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

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

Поиск в глубину и ширину.

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

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

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

Procedure depth_search

Begin

Поместить начальную вершину в список open;

Closed:=’пустой список’;

While open<>’пустой список’ do

Begin

n:=first(open);

if n=’целевая вершина’ then exit (успех);

переместить n из open в closed;

раскрыть вершину n;

поместить все ее дочерние вершины, отсутствующие в списках open и closed, в начало списка open, связав с каждой дочерней вершиной указатель на n

end;

выход (неудача);

end;

В начале поиска список closed пустой, а open содержит только начальную вершину. Каждый раз из списка open выбирается для раскрытия первая вершина (вызов функции first (open)). Раскрытая вершина перемещается в список closed, а ее дочерние вершины помещаются в начало списка open.

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

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

Следовательно, при поиске в ширину принцип формирования списка open соответствует очереди, то есть вершина, внесенная в список первой, обрабатывается первой. Благодаря этому, фронт поиска растет в ширину, что гарантирует нахождение пути с минимальным количеством дуг (ребер) между исходной и целевой вершиной.

Алгоритм равных цен.

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

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

g(nj)=g(ni)+c(ni,nj), где g(ni) – стоимость пути из начальной вершины в вершину ni.

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

В процессе поиска стоимость пути к вершине может меняться, если обнаруживается более дешевый путь. Поэтому будем обозначать стоимость оптимального пути из начальной вершины в вершину n через g(n), а стоимость текущего пути, найденного алгоритмом, через g^(n). То есть g^(n) – оценка стоимости пути g(n). В конце поиска эти две величины равны.

Процедура поиска оптимального пути (минимальной стоимости):

Procedure Optimal_Search

Begin

Поместить начальную вершину в список open;

Closed:=’пустой список’;

While open<>’пустой список’ do begin

M:=first(open);

If n=’целевая вершина’ then Выход (успех);

Переместить вершину n из списка open в closed;

Раскрыть вершину n;

Для каждой дочерней вершины I вычислить стоимость g^(n, ni);

Поместить дочерние вершины, которых нет в списках open и closed в список open, связав с каждой вершиной указатель на вершину n и положить g^(ni)=g^(n,ni);

Для каждой из дочерних вершин, которые уже содержатся в списке open, сравнить текущую стоимость g^(n, ni) с ранее вычисленным значением стоимости g^(ni), хранящемся в списке open.

Если g^(n, ni)<g^(ni) то установить g^(ni)=g^(n, ni).

Снабдить указанные дочерние вершины указателями на вершину n;

Упорядочить список open по возрастанию стоимости;

End;

Выход (неудача);

End;

В тот момент, когда раскрывается некоторая вершина n, оптимальный путь к этой вершине уже найден, то есть g^(n)=g(n). Иными словами, если вершина уже находится в начале списка open, то для нее невозможно найти более дешевого пути. Следовательно, перевод вершины в список closed является окончательным.

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


Эвристический поиск.

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

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

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

 

Алгоритм подъема на гору.

Алгоритм осуществляет целенаправленный поиск в направлении наибольшего убывания эвристической оценочной функции h^(n). Данная функция обеспечивает оценку (прогноз) стоимости кратчайшего пути от текущей вершины n до ближайшей целевой вершины, то есть является мерой стоимости оставшегося пути. Чем меньше значение оценочной функции, тем более «перспективен» путь, на котором находится вершина N.

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

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

На очередном шаге алгоритма для каждой из дочерних вершин n1, n2,.., nm вершины n вычисляется значение оценочной функции h^(ni) и для продолжения пути выбирается вершина с наименьшим значением оценочной функции. Процедура поиска терпит неудачу, если для всех дочерних вершин выполняется неравенство h^(ni)>h^(n).

Процедура алгоритма на псевдоязыке:

Procedure hill_Climbing

Begin

Ni:=’начальная вершина’;

While n<>’целевая вершина’ do

Begin

Раскрыть вершину n;

Для всех дочерних вершин ni вычислить оценки h^(ni);

Выбрать дочернюю вершину ni с минимальным значением h^(ni)

If h^(ni)>=h^(n) then выход (неуспех)

N:=ni

End

Выход (успех)

End;

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

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

- если в процесс поиска встречается локальные минимумы оценочной функции h^(n);

- если для группы соседних вершин оценки h^(n) равны между собой (проблема Плато);

 

Алгоритм глобального учета соответствия цели.

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

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

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

Процедура поиска, основанная на данном алгоритме, похожа на процедуру Optimal_Search. Отличие состоит в том, что вместо функции стоимости g^(n) применяется оценочная эвристическая функция h^(n), то есть учитываются только предстоящие затраты.

Procedure Best_First_Search;

Begin

Поместить начальную вершину в open;

Closed:=’пустой список’;

While open<>’пустой список’ do

Begin

N:=first(open);

If n=’целевая вершина’ then выход (успех)

Переместить вершину n из open в closed;

Раскрыть вершину n, для каждой дочерней вершины вычислить оценочную функцию h^(ni);

Поместить дочерние вершины, которых нет в списках open и closed, в список open, связав с каждой дочерней вершиной указатель на вершину n;

Упорядочить список open по возрастанию значений h^(n);

End;

Выход (неудача);

End;

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

Эффективность процесс поиска будет оставаться высокой, если оценка стоимости кратчайшего пути h^(n) из вершины n в целевую вершину будет как можно ближе к реальной стоимости h(n).

 

А-алгоритм.

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

Естественным является стремление комбинировать эти алгоритмы и учитывать, как сделанные, так и предстоящие затраты. Этого можно добиться, если воспользоваться оценочной функцией f^(n)=g^(n)+h^(n). Тут g^(n) – оценка стоимости пути из начальной вершины в вершину n, а h^(n) – оценка стоимости кратчайшего пути из вершины n в целевую вершину.

Алгоритм, базирующийся на использовании оценочной функции f^(n), называется А-алгоритмом. Оценки h^(n) в ходе поиска не меняют своих значений, оценки g^(n) также не меняют своих значений и всегда равны реальным затратам g(n), если поиск пути выполняется на дереве состояний. Однако при поиске пути на графе состояний оценки g^(n) могут меняться.

Следовательно, в общем случае оценки f(n) меняют свои значения в процессе поиска. Это приводит к тому, что вершины из списка closed могут перемещаться обратно в список open.

Procedure A_Search;

Begin

Поместить начальную вершину s в список open: f^(s)=h^(s);

Closed:=’пустой список’;

While open<>’пустой список’ do

Begin

N:=first(open);

If n=’целевая вершина’ then выход (успех);

Переместить n из open в closed;

Раскрыть n, для всех ее дочерних вершин ni вычислить оценку f^(n, ni)=g^(n, ni)+h^(ni);

Переместить дочерние вершины, которых нет в списках open и closed, в список open, связав с каждой вершиной указатель на вершину n;

Для дочерних вершин ni, которые уже содержатся в open, сравнить оценки f^(n, ni) и f^(ni),

Если выполниться неравенство f^(n, ni)<f^(ni), то связать с вершиной ni новую оценку из левой части неравенства и указатель на вершину n;

Если вершина ni содержится в списке closed, и выполняется неравенство f^(n, ni)<f^(ni), то связать с вершиной ni новую оценку f^(n, ni), переместить ее в список open и установить указатель на n;

Упорядочить список open по возрастанию f^(ni);

End;

Выход (неудача);

End;

Свойства А-алгоритма.

Если для всех вершин h^(n)=0, то А-алгоритм будет соответствовать алгоритму равных цен. В этом случае гарантируется нахождение оптимального пути, но эффективность поиска будет низкой и если пространство поиска будет бесконечно, то поиск просто неосуществим.

А-алгоритм не дает гарантии, что найденный путь будет оптимальным. Путь может быть не оптимальным в случае, если оценка затрат на пути из вершины n в целевую вершину будет преувеличена (переоценена), то есть если h^(n)>h(n).

Рассмотрим пример.

Граф состояний с переоценкой затрат h(n)

Числа в скобках при вершинах соответствуют оценкам h^(n), а рядом с ребрами – стоимости перехода c(ni, nj). При раскрытии вершины s получаем дочерние вершины a и b. Оценки f^(n) для этих вершин равны: f^(a)=2+4=6, f^(b)=3+5=8. На следующем шаге раскрывается вершина a, и получается f^(g)=7+0=7. Решением будет путь s -> a -> g, который для данного графа не является оптимальным.

А-алгоритм обеспечивает поиск оптимального пути, если выполняется условие: h^(n)<=h(n) (1)

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

Пусть А*1 и А*2 – произвольные гарантирующие алгоритмы, и на всех вершинах h^1(n)>h^2(n). Тогда информированность А*1 выше чем А*2. Говорят, что в этом случае А*1 имеет большую эвристическую силу, чем А*2. Эвристический более сильный алгоритм А*1 в большей степени сокращает пространство поиска.

Если оценка h^(n)=h(n), то информированность является полной. В этом случае никакого поиска не происходит, и приближение к цели идет по оптимальному пути. Таким образом, свойства А-алгоритма существенно зависят от условий, которым удовлетворяет или не удовлетворяет эвристическая часть оценочной функции f^(n):

1. А-алгоритм соответствует алгоритму равных цен, если h(n)=0

2. А-алгоритм гарантирует оптимальное решение, если h^(n)<=h(n). В этом случае он называется А*-алгоритмом.

3. А-алгоритм обеспечивает однократное раскрытие вершин, если выполняется условие монотонности h^(ni)<=h^(nj)+c(ni, nj).

4. Алгоритм А*1 эвристически более сильный, чем алгоритм А*2, если h^1(n)>h^2(n)

5. А*-алгоритм полностью информирован, если h^(n)=h(n).

6. При h^(n)>h(n) А-алгоритм не гарантирует получение оптимального решения. Однако часто решение получается быстро.

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

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

Поиск решений в пространстве состояний – комбинаторная задача. Решение получается на основе перебора всех состояний. Однако для многих практических задач полный перебор невозможен.

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

Если рассматривать дерево состояний, то можно вывести формулу, устанавливающую зависимость общего числа состояний N от степени разветвления B и глубины дерева L: N=B((В в степени L)-1)/(B-1).

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

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

 

Поиск с распространением ограничений.

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

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

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

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

Рассмотрим задачу согласованной разметки, при решении которой анализируется m элементов, пронумерованных от единицы до n.

Предположим, что каждый элемент ni может быть помечен (интерпретирован) несколькими способами. Количество возможных интерпретаций каждого элемента задается числами b1, b2, …, bm.

Если рассматривать возможные интерпретации всей совокупности элементов и проверять их на соблюдение ограничений целостности, то необходимо проанализировать b1*b2*b3…*bm случаев. Хотя данная задача легко представляется в виде графа состояний, целесообразнее перейти к другому представлению – к графу, вершины которого есть элементы ni, а ребра соответствуют бинарным отношениям между соответствующими элементами.

Пусть для каждого из элементов ni, принадлежащих множеству n1,n2,…,nm имеется конечное множество интерпретацией (меток) Li мощностью Gi. Возможность или невозможность согласованной интерпретации двух элементов ni и nj с помощью меток liЭLi и ljЭLj задается бинарным отношением bij.

Если определенная метка li для элемента ni не согласуется с соответствующей меткой lj для элемента nj (то есть не удовлетворяет отношению bij), то данная метка удаляется из множества Li. Аналогичным образом исследуются все метки, входящие во множество Lj.

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

Рассмотрим пример согласованной разметки вершин графа, изображенного на рисунке.

 
 

 


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

Рассмотрим множества совместимых меток для вершин N1 и N2 при ограничении l1+l2=8. Сначала при заданном множестве L1={1,3,4,5,6} удалим из L2 все метки, не удовлетворяющие указанному условию. В данном случае отношение b12 выполняется для всех меток из L2, за исключением метки 6. Следовательно, данная метка удаляется, и L2={3,4,5,7}. Затем отношение b12 используется для проверки множества меток L1. В этом случае из L1 также удаляется метка 6, и множество L1={1,3,4,5}.

Таким образом, мы сначала распространили ограничение b12 из вершины n1 в вершину n2, а затем обратно, из n2 в n1, удаляя соответствующие метки из множеств L2 и L1. Метки, входящие во множества L2 и L1, теперь согласованы.

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

Распространив ограничение от n1 к n3 и от n2 к n3, получим L3={1,3,5}. Затем соответствующие ограничения распространяются в обратную сторону, при этом множества L2 и L1 не изменяются. Аналогичные операции выполняются с вершиной n4. В итоге L4={3,4}, L2={4,5}, L3={3,5}.

Затем ограничения распространяются между n2 и n3. Это дает L3={3}, а также от n2 и n3 к n1. Получаем L1={3,4}. Распространяя ограничения обратно от n1 к n2, n3 и n4, получаем окончательный результат l1=4, l2=4, l3=3, l4=2.

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

Очевидно, в этом случае задача имеет несколько решений.

 


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

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

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

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

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

2) Расширяют потенциальный подграф решений.

В ходе выполнения первого действия проверяет все концевые вершины потенциального подграфа. Если эти вершины соответствуют элементарным задачам, решение которых известно, то они считаются заключительными и помечаются меткой solved (разрешимые). Если концевые вершины являются тупиковыми, то они помечаются как неразрешимые (unsolved). Затем анализируются их родительские вершины.

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

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

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

Аналогично поиску в пространстве состояний, при поиске в пространстве редукций задачи выделяют алгоритмы слепого и упорядоченного (эвристического) поиска.


<== предыдущая лекция | следующая лекция ==>
Разработка экспертных систем средствами CLIPS | Поиск решений в игровых программах
Поделиться с друзьями:


Дата добавления: 2014-01-06; Просмотров: 1324; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.134 сек.