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],Состояние)

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


 

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

81525. Генетическая гетерогенность. Полиморфизм белков в популяции человека (варианты гемоглобина, гликозилтрансферазы, группоспецифических веществ и др) 107.01 KB
  Группы крови. Другой важный пример полиморфизма белков связанный с проблемой переливания крови существование в популяции людей 3 аллельных вариантов гена фермента гликозилтрансферазы А В и 0. Антитела к антигенам А и В обычно имеются в сыворотке крови людей на поверхности эритроцитов которых отсутствует соответшвующий антиген т. индивидуумы с антигенами А на поверхности эритроцитов продуцируют в сыворотку крови антитела к Вантигенам антиВ а люди с Вантигенами антитела к антигенам А антиА.
81526. Биохимические основы возникновения и проявления наследственных болезней (разнообразие, распространение) 104.52 KB
  За этой группой следуют белки модулирующие функции белков и участвующие в правильном сворачивании полипептидных цепей. Хорошо изученными наследственными заболеваниями связанными с нарушением синтеза α или βцепей НЬ являются талассемии. Синтез α и βцепей в норме регулируется таким образом что все молекулы протомеров используются на синтез тетрамера α2β2 Талассемии возникают как результат мутаций включающих замены или делеции одного или нескольких нуклеотидов а иногда и целого гена кодирующего структуру одного из протомеров....
81527. Основные системы межклеточной коммуникации: эндокринная, паракринная, аутокринная регуляция 100.4 KB
  По расстоянию от клетки продуцента гормона до клеткимишени различают эндокринный паракринный и аутокринный варианты регуляции. Клеткимишени могут отстоять от эндокринной клетки сколь угодно далеко. Пример: секреторные клетки эндокринных желёз гормоны из которых поступают в систему общего кровотока. Примеры: эндотелины вырабатываемые клетками эндотелия и воздействующие на эти же эндотелиальные клетки; Тлимфоциты секретирующие интерлейкины имеющие мишенями разные клетки в том числе и Тлимфоциты.
81528. Роль гормонов в системе регуляции метаболизма. Клетки-мишени и клеточные рецепторы гормонов 106.94 KB
  Клеткимишени и клеточные рецепторы гормонов Роль гормонов в регуляции обмена веществ и функций. Физиологический эффект гормона определяется разными факторами например концентрацией гормона которая определяется скоростью инактивации в результате распада гормонов протекающего в основном в печени и скоростью выведения гормонов и его метаболитов из организма его сродством к белкампереносчикам стероидные и тиреоидные гормоны транспортируются по кровеносному руслу В комплексе с белками количеством и типом рецепторов на поверхности...
81529. Механизмы передачи гормональных сигналов в клетки 98.08 KB
  По механизму действия гормоны можно разделить на 2 группы. К первой группе относят гормоны взаимодействующие с мембранными рецепторами пептидные гормоны адреналин а также гормоны местного действия цитокины эйкозаноиды. Вторая группа включает гормоны взаимодействующие с внутриклеточными рецепторами.
81531. Строение, синтез и метаболизм иодтиронинов. Влияние на обмен веществ. Изменение метаболизма при гипо- и гипертиреозе. Причины и проявление эндемического зоба 160.08 KB
  Биосинтез йодтиронинов. Из цистерн ЭР Тиреоглобулин поступает в аппарат Гольджи включается в состав секреторных гранул и секретируется во внеклеточный коллоид где происходит йодирование остатков тирозина и образование йодтиронинов. Йодирование тиреоглобулина и образование йодтиронинов осуществляется в несколько этапов Транспорт йода в клетки щитовидной железы. Образование йодтиронинов.
81532. Регуляция энергетического метаболизма, роль инсулина и контринсулярных гормонов в обеспечении гомеостаза 107.55 KB
  Абсорбтивный период характеризуется временным повышением концентрации глюкозы аминокислот и жиров в плазме крови. Изменения метаболизма в печени в абсорбтивном периоде После приёма пищи печень становится главным потребителем глюкозы поступающей из пищеварительного тракта. Почти 60 из каждых 100 г глюкозы транспортируемой портальной системой задерживается в печени. Увеличение потребления печенью глюкозы не результат ускорения её транспорта в клетки транспорт глюкозы в клетки печени не стимулируется инсулином а следствие ускорения...
81533. Изменения метаболизма при сахарном диабете. Патогенез основных симптомов сахарного диабета 115.42 KB
  При недостаточности содержания инсулинавозникает заболевание которое носит название сахарный диабет: повышается концентрация глюкозы в крови гипергликемия появляется глюкоза в моче глюкозурия и уменьшается содержание гликогена в печени. При введении инсулина больным диабетом происходит коррекция метаболических сдвигов: нормализуется проницаемость мембранмышечных клеток для глюкозы восстанавливается соотношение между гликолизом и глюконеогенезом. В связи с этим при инсулярной недостаточности и сохранении или даже повышении...