23659

Стратегии поиска в СОЗ

Лекция

Информатика, кибернетика и программирование

7 Начальныесостояния Цель конечные состояния Реализует возможность выбора Выполняет шаги от начального состояния к новым более близким к цели Исходные посылки и факты Поиск Стратегия поиска B A C C A B A B C A B C C B A B C A B A C C A B A B C C A B B A C A B C A C B 8. Стратегии поиска в СОЗ 8. Поиск в СОЗ Причем поиск конечного состояния выполняется автоматически на основе реализованной в СОЗ стратегии поиска которая: реализует возможность выбора; позволяет выполнять шаги от начального...

Русский

2013-08-05

105.5 KB

1 чел.

© SerP   С.Хабаров  - Лекция по курсу "Информационные технологии " (7 стр.)  стр. 7


Начальные
состояния

Цель (конечные состояния)

Реализует возможность выбора

Выполняет шаги от начального состояния к новым, более близким к цели

Исходные посылки и факты

П
о
и
с
к

Стратегия поиска

B

A

C

C

A

B

       A

B      C

A

B     C

C

B

A

B

C

A

B

A      C

C

A      B

A B C

       C

A     B

       B

A     C

A

B

C

A

C

B

8. Стратегии поиска в СОЗ

8.1. Поиск как основа функционирования СОЗ

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

Рис. 8.1. Поиск в СОЗ

Причем поиск конечного состояния выполняется автоматически на основе реализованной в СОЗ стратегии поиска, которая:

реализует возможность выбора;

позволяет выполнять шаги от начального состояния к новым состояниям, более или менее близким к цели.

Таким образом, реализованные в СОЗ стратегии поиска отыскивают цель, «шагая» от одного состояния системы к другому. При этом они обеспечивают распознавание ситуации, когда они находят цель или попадают в тупик.

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

Большинство СОЗ работают по этой модели.

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

Система, построенная на основе знаний об этой карте дорог, должна поработать с картой и спланировать наше путешествие, например из города «А» в город «F».

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

Рис. 8.2. Карта дорог

Дерево поиска показывает все возможные варианты выбора при движении из «А» (начальное состояние), а также и все варианты выбора в каждом из промежуточных пунктов (состояний).

Место, откуда начинается поиск, находится в вершине дерева поиска.

Все дороги, начинаясь в «А», либо приводят в тупик, либо заканчиваются в «F».

                

Рис. 8.3. Дерево поиска

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

Человек при взгляде на дерево поиска сразу же выберет подходящую дорогу, но компьютер на это не способен. Какую стратегию поиска применит компьютер?

Рассмотрим пример, который заставит нас думать как компьютер.

Мы находимся в темной комнате, на стене которой дерево поиска, а у нас фонарик, который освещает всего два соседних пункта.

Нам известно, где расположена вершина дерева, откуда надо начать поиск. Как наиболее эффективно перемещать луч фонарика, чтобы найти маршрут до «F»?

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

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

8.2. Стратегии поиска в глубину и ширину

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

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

Рис. 8.4. Поиск в глубину

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

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

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

Рис. 8.5. Поиск в ширину

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

Обе эти стратегии предполагают последовательный перебор возможных вариантов.

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

8.3. Стратегия эвристического поиска

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

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

Существует целый ряд эвристических методов. Простейший из них носит название «взбирание на гору». Его принцип:

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

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

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

Такой подход не всегда действенен, но это хорошая стратегия. В нашем примере программа исследует маршрут A  B  C и найдет тупик, затем вернется назад, в то место, где существует альтернатива выбору, т.е. в «В», а затем сразу отправится по маршруту B  E  F, который приведет к цели.

Рис. 8.6. Метод «Взбирание на гору»

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


8.4. Формализация задач в пространстве состояний

Процесс решения задачи, как правило, включает два этапа: представление задачи и реализацию стратегии поиска.

Полное представление задачи в пространстве состояний включает:

описание всех или только начальных состояний;

задание операторов, отображающие одни состояния в другие;

задание целевого состояния.

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

Таким образом, представление задачи в пространстве состояний определяется совокупностью трех составляющих — тройкой

< S0, F, G>

где S0 - множество начальных состояний (может состоять из одного элемента);

F - множество операторов, отображающих одно состояние в другое;

G - множество целевых состояний.

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

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

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

Тогда начальное состояние будет описываться списком, состоящим только из одного элемента, соответствующего начальному пункту пути:

[A]

Конечным состояниям будут соответствовать любые списки, первые элементы которых  соответствуют целевой вершине, т.е. конечному пункту маршрута:

[F ¦  ]

Для рассмотренного выше примера конечному состоянию будут соответствовать списки:

[F ¦ [ E,B,A]]

[F ¦ [H,G,A]] и т.д.

Операторы преобразования для этого примера могут быть представлены в виде:

набора фактов, определяющих дороги между городами;

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

Для рассмотренного примера набор фактов может быть следующим:

дорога (a, b)

дорога (a, g)

дорога (a, e)

дорога (b, c)

……………

дорога (g, h)

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

маршрут (Кон_город,Кон_город,[Кон_город]).

маршрут (Город,Кон_город,[Город|Путь_до_конца]):-

дорога(город,город_к),

маршрут (Город_к,Кон_город,Путь_до_конца)

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

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

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

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

Рис. 8.7. Задача

Условия задачи:

  1.  На каждом шаге можно переставить только один кубик;

Кубик можно взять только тогда, когда верхняя поверхность свободна;

Кубик можно поставить либо на стол, либо на другой кубик.

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

Эту задачу можно представить как задачу выбора среди множества возможных альтернатив.

В исходной ситуации альтернатива одна — поставить кубик C на стол.

После того как кубик C поставлен на стол, мы имеем три альтернативы:

1)поставить A на стол,

или

2) поставить A на C,

или

3) поставить C на A.

Как показывает рассмотренный пример с задачами такого рода связано два типа понятий:

проблемные ситуации.

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

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

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

Для рассмотренной задачи решением является выделенный на графе путь.

Рис. 8.8. Граф (пространство состояний)

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

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

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

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

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

Но прежде, чем говорить о возможных стратегиях поиска в пространстве состояний, давайте выясним, как можно представить пространство состояний в БЗ, используя для примера язык Пролог.

8.5. Представление пространства состояний в виде базы знаний

Будем представлять пространство состояний при помощи отношения предиката

после (Х,Y)

которое истинно тогда, когда в пространстве состояний существует разрешенный ход из вершины Х в вершину Y. Будем говорить, что Y - это преемник вершины Х. Если с ходом связаны их стоимости, мы добавим третий аргумент, стоимость хода:

после (X,Y,S)

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

Поэтому отношение следования «после ( )» обычно определяется при помощи правил

вычисления вершин - приемников

некоторой заданной вершины

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

операций вычисления вершин - приемников.

а возможно и стоимостей соответвующих ходов.

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

Тогда исходную ситуацию (состояние) можно записать как терм вида:

[[c,a,b],[   ],[   ]]

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

[[a,b,c],[   ],[   ]],

[[   ],[a,b,c],[   ]],

[[   ],[   ],[a,b,c]].

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

«Состояние 2» есть приемник «Состояния 1» если в «состоянии 1» имеется два столбика «Столб 1» и «Столб 2», такие, что верхний кубик из «Столб 1» можно поставить сверху на «Столб 2» и получить при этом «Состояние 2».

При этом целевое условие может быть также представлено в виде правила:

Цель(состояние):-принадлежит([a,b,c],Состояние)

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


 

А также другие работы, которые могут Вас заинтересовать

21636. Дифференциальная диагностика и лечение боли в области сердца 444 KB
  Этиология, патогенез и классификация перикардитов; клиника, диагностика фибринозного перикардита. Дифференциальный диагноз; лечение фибринозного перикардита; клиника, диагностика экссудативного перикардита. Дифференциальный диагноз; лечение экссудативного перикардита. Показания к перикардиоцентезу;
21637. Распространение радиоволн, процессы распространения электромагнитных волн радиодиапазона в атмосфере, космическом пространстве и толще Земли 401.5 KB
  Радиоволны излучаемые передатчиком прежде чем попасть в приёмник проходят путь который может быть сложным. Радиоволны могут достигать пункта приёма распространяясь по прямолинейным траекториям огибая выпуклую поверхность Земли отражаясь от ионосферы и т. существенно зависят от длины волны  от освещённости земной атмосферы Солнцем и от ряда др. Прямые волны.
21638. ОСОБЕННОСТИ РАСПРОСТРАНЕНИЯ КОРОТКИХ РАДИОВОЛН 405 KB
  В отличие от более коротких волн которые распространяются земной волной декаметровые волны распространяются в основном путем отражении от ионосферы. Но короткие волны могут распространяться на многие тысячи километров путем многократных последовательных отражений от ионосферы и Земли рис. Кроме радиосвязи декаметровые волны широко используются для радиовещания дальней загоризонтной радиолокации исследования ионосферы и др. Одной из основных особенностей KB радиолиний является ограничение рабочих частот как со стороны высоких так и...
21639. Зеркальные антенны. Общие сведения и принцип действия зеркальной антенны 344.5 KB
  Источником электромагнитной волны обычно служит какаянибудь небольшая элементарная антенна называемая в этом случае облучателем зеркала или просто облучателем. Поверхности зеркала придается форма обеспечивающая формирование нужной диаграммы направленности. Наиболее распространенными являются зеркала в виде параболоида вращения усеченного параболоида параболического цилиндра или цилиндра специального профиля.
21640. ОСНОВЫ ТЕОРИИ ПРАВА 99 KB
  Особенностями правил поведения, которые образуют право и отличают эти правила от других: морали, традиций, обычаев, являются то, что они устанавливаются государством, защищаются от нарушения государством, должны выражать интересы большинства населения, независимо от политических, экономических и других взглядов, они обязательны для всех.
21641. ЭЛЕКТРИЧЕСКИЕ ПАРАМЕТРЫ АНТЕНН 256.5 KB
  ЭЛЕКТРИЧЕСКИЕ ПАРАМЕТРЫ АНТЕНН. Основные электрические параметры передающих антенн. РАСЧЕТ ПОЛЯ ИЗЛУЧЕНИЯ АНТЕНН. Применение принципа суперпозиции к расчету поля излучения антенн.
21642. Антенны с круговой диаграммой направленности 188 KB
  По той же причине в качестве базовых антенн выбираются антенны с круговой диаграммой направленности в горизонтальной плоскости одинаково хорошо работающие в любом направлении. Наиболее широкое применение в этой группе получили антенны типа Ground Plane GP – рис. Конструкция антенны GP Штыревая конструкция антенны удобна для размещения как на крыше здания так и на автомобиле.
21643. Сущность, принципы и функции планирования на предприятии 64 KB
  Планирование как общее понятие – это процесс моделирования вариантов развития объекта (явления) на определенный период, оценки, сравнения, выбора и разработки промежуточных и конечных показателей реализации плана.
21644. Конструкция антенна Двойной квадрат 202.5 KB
  Как все проволочные антенны она достаточно проста в изготовлении и не требует дорогостоящих материалов. Антенны типа Двойной квадрат обладают следующими характеристиками. Сравнение характеристик антенны GP 5 8 и описываемой антенны проводилось при малых углах излучения по отношению к горизонту что наиболее важно для проведения дальних связей поверхностной волной. Распорки антенны 8 шт.