Методы поиска решений реферат

Обновлено: 04.07.2024

Задание
1. Выбрать ТО, улучшить его показатели методом ОМА (обратной мозговой атаки).
2. Выявить и устранить дефекты выбранного ТО методом ОМА.
В качестве ТО выбраны генератор прямоугольных импульсов и паяльник с источником питания.

В основе ОМА лежит закон конструктивно-прогрессивной эволюции ТО. Цель ОМА заключается в составлении наиболее полного списка недостатков объектов. Решаются две задачи:
* выявление в существующих изделиях максимального числа недостатков;
* максимальное устранение недостатков во вновь разрабатываемом изделии.

Недостатки Предложения
Большой размер опасной части Уменьшить опасную часть
Плохая теплоизоляция ручки. Сделать хорошую теплоизоляцию ручки.
Неразборная ручка. Сделать ручку ремонтопригодной.
Плохое крепление провода к ручке. Использовать керамический нагревательный элемент.
Негибкость провода. Сделать привинчивающийся разъем.
Большой блок питания. Заменить блок питания тиристорным регулятором в ручке паяльника.
Непродуманный разъем соединения блока питания и паяльника. Сделать штыревой разъем.
Нет автоподачи припоя и канифоли. Разработать автоподачу припоя и канифоли.
Неудобная смена насадок. Разработать специальный зажим для смены насадок в процессе работы.
Монотонность расцветки паяльника. Выделять ручку и нагревательный элемент разными цветами.
Непрочные механические крепления нагревающей части и ручки. Предусмотреть насадку для снятия припоя.
Нетермостойкая изоляция провода. Использовать провод с термостойкой изоляцией.
Плохой нагревательный элемент. Вынести нагревательный элемент ближе к жалу.
Плохое крепление жала. Для автоподачи припоя сделать специальное жало с отверстием по середине.

Недостатки Предложения
Сложная буквенно-цифровая маркировка органов управления. Упростить буквенно-цифровую маркировку органов управления.
Отсутствие управления формой импульсов. Ввести управление формой импульсов.
Неудачная раскраска кнопок. Разнести группы кнопок и изменить их цвета на менее контрастные.
Плохие жесткие переключатели кнопок. Сделать клавишные переключатели.
Неэргономичен (Громоздкий). Уменьшить габариты.
Отсутствие возможности генерировать пачки импульсов. Предусмотреть генерацию пачки импульсов.
Нет индикации текущего режима работы. Организовать индикацию текущего режима работы.
Неудобная ручка. Сделать ручку более удобной.
Малый диапазон частот. Увеличить диапазон частот.
Нет ограничений по току. Ввести ограничения по току.
Возможное несогласование параметров. Сделать генератор в цифровой форме.
Плохое сочетание цветов (Черные кнопки кажутся нажатыми). Сделать принципиально новую индикацию на генераторе импульсов.
Требует внешнего источника питания Встроить источник питания
Ограниченные возможности генератора импульсов. Расширить возможности генератора импульсов (частота, форма импульсов и так далее).

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

- размер, устанавливающий объем пространства, в котором предстоит находить решение;

- изменяемость области, характеризует степень изменяемости области во времени и пространстве (статические и динамические);

- полнота модели, обрисовывающей область, характеризует адекватность модели, используемой для описания предоставленной области;

- определенность данных о решаемой задаче, характеризует степень точности (ошибочности) и полноты (неполноты) данных.

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

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

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

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

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

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

- способы поиска при неточных и неполных данных;

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

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

Методы решения задач, основанные на сведении 'их к поиску, зависят от

особенностей предметной области, в которой решается задача, и от

требований, предъявляемых пользователем к решению. Особенности предметной

объем пространства, в котором предстоит искать решение;

степень изменяемости области во времени и пространстве (статические и

полнота модели, описывающей область, если модель не полна, то для описания

области используют несколько моделей, дополняющих друг друга;

определенность данных о решаемой задаче, степень точности (ошибочности) и

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

поиска, можно характеризовать

1) количеством решений : одно решение, несколько решений, все решения.

2) свойствами результата: ограничения, которым должен удовлетворять

3) и (или) способом его получения.

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

можно классифицировать следующим образом:

методы поиска в одном пространстве - методы, предназначенные для

использования в следующих условиях: области небольшой размерности, полнота

модели, точные и полные данные;

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

работы в областях большой размерности;

методы поиска при неточных и неполных данных ;

методы поиска, использующие несколько моделей, предназначенные для работы с

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

Предполагается, что перечисленные методам при необходимости должны

объединяться для того, чтобы позволить решать задачи, сложность которых

возрастает одновременно по нескольким параметрам.
Поиск в пространстве состояний

Задача поиска в пространстве состояний обычно формулируется в

Пусть задана тройка (S0, F, SТ), где S0 - множество начальных

состояний (условия задачи), F - множество операторов задачи, отображающих

одни состояния в другие, SТ - множество конечных (целевых) состояний

Цель: определять такую последовательность операторов, которая

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

Процесс решения в виде графа G=(Х, Y), где X= - множество

(в общем случае бесконечное) вершин графа, состояний, а Y - множество,

содержащее пары вершин (xi, xj), (xi, xj)(X. Если каждая пара (xi, xj)

неупорядочена, то ее называют ребром, а граф - неориентированным. Если для

каждой пары (xi, xj) задан порядок (направление), то пару (xi, xj) называют

дугой (ориентированным ребром), а граф называют ориентированным

Поиск в пространстве состояний естественно представить в виде

ориентированного графа. Наличие пары (xi, xj) свидетельствует о

существовании некоторого оператора f (f(F), преобразующего состояние,

соответствующее вершине xi, в состояние xj. Для некоторой вершины xi

выделяем множество всех направленных пар (xi, xj)(Y, т.ь. множество дуг,

исходящих из вершины хi, (родительской вершины), и множество вершин

(называемых дочерними вершинами), в которые эти дуги приводят. Множество

дуг, исходящих из вершины xi, соответствует множеству операторов, которые

могут быть применены к состоянию, соответствующему вершине хi.

В множестве вершин X выделяют подмножество вершин Х0(Х,

соответствующее множеству начальных состояний (So),, и подмножество вершин

Хт(X, соответствующее множеству конечных (целевых) состояний (SТ).

Множество Хт может быть задано как явно, так и неявно, т.е. через свойства,

которыми должны обладать целевые состояния.

Отметим, что граф С может быть задан явно и неявно. Неявное задание

графа G стоит в определении множества Х0(Х (соответствующего множеству

начальных состояний) и множества операторов, которые, будучи применимы к

некоторой вершине графа, дают все ее дочерние вершины.

Итак, граф G задает пространство состояний, т.е. пространство, в

котором осуществляется поиск решения. Построение пространства

осуществляется с помощью следующего процесса. Берется некая вершина х0(Х, к

ней применяются все возможные операторы, порождающие все дочерние вершины.

Этот процесс называют процессом раскрытия вершин. Если получена целевая

вершина, то она не раскрывается. Процесс построения пространства состояний

заканчивается, когда все нераскрытые вершины являются целевыми, или

терминальными (т.е. вершинами, к которым нельзя применить никаких

операторов). В связи с тем, что пространство состояний может содержать

бесконечное количество вершин, на практике процесс порождения пространства

ограничивают либо временем, либо объемом памяти.

На практике требуется обеспечить полноту поиска, т.е. организовать

поиск так, чтобы все целевые вершины были найдены, если они существуют.

Надежным способом обеспечения полноты является полный перебор всех вершин.

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

будут перебираться вершины графа. Обычно выделяют два основных способа

поиск в глубину (сначала раскрывается та вершина, которая была построена

поиск в ширину. (вершины раскрываются в том же порядке, в котором они

Целевые вершины помечены черными квадратами, а терминальные - белыми

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

решения. При переборе всего пространства оба метода будут анализировать

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

существенно больше памяти, так как он запоминает все пути поиска (а не

один, как при поиске в глубину).

Метапространство в иерархии пространств.

При решении любой задачи многократно возникает вопрос: "что делать на следующем шаге"? В простейшем случае решение о том, что делать на следующем шаге, предопределено методом поиска решения. При поиске в абстрактных и конкретных пространствах на каждом шаге решался вопрос о том, какой из операторов, существующих в проблемной области, применить к текущему состоянию проблемной области. Вопрос о том, как решающая программа это сделает, не обсуждался. Можно оказывать не явное, а косвенное влияние на определение того, "что делается на следующем шаге в проблемной области" путем выбора того или иного метода, известного решателю. Подобный подход требует явного разграничения знаний о процессе решения и знаний о проблемной области. В последнее время наблюдается интерес к разработке систем, которые могут рассуждать о процессе получения ими решения, например планировать процесс своих рассуждений. В такой постановке речь идет о решении задачи на метауровне. Решатель в метапространстве содержит явное описание процесса организации поиска, т.е. описание состояний, операторов, условий применимости операторов, описание доступных методов (стратегий) поиска и способов их взаимодействия. Получить решение в метапространстве - это значит определить, какой метод (программа) будет применен на следующем шаге, т.е. составить метаплан решения задачи. Заметим, что метаплан, в отличие от абстрактного плана, выражается не в терминах операторов проблемной области, а в терминах методов (программ), известных решателю.

Не существует причин ограничивать метазнания одним уровнем. Примером экспертной системы, в которой для решения задач использовано метапространство и метапланирование, является система МOLGEN (см. § 1.5 и п.. 5.3.5). В МOLGEN метапространство содержит описание используемых методов: метода наименьших свершений и эвристических стратегий ("угадывания"). В зависимости от ситуации, возникающей в ходе решения задачи, МOLGEN составляет метаплан, определяющий, какой из методов и какая его компонента должны работать в текущий момент.

Итак, но аналогии с факторизацией абстрактного пространства можно говорить о разбиении метапространства на метазадачи (методы, программы). Разбиение на метазадачи является полезным методом организации, знаний в экспертных системах, однако в настоящее время еще далеко до общего теоретического осмысления данного вопроса [Вейраух,1980].

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

Поиск в альтернативных пространствах.

Предположения и мнения.

Методы исходят из молчаливой предпосылки, что знания о проблемной области и данные о решаемой задаче являются точными и полными. В рассмотренных до этого методах поиска по построению справедливо следующее: 1) все утверждения, описывающие состояние, являются истинными; 2) применение оператора к некоторому состоянию формирует некоторое новое состояние, описание которого состоит только из истинных фактов. Однако при решении любых практических задач и особенно при решении неформализованных задач распространена обратная ситуация. Эксперту приходится работать в условиях неполноты и неточности, знаний (данных) и, как правило, в условиях дефицита времени. Когда эксперт решает задачу, он использует методы, отличающиеся от формальных математических рассуждений. В математических рассуждениях каждое заключение должно строго следовать из предыдущей информации. В противоположность этому в правдоподобных рассуждениях, основанных на здравом смысле, заключения основываются на частичной информации. В этом случае эксперт делает пробные правдоподобные предположения, которые он не может доказать; тем самым вопрос об их истинности остается открытым. Все утверждения, полученные на основе этих правдоподобных предположений, также не могут быть доказаны.

Один из способов обоснования предположений заключается в том, чтобы рассматривать их как возможные значения, задаваемые по умолчанию. Например, высказав предположение, что сейчас 14 часов (посмотрев на часы), мы молчаливо предполагаем, что часы идут, и идут правильно. Обычно человек знает, что некоторые предположения верны только при определенных условиях. Если информация, указывающая на нарушение этих условий, отсутствует, то предположение может быть высказано. Другое обоснование предположения базируется на рассмотрении рассуждения как процесса с ограниченными ресурсами. Так, можно считать, что предположение (X) имеет место, если, используя ограниченные ресурсы, нельзя доказать истинность противоположного утверждения. Предположение и выводы, сделанные на его основе, должны устраняться, если появилась информация, показывающая ошибочность этого предположения. Этот аспект в построении умозаключений с использованием предположений называется не монотонностью. Любая формальная система (см. например, [Мендельсон, 1971]) является монотонной, т.е. если А, В и С есть некоторые высказывания, такие, что В выводится из А, то В будет выводиться и из А Ù С. Система немонотонна, если В выводится из А, но В выводится из А Ù С [Виноград, 1980]. Немонотонные рассуждения особенно важны при решении задач планирования и конструирования. В этих задачах пространство поиска иногда очень велико, и нет возможности предвидеть все последствия сделанного выбора. Так, например, конструктор знает, чего он хочет, но не знает, как это сделать. Поэтому при конструировании предположения выступают в виде пробных решений, последствия которых затем анализируются с точки зрения их пригодности (непригодности). Если последствия не противоречат тому, что хотел конструктор, то процесс конструирования продолжается дальше, возможно, с выдвижением новых предположений. В противном случае необходимо устранить все последствия и сделать альтернативное предположение и т.д.

Поиск в фиксированном множестве пространств.

Применение рассмотренного выше метода факторизации пространства ограничено тем, что для ряда областей не удается по частичному решению сделать заключение о его непригодности. Примерами таких областей являются задачи планирования и конструирования. Действительно, как правило, по фрагменту плана или конструкции нельзя сказать, что этот фрагмент не может являться частью полного решения. В данном и последующих двух пунктах будут рассмотрены методы поиска, использующие идею абстрактного пространства. Методы различаются предположениями природе этого пространства. Абстракция должна подчеркнуть важные особенности рассматриваемой задачи, позволить разбить задачу на более простые подзадачи и определить последовательность подзадач (план решения), приводящую к решению основной задачи. В простейшем случае, с которого мы и начнем рассмотрение, пространство поиска разбиваетсяна фиксированную последовательность подзадач (подпространств), с помощью которых можно решить любую входную задачу. Подобный метод поиска использован в экспертной системе R1 (см. § 1.5). На основании заказа покупателя на требуемую ему конфигурацию системы VАХ система R1 выдает диаграммы, изображающие пространственные взаимосвязи компонент VАХ, и указывает какие компоненты необходимы для функционирования заказанной конфигурации.

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

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

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

3.1. ПОИСК РЕШЕНИЙ В ОДНОМ ПРОСТРАНСТВЕ

Методы поиска решений в одном пространстве обычно делятся на:

3.1.1. Поиск в пространстве состояний

Задача поиска в пространстве состояний обычно формулируется в теоретико-графовой интерпретации.

Пусть задана тройка (S 0 , F, S Т ), где S 0 - множество начальных состояний (условия задачи), F - множество операторов задачи, отображающих одни состояния в другие, S Т - множество конечных (целевых) состояний (решений задачи).

Цель: определять такую последовательность операторов, которая преобразует начальные состояния в конечные.

Процесс решения в виде графа G=(Х, Y), где X= - множество (в общем случае бесконечное) вершин графа, состояний, а Y - множество, содержащее пары вершин (x i , x j ), (x i , x j ) Î X. Если каждая пара (x i , x j ) неупорядочена, то ее называют ребром, а граф - неориентированным. Если для каждой пары (x i , x j ) задан порядок (направление), то пару (x i , x j ) называют дугой (ориентированным ребром), а граф называют ориентированным (направленным). Вершины пары (x i , x j ) называют концевыми точками ребра (дуги).

Поиск в пространстве состояний естественно представить в виде ориентированного графа. Наличие пары (x i , x j ) свидетельствует о существовании некоторого оператора f (f Î F), преобразующего состояние, соответствующее вершине x i , в состояние x j . Для некоторой вершины x i выделяем множество всех направленных пар (x i , x j ) Î Y, т.ь. множество дуг, исходящих из вершины х i , (родительской вершины), и множество вершин (называемых дочерними вершинами), в которые эти дуги приводят. Множество дуг, исходящих из вершины x i , соответствует множеству операторов, которые могут быть применены к состоянию, соответствующему вершине х i .

В множестве вершин X выделяют подмножество вершин Х 0 Í Х, соответствующее множеству начальных состояний (S o ),, и подмножество вершин Х т Í X, соответствующее множеству конечных (целевых) состояний (S Т ). Множество Х т может быть задано как явно, так и неявно, т.е. через свойства, которыми должны обладать целевые состояния.

Отметим, что граф С может быть задан явно и неявно. Неявное задание графа G стоит в определении множества Х 0 Í Х (соответствующего множеству начальных состояний) и множества операторов, которые, будучи применимы к некоторой вершине графа, дают все ее дочерние вершины.

Итак, граф G задает пространство состояний, т.е. пространство, в котором осуществляется поиск решения. Построение пространства осуществляется с помощью следующего процесса. Берется некая вершина х 0 Í Х, к ней применяются все возможные операторы, порождающие все дочерние вершины. Этот процесс называют процессом раскрытия вершин. Если получена целевая вершина, то она не раскрывается. Процесс построения пространства состояний заканчивается, когда все нераскрытые вершины являются целевыми, или терминальными (т.е. вершинами, к которым нельзя применить никаких операторов). В связи с тем, что пространство состояний может содержать бесконечное количество вершин, на практике процесс порождения пространства ограничивают либо временем, либо объемом памяти.

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

Целевые вершины помечены черными квадратами, а терминальные - белыми квадратами. При использовании каждого из способов могут быть найдены все решения. При переборе всего пространства оба метода будут анализировать одинаковое количество вершин, однако метод поиска в ширину будет требовать существенно больше памяти, так как он запоминает все пути поиска (а не один, как при поиске в глубину).

3.1.2. Поиск методом редукции

При поиске методом редукции решение задачи сводится к решению совокупности образующих ее подзадач. Этот процесс повторяется для каждой подзадачи до тех пор, пока каждая из полученного набора подзадач, образующих решение исходной задачи, не будет иметь очевидное решение. Процесс решения задачи разбиением ее на подзадачи можно представить в виде специального направленного графа G, называемого И/ИЛИ-графом; Каждой вершине этого графа ставится в соответствие описание некоторой задачи (подзадачи). В графе выделяют два типа вершин: конъюнктивные вершины и дизъюнктивные вершины.

Решение задачи при поиске методом редукции (при поиске в И/ИЛИ-графе) сводится к нахождению в И/ИЛИ-графе решающего графа.

Цель процесса поиска в И/ИЛИ-графе - показать, что начальная вершина разрешима, т.е. для этой вершины существует решающий граф. Определение разрешимой вершины в И/ИЛИ-графе можно сформулировать рекурсивно следующим образом:

Конечные (целевые) вершины разрешимы, так как их решение известно по исходному предположению.

Вершина ИЛИ разрешима тогда и только тогда, когда разрешима по крайней мере одна из ее дочерних вершин.

Вершина И разрешима тола и только тогда, когда разрешима каждая из ее дочерних вершин.

Решающий граф определяется как подграф из разрешимых вершин, который показывает, что начальная вершина разрешима (в соответствии с приведенным выше определением). На рис. 3.3. разрешимые вершины зачернены, а неразрешимые оставлены белыми.

Для графа И/ИЛИ, так же как для поиска в пространстве состояний, можно определить поиск в глубину и поиск в ширину как в прямом, так и в обратном направлении. На рис. 3.4. приведен пример поиска в ширину (рис. 3.4., а) и поиска в глубину (рис. 3.4., б). На рисунке вершины пронумерованы в том порядке, в котором они раскрывались, конечные вершины обозначены квадратами, разрешимые вершины зачернены, дуги решающего графа выделены двойными линиями.

3.1.3. Эвристический поиск

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

3.1.4.Поиск методом "генерация-проверка"

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

3.2. ПОИСК В ИЕРАРХИИ ПРОСТРАНСТВ

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

Методы поиска решения в иерархических пространствах обычно делятся на:

3.2.1. Поиск в факторизованном пространстве

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

3.2.2. Поиск в фиксированном множестве пространств

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

3.2.3. Поиск в изменяющемся множестве иерархических пространств

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

3.3. ПОИСК В АЛЬТЕРНАТИВНЫХ ПРОСТРАНСТВАХ

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

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

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

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

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

Этот метод поиска называют поиском, направляемым зависимостью.

3.4. ПОИСК С ИСПОЛЬЗОВАНИЕМ НЕСКОЛЬКИХ МОДЕЛЕЙ

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

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

3.5. ВЫБОР МЕТОДА РЕШЕНИЯ ЗАДАЧ

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

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

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

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

Читайте также: