Общие представления о недетерминированных поисково-переборных задачах

В общем случае для недетерминированных поисковых задач решения представляются двумя типами графов:

1. граф с И – решением;

2. граф с ИЛИ – решением;

граф И - решения граф ИЛИ – решений

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

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

Поисково-переборная задача в общем случае характеризуется такими качественными категориями, как:

1. неопределенность процесса;

2. свобода выбора;

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

Существуют следующие формализации понятия «свобода» выбора:

1. выбор 1 из k;

2. выбор n из k, где (n< k);

3. выбор k из k;

где k – коэффициент ветвления для текущей вершины;

Вариант 1 из k означает, что из k возможных процессов всегда выбирается один приоритетный, при этом процедура выбора является или специализируемой, или эвристической.

Вариант n из k, используется для одновременной реализации n невзаимодействующих процессов, при этом универсальные процедуры определения n, как правило, отсутствуют.

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

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

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

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

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

Алгоритм – это точное предписание действий. Предписательная семантика означает, что между алгоритмами заранее задана последовательность действий, изменить которую исполнитель не может.

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

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

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

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

Проблема организации поиска в условиях априорной неопределенности шагов имеет прежде всего ресурсное ограничение. Данное ограничение связано с наличием фиксированного количества активных исполнительных устройств (процессов), способных параллельно выполняться в вычислительной системе. Если количество активных устройств (процессов) превышает текущий коэффициент ветвления, то все ветви графа могут выполняться независимо с формированием различных промежуточных результатов. В противном случае, возникает конфликт за общий ресурс (активные устройства или процессs) и необходимость выбора приоритетных из них. В рамках объектно-ориентированной операционной системы возможен механизм организации квазипараллельных вычислений, при котором с точки зрения программиста организуется параллельный обход графа с использованием потоков. Техническая поддержка параллельного программирования многопроцессорной организации позволит перейти от квазипараллельных вычислений к параллельным вычислениям в условиях априорной неопределенности.

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

1. этап генерации полного множества решений;

2. этап выбора подмножества оптимальных решений по заданным критериям.

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

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

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

Задача поиска формально определяется следующим образом:

{S, F, Z, P, Q}, (1)

где S – начальное состояние, F – множество конечных состояний, Z- множество заключительных состояний (ZÍ F), P – множество правил преобразования вида (2), носящих недетерминированный смысл исполнения, Q – множество ограничений на правила преобразования.

А ® В, (2)

где А – заменяемое состояние, В – заменяющее состояние.

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

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

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

Решение задачи путем поиска имеет следующиеколичественные характеристики графа состояний:

1. глубина поиска

а) кратчайший путь в графе

б) путь в графе максимальной длины

2. ширина поиска

а) максимальный коэффициент ветвления

б) средний коэффициент ветвления по графу

3. общее количество состояний в графе

4. коэффициент сужения

б) средний коэффициент сужения по графу.

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

Коэффициент ветвления графа определяется выражением (3)

, (3)

где st^’ – вершина, имеющая более одного состояния-потомка, f - конечная вершина графа. Например, пусть в графе у каждой вершины имеется B потомков и граф содержит n уровней. Тогда конечные вершины располагаются на последнем n-ом уровне, а их количество составляет Bⁿ вершин. Общее количество вершин в графе определяется суммой вершин по всем уровням и определяется выражением (4)

B+B²+… +B^n-2+B^n-1+Bⁿ (4).

Коэффициент ветвления для такого графа определяется как (5)

(5).

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

Текущий коэффициент сужения определяется как (6)

, (6)

где sp – количество состояний-предков у i-ой вершины.

Общий коэффициент сужения – это сумма текущих коэффициентов сужения по всем состояниям графа (7)

, (7)

где KS_j – j-ый коэффициент сужения, j=1-n –количество состояний в графе.

Коэффициент сужения определяет «недостроенные» пути и «недополученные» в графе состояния.

Поисковые процедуры подразделяются:

1. по выбору начального и конечного состояния

а) поиск от данных (прямой поиск)

б) поиск от цели (обратный поиск)

2. по направлению обхода

а) в глубину

б) в ширину.

При поиске от данных процесс решения задачи начинается от заданного начального состояния и состоит в применении правил преобразования состояний задачи, которые, в свою очередь, используются для генерации новых состояний. Этот процесс продолжается до тех пор, пока не будет достигнуто целевое состояние. Возможен и другой подход. Целевое состояние рассматривается как потенциально достижимое, но путь кнему неизвестен. Для восстановления пути от целевого состояния к начальному состоянию анализируются допустимые правила преобразования, ведущие к цели. Эти новые состояния становятся новыми подцелями поиска. Поиск ведется в обратном направлении от достигнутых подцелей до достижения начального состояния. Таким образом, определяется путь от цели к исходным данных. Иногда поиск от цели, восстанавливающий путь в обратном порядке называют обратным поиском.

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

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

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

При поиске' на исповеданных {data-driven search—поиск, управляемый данными), который иногда называют прямой цепочкой (forward chaining), исследователь начинает про­цесс решения задачи, анализируя ее условие, а затем применяет допустимые ходы или пра­вила изменения состояния. В процессе поиска правила применяются к известным фактам для получения новых фактов, которые, в свою очередь, используются для генерации новых фактов. Этот процесс продолжается до тех пор, пока мы, если повезет, не достигнем цели.

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

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

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

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

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

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

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

Таким образом, при поиске цели подходящие правила применяются для исключе­ния неперспективных ветвей поиска.

Поиск на основе данных применим к решению задачи в следующих случаях.

Все или большинство исходных данных заданы в постановке задачи. Задача интерпретации состоит в выборе этих данных и их представлении в виде, подходящем для использования в интерпретирующих системах более высокого уровня. На стратегии поиска от данных основаны системы анализа данных определенного типа Это такие системы, как PROSPECTOR или Dipmeter, анализаторы геологических данных, определяющие, какие минералы с наибольшей вероятностью могут быть найдены в некотором месте.

Существует большое число потенциальных целей, но всего лишь несколько спосо­бов применения фактов и представления информации о конкретном примере задачи (рис. 3.11). Примером этого типа систем является программа DENDRAL—экспертная система исследования молекулярных структур органических соединений

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

3. Сформировать цель или гипотезы очень трудно. Например, при использовании системы DENDRAL изначально может быть очень мало информации о возможной структуре соединения.

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

Подводя итог, заметим, что ничто не заменит тщательного анализа каждой конкрет­ной задачи. Необходимо учитывать такие особенности, как фактор ветвления при ис­пользовании правил, доступность данных и простота определения потенциальных целей. В главе 4 рассказывается о том, сколько новых состояний возникает в результате приме­нения правил поиска в обоих направлениях.
Лекция №5, 6