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


 

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

33348. Принципы формирования МКЛС с частотным разделением сигналов (ЧРК) 33.83 KB
  Частотное разделение сигналов Функциональная схема простейшей системы многоканальной связи с разделением каналов по частоте представлена на Рис. ФN спектры gK канальных сигналов занимают соответственно полосы частот 1 2 . Проследим основные этапы образования сигналов а также изменение этих сигналов в процессе передачи Рис.
33349. Принципы формирования МКЛС с временным разделением каналов (ВРК) 25.94 KB
  Временное разделение каналов Принцип временного разделения каналов ВРК состоит в том что групповой тракт предоставляется поочередно для передачи сигналов каждого канала многоканальной системы Рис. Принцип временного разделения каналов В зарубежных источниках для обозначения принципа временного разделения каналов используется термин Time Division Multiply ccess TDM. Для этого один из каналов занимают под передачу специальных импульсов синхронизации.
33350. Особенности построения цифровых многоканальных систем передачи. Плезиохронная цифровая иерархия (ПЦИ). Cинхронная цифровая иерархия 72.37 KB
  Особенности построения цифровых систем передачи Основной тенденцией развития телекоммуникаций во всем мире является цифровизация сетей связи предусматривающая построение сети на базе цифровых методов передачи и коммутации. Это объясняется следующими существенными преимуществами цифровых методов передачи перед аналоговыми. Представление информации в цифровой форме позволяет осуществлять регенерацию восстановление этих символов при передаче их по линии связи что резко снижает влияние помех и искажений на качество передачи информации.
33351. Виды и тенденции развития направляющих систем электросвязи (НСЭ) 90.94 KB
  Тенденции развития направляющих систем электросвязи НСЭ Построение сети базируется на направляющих средах передачи рис. В направляющие среды передачи входят вся номенклатура действующих металлических кабелей связи волоконнооптические кабели воздушные линии волноводы линии поверхностной волны высоковольтные линии электропередачи электрофицированные железные дороги радиорелейные линии и спутниковые линии. Направляющими системами передачи НСП имеющими первостепенное значение при построении сетей электросвязи являются электрические...
33352. Металлические кабели и их основные параметры 42.52 KB
  проводников К линиям связи предъявляются следующие основные требования: осуществление связи на практически требуемые расстояния; пригодность для передачи различных видов сообщений как по номенклатуре так и по пропускной способности; защищенность цепей от взаимных влияний и внешних помех а также от физических воздействий атмосферных явлений коррозии и пр. В простейшем случае проводная ЛС физическая цепь образуемая парой металлических проводников. По конструкции и взаимному расположению проводников различают симметричные СК и...
33353. Волоконно-оптические кабели и их основные параметры 13.74 KB
  Многомодовое волокно со ступенчатым изменением показателя преломления диаметр сердечника 40 – 100 мкм. Многомодово волокно с плавным изменение показателя преломления диаметр сердечника 40 – 100 мкм. Одномодовое волокно диаметр сердечника 5 – 15 мкм. В одномодовом кабеле используется центральный проводник очень малого диаметра соизмеримый с длинной волной света – от 5 до 10 мкм.
33354. Общие сведения о радиолиниях связи. Основные понятия и определения. Классификация диапазонов радиочастот и радиоволн. Особенности распространения радиоволн метрового и миллиметрового диапазонов 18.21 KB
  Классификация диапазонов радиочастот и радиоволн. Особенности распространения радиоволн метрового и миллиметрового диапазонов. Классификация диапазонов радиочастот и радиоволн. Радиосвязь вид электросвязи осуществляемый с помощью радиоволн.
33355. Обеспечение дальности связи. Радиорелейные, тропосферные и спутниковые линии (системы) передачи (связи). Магистральные кабельные линии (системы) передачи 64.86 KB
  Радиорелейные тропосферные и спутниковые линии системы передачи связи. Магистральные кабельные линии системы передачи. Радиолинии передачи 6. Радиорелейные линии передачи Радиолиния передачи в которой сигналы электросвязи передаются с помощью наземных ретрансляционных станций называется радиорелейной линией передачи.
33356. Открытые системы и их взаимодействие. Эталонная модель взаимодействия открытых систем. Основные понятия и определения 27.2 KB
  Прикладной процесс Системы А сообщается с Уровнем 7 Системы А верхний уровень который сообщается с Уровнем 6 Системы А который в свою очередь сообщается с Уровнем 5 Системы А и так далее до Уровня 1 Системы А. После того как информация проходит через физическую среду и принимается Системой В она поднимается через слои Системы В в обратном порядке сначала Уровень 1 затем Уровень 2 и т. пока она наконец не достигнет прикладного процесса Системы В.