8124

Поиск в пространстве состояний. Формальная постановка задачи. Обобщенный алгоритм поиска. Критерии оценки стратегий

Лекция

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

Поиск в пространстве состояний.Формальная постановка задачи. Обобщенный алгоритм поиска. Критерии оценки стратегий. Многие задачи,в частности игры и головоломки,могут быть представлены как задачи поиска в пространств...

Русский

2013-02-04

116.01 KB

17 чел.

Поиск в пространстве состояний. Формальная постановка задачи. Обобщенный алгоритм поиска. Критерии оценки стратегий.

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

Решить задачузначит найти путь из исходного состояния в целевое.

Формально задача поиска в пространстве состояний в общем случае задается четверкой:

<I, {Oi}, GT, PC>,

где Iисходное состояние, т. е. состояние мира в начале задачи;

     {Oi} –множество действий (операторов), возможных в различных состояниях;

      GT (goal test) –проверка достижения целевого состояния;

      PC (path cost) –функция стоимости пути.

Действия (операторы) переводят состояния в другие состояния. Таким образом, можно ввести в рассмотрение функцию последователей S (successor), ставящую в соответствие каждому состоянию x множество состояний S(x), достижимых из x за одно действие.

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

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

  •  явное перечисление множества целевых состояний;
  •  использование предикатов, описывающих целевые состояния.

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

Функция PC (path cost) позволяет вычислить стоимость пути в заданных единицах. Как правило PC является аддитивной оценкой, т. е. стоимость пути вычисляется как сумма стоимостей элементов пути (операторов).

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

datatype Problem component : INITIAL-STATE, Оperations, Goal Test, Path-Cost-Funct.

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

  1.  Находит ли он решение в принципе (полнота);
  2.  Является ли найденное решение хорошим (т.е. имеющим низкую стоимость пути).
  3.  Какова стоимость реализации поиска, определяемая временем и памятью, требуемыми для нахождения решения (пути).

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

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

Корнем этого дерева является вершина соответствующая начальному состоянию.

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

На каждом шаге алгоритм поиска выбирает для раскрытия одну концевую вершину.

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

Function General-Search (Problem, Strategy) returns solution or failure

Инициализация дерева поиска исходным состоянием задачи I

Loop do  - цикл

if (нет вершин - кандидатов для раскрытия)

then return failure

Выбрать концевую вершину (лист) для раскрытия в соответствии со стратегией.

if (вершина содержит целевое состояние)

then return solution (путь к этой вершине)

else

 Раскрыть вершину и добавить новые вершины в дерево поиска.

end

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

. Состояние в пространстве состояний, которому сопоставлена вершина.

. Родительская вершина –это вершина, непосредственным потомком которой является данная вершина.

. Оператор, в результате применения которого была порождена  данная вершина.

. Глубина вершинычисло вершин в пути от корня дерева к данной вершине.

. Стоимость пути от корневой вершины к текущей.

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

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

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

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

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

. make-Queue (Elements) –создание очереди с заданными элементами;

. empty?(Queue) –возвращает true, если очередь пуста;

. remove-front(Queue) –возвращает первый элемент очереди и удаляет его из очереди;

. Queueing-Fn(Elements, Queue) –добавляет в очередь множество элементов. Именно эта функция определяет разные стратегии, реализующие разные алгоритмы поиска.

С использованием введенных обозначений можно записать алгоритм поиска:

function General-Search(Problem, Queuing-Fn) returns solution or failure

    nodes  make-Queue(Make-Node(Init-State[Problem]) //присваивание

    Make-Node;  // порождение вершины, т.е. получили корень

     loop do

if  nodes = 0 then return failure

node  Remove-Front (nodes)

         if Goal-Test[problem] (State(node))=true

 then return node

 else nodes  Queueing-Fn(nodes, Expand(node, OPERATORS[Problem]))

end

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

3


 

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

80906. ФУНКЦИОНАЛЬНОЕ РАЗДЕЛЕНИЕ УПРАВЛЕНЧЕСКОГО ТРУДА 46.33 KB
  Он основан на функциональном профессиональном квалификационном и операционнотехнологическом разделении труда. Функциональное разделение труда основывается на формировании групп работников управления выполняющих одинаковые общие функции менеджмента. Наряду с этим функциональное разделение труда предполагает выделение из общего состава менеджеров специалистов которые отвечают за процесс управления в целом а не за какуюто одну функцию.
80907. Психологический аспект в работе с инвалидами 25.75 KB
  Это связано прежде всего с дефектами их физического состояния вызванного заболеваниями приведшими к инвалидности а также с имеющимся комплексом сопутствующей соматической патологии и с пониженной двигательной активностью характерными для большинства инвалидов. Психологические проблемы возникают при изолированности инвалидов от внешнего мира как вследствие имеющихся недугов так и в результате неприспособленности окружающей среды для инвалидов на креслоколясках при разрыве привычного общения в связи с выходом на пенсию при наступлении...
80908. Основное содержание и виды реабилитации инвалидов 30.05 KB
  Реабилитация больных и инвалидов представляет собой комплексную систему государственных медицинских психологических социальноэкономических педагогических производственных бытовых и других мероприятий. Профессиональная реабилитация предусматривает обучение или переобучение доступным формам труда обеспечение необходимыми индивидуальными техническими приспособлениями для облегчения пользования рабочим инструментом приспособление прежнего рабочего места больного или инвалида к его функциональным возможностям организацию для инвалидов...
80909. Формы социальной поддержки детей-инвалидов 34.02 KB
  Особенности реабилитации детей с ограниченными возможностями заключаются в том что в процессе реабилитации необходимо предусмотреть не только ликвидацию или коррекцию дефекта вызванного заболеванием но и обеспечение развития других функций формирование которых может быть задержано в связи с болезнью. В настоящее время изза отсутствия государственной системы реабилитации детейинвалидов звенья реабилитационного процесса нескоординированы...
80910. Культурно–досуговая работа с инвалидами 34 KB
  При организации досуговой деятельности инвалидов в целях их оптимального вхождения в социокультурное пространство и восстановления социокультурных связей необходимо ориентироваться на наличие специализированной политики государства учитывающей индивидуальные особенности данной группы населения. В Концепции социокультурной политики в отношении инвалидов в Российской Федерации 1997 отмечено что государственная политика в отношении людей с ограниченными возможностями как одной из наименее социально защищенных категорий населения является...
80911. Модели социальной поддержки инвалидов 33.5 KB
  Социальная политика в отношении инвалидов осуществляется с целью их успешной социальной интеграции которая является средством социального развития общества. В общем интеграция инвалидов в социальное общество осуществляется через эффективный реабилитационный процесс. Задача социореабилитации – с помощью технических средства реабилитации восстановить нормальные отношения инвалидов с окружающими людьми вопреки физическому или психическому дефекту.
80912. Инновационные формы социальной защиты инвалидов 45.59 KB
  Последствия таких подходов создавали иллюзию мнимого благополучия так как относительные показатели инвалидности на фоне естественного прироста населения улучшались изза чего реальные стимулы к поиску истинных причин роста абсолютного числа инвалидов отсутствовали. С начала 90х годов традиционные принципы государственной политики направленной на решение проблем инвалидности и инвалидов в связи со сложной социальноэкономической ситуацией в стране утратили свою эффективность. В настоящее время инвалид характеризуется как лицо которое имеет...
80913. Понятие и сущность инвалидности 29.22 KB
  Наконец после Второй мировой войны в русле общего движения по формулированию и защите прав человека в целом и отдельных категорий населения в частности происходит формирование понятия инвалид относящегося ко всем лицам имеющим физические психические или интеллектуальные ограничения жизнедеятельности. инвалид определяется как лицо которое имеет нарушение здоровья со стойким расстройством функций организма обусловленным заболеваниями последствиями травм или дефектами приводящими к ограничению жизнедеятельности и вызывающими...
80914. Социальные барьеры людей с ограниченными возможностями 29.35 KB
  Мысль о том что инвалидам должны предоставляться равные возможности со здоровыми что они не должны подвергаться сегрегации и дискриминации еще не овладела ни нашим обществом в целом ни даже теми его членами которые непосредственно причастны к судьбам инвалидов. По данным отечественных и зарубежных экспертов трудовая деятельность доступна приблизительно 2 3 всех инвалидов работает же не более 11 из них. Третьим барьером в жизни инвалидов выступает малообеспеченностъ которая является следствием социальнотрудовых ограничений: эти люди...