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

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


 

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

46297. Объединения юридических лиц 15.56 KB
  Объединения Юридических Лиц некоммерческие организации созданные юридическими лицами на добровольных договорных началах и на основе их членства в форме ассоциаций и союзов в целях координации их деятельности и представления и защиты их общих в том числе имущественных интересов п. Объединения Юридических Лиц не вправе осуществлять какиелибо управленческие функции в отношении участников которые полностью сохраняют свою самостоятельность. атривает минимально необходимого числа участников Объединения Юридических Лиц отдавая решение этого...
46298. Грамматическое значение и грамматические формы. Способы выражения грамматических значений в языке 15.55 KB
  Грамматическое значение и грамматические формы. Таким образом можно сказать что каждое грамматическое явление всегда имеет две стороны: внутреннюю – грамматическое значение и внешнюю – грамматический способ выражения. Если лексическое значение может быть только одно то грамматических значений у слова может быть несколько и они находят в языке свое морфологическое и синтаксическое выражение. В области морфологии грамматическое значение – это общие значения слов как частей речи например значение предметности у существительных а также...
46299. The adjective 15.52 KB
  Unlike nouns djectives do not possess full nomintive vlue. Clssifiction of djectives.Хаймович и Роговская With regrd to the ctegory of the degrees of comprison djectives fll under 2 lexicogrmmticl subclsses: comprbles nd noncomprbles. The nucleus of the ltter is composed of derived djectives like wooden Crimen mthemticl etc.
46300. ФОНЕМА КАК ЕДИНИЦА ЯЗЫКА. ФУНКЦИИ ФОНЕМЫ 15.5 KB
  Функции фонем Фонемы выполняют следующие функции: дистинктивная различительная функция выражается в том что фонема служит для фонетического опознавания и семантического отождествления слов и морфем. Дистинктивная функция включает в себя перцептивную опознавательную и сигнификативную смысл оразличительную функции перцептивная функция функция доведения звуков речи до восприятия: она дает возможность воспринимать и опознавать органом слуха звуки речи и их сочетания способствуя отождествлению одних и тех же слов и морфем...
46301. Методика экономического анализа 15.5 KB
  В экономическом анализе методика представляет собой совокупность аналитических способов и правил исследования экономики предприятия определенным образом подчиненных достижению цели анализа. Методика экономического анализа совокупность специфических приемов и способов исследования которые применяются при обработке экономической информации в соответствии с поставленными задачами. Она содержит следующие моменты: задачи и формулировки целей анализа; объекты анализа; системы показателей с помощью которых будет исследоваться каждый...
46302. Понятие языковой идиоматики: пословицы, поговорки, афоризмы и речевое клише 15.48 KB
  Понятие языковой идиоматики: пословицы поговорки афоризмы и речевое клише. Можно говорить о пословичном стиле существующем как бы вне времени: традиционность настолько неотъемлемая его черта что сама мысль об истоках пословицы кажется в чемто противоречивой. Пословицы изучает паремиология. Определение Даля складная короткая речь ходячая в народе но не составляющая полной пословицы вполне подходит к поговорке отмечая в то же время особый и очень распространенный вид поговорки ходячее выражение недоразвившееся до полной...
46303. С. Выготский «Проблема обучения и умственного развития в школьном возрасте» 15.45 KB
  Выготский Проблема обучения и умственного развития в школьном возрасте Хрестоматия по возрастной психологии. схематически сводит все существующие решения вопроса об отношении развития и обучения ребенка к трем основным группам. Первая группа имеет своим центром положение о независимости процессов детского развития от процессов обучения. Обучение в этих теориях рассматривается как чисто внешний процесс который должен быть так или иначе согласован с ходом детского развития но сам по себе не участвующий активно в детском развитии ничего в...
46304. Методика обучения словообразованию 15.44 KB
  Изучение морфемики и словообразования – это основа формирования представлений о языке как развивающейся системе постоянно пополняющейся новыми словами. Элементарные знания даются в начальной школе в 57 классах – ученики знакомятся с основными понятиями структуры слова и словопроизводства в 89 классах – полученные сведения закрепляются и обобщаются. познавательные цели: ознакомление учащихся со структурой русского слова основными способами русского словообразования показать взаимосвязь между единицами разных уровней языка:...
46305. Noun 15.41 KB
  Noun hs ctegoricl mening of thingness becuse noun effects nomintion of the fullest vlue. The N is chrcterized by specific set of wordbuilding ffixes nd wordbuilding models which unmistkbly mrk noun mong them: suffixes of the doer worker nturlist etc. s for wordchnging ctegories the noun is chnged ccording to the ctegories of number boyboys cse boyboy’s nd rticle determintion boy boy the boy.