Эвристическая информация
Cтраница 1
Эвристическая информация носит сугубо специальный характер и может применяться только в рамках данной задачи, в лучшем случае в рамках задач данного класса. [1]
 |
Процедура поиска решения неформализованной задачи с использованием принципа декомпозиции задачи на подзадачи способом в ширину ( я и в глубину ( б. [2] |
Другой способ состоит в использовании эвристической информации для определения на каждом шаге дальнейшего направления перебора. Для этого необходимо ввести меру перспективности вершины в виде некоторой оценочной функции. [3]
В работах [ Stefanuk, 1973; Стефанюк, 1975; Stefanuk, 1996 ] мы показали, что обычно сама исходная задача содержит определенную эвристическую информацию, необходимую для ее упрощения. Эта эвристическая информация может быть выделена на стадии первых попыток решить задачу. [4]
В случае, если существует некоторая дополнительная информация о предметной области, которая позволяет делать суждения о характере графа пространства состояний и расположения цели, говорят об эвристическом8 поиске. Эвристическая информация, опирающаяся, как правило, на предыдущий опыт, позволяет выполнять поиск в наиболее перспективных направлениях. [5]
В работах [ Stefanuk, 1973; Стефанюк, 1975; Stefanuk, 1996 ] мы показали, что обычно сама исходная задача содержит определенную эвристическую информацию, необходимую для ее упрощения. Эта эвристическая информация может быть выделена на стадии первых попыток решить задачу. [6]
Линейно упорядоченные множества альтернатив еще больше увеличивают управляющую информацию, имеющуюся в структуре предположений по умолчанию, а именно добавляется порядок, в котором должны быть испробованы альтернативы. Эта дополнительная эвристическая информация могла бы быть использована, например, при упорядочении выбора дней недели для заседания, стратегий планирования или состояний транзистора при анализе предложенной электронной схемы. [7]
К недостаткам обобщенной гистограммы можно отнести, во-первых, то, что число слагаемых равно числу реализаций ( неудобно при большом количестве N), и, во-вторых, неоднозначность оценки в зависимости от выбора h - q ( N) и конкретного вида ядра. Для оптимизации оценки, получаемой данным методом, необходима дополнительная эвристическая информация. [8]
Если мы хотим применить программу поиска с предпочтением, показанную на рис. 12.3, к какой-нибудь задаче, мы должны добавить к нашей программе отношения, отражающие специфику этой конкретной задачи. Эти отношения определяют саму задачу ( правила игры), а также вносят в алгоритм эвристическую информацию о методе ее решения. Эвристическая информация задается в форме эвристической функции. [9]
Если мы хотим применить программу поиска с предпочтением, показанную на рис. 12.3, к какой-нибудь задаче, мы должны добавить к нашей программе отношения, отражающие специфику этой конкретной задачи. Эти отношения определяют саму задачу ( правила игры), а также вносят в алгоритм эвристическую информацию о методе ее решения. Эвристическая информация задается в форме эвристической функции. [10]
Стремление сократить время поиска привело к созданию эвристических методов поиска, т.е. методов, использующих некоторую информацию о предметной области для рассмотрения не всего пространства поиска, а таких путей в нем, которые с наибольшей вероятностью приводят к цели. Один способ сокращения перебора состоит в выборе более информированного оператора, который не строит так много вершин, не относящихся к делу. Другой способ состоит в использовании эвристической информации для определения на каждом шаге дальнейшего направления перебора. Для этого необходимо ввести меру перспективности вершины в виде некоторой оценочной функции. В некоторых случаях удается ввести такую оценочную функцию, что она, сокращая перебор, не теряет свойства полноты. Чаще же используемые эвристики, существенно сокращая перебор, влекут за собой потерю свойства полноты. Как правило, оценочные функции пытаются количественно оценить расстояние от текущей вершины до конечной. Из двух вершин при одинаковой глубине перспективней та, от которой меньше расстояние до цели. Для многих приложений, в частности для экспертных систем, применение количественных оценок не позволяет эффективно направлять процесс поиска. [11]
Чтобы написать такую программу, необходимо сначала тщательно исследовать деятельность человека-эксперта. Это исследование включает наблюдения, интервьюирование и сбор статистики. Обычно эксперт имеет целый набор стратегий для определенных ситуаций. Они и составляют типичную эвристическую информацию. [12]
К достоинствам процедуры РЕВОП принадлежит возможность включения большого числа факторов и легкость счета. Однако все факторы должны задаваться в метрических шкалах. Кроме того, трудно извлечь из результатов эвристическую информацию. Не ясно, какой фактор важен, какой нет, как устроена поверхность отклика. Да и движение к оптимуму носит случайный характер. [13]
Методы поиска в глубину и ширину назьь вают слепым поиском, поскольку в этих методах порядок раскрытия вершин предопределен и никак - не зависит от расположения цели. При увеличении пространства поиска методы слепого поиска требуют чрезмерных затрат времени и ( или) памяти. Стремление сократить время поиска привело к созданию эвристических методов поиска, т.е. методов, использующих некоторую информацию о проблемной области для рассмотрения не всего пространства поиска, а таких путей в нем, которые с наибольшей вероятностью приводят к цели. Один способ сокращения перебора состоит в выборе более информированного оператора, который не строит так много вершин, не относящихся к делу. Другой способ состоит в использовании эвристической информации для определения на каждом шаге дальнейшего направления перебора. Для этого необходимо ввести меру перспективности вершины в виде некоторой оценочной функции. В некоторых случаях удается ввести такую оценочную функцию, что она, сокращая перебор, не теряет свойства полноты. Чаще же используемые эвристики, сильно сокращая перебор, влекут за собой потерю свойства полноты. Как правило, оценочные функции пытаются количественно оценить расстояние от текущей вершины до конечной. Из двух вершин при одинаковой глубине перспективней та, от которой меньше расстояние до цели. Для многих приложений, в частости для экспертных систем, применение количественных оценок не позволяет эффективно направлять процесс поиска. [14]
Мы можем резольвировать любую пару дизъюнктов, соединенных ребром, так как все ребра соединяют контрарные пары. Резольвента всегда наследует связи, соединяющие литеры-вершины дизъюнктов, инцидентных резольвированной связи. Использованная единожды связь удаляется из графа, чем достигается ограничение излишней резолюции между данной парой дизъюнктов. Множество дизъюнктов, соответствующее графу связей, невыполнимо, если мы можем вывести пустой дизъюнкт из графа связей. Связи графа могут быть выделены сверху вниз, снизу вверх или комбинацией обоих методов. Поскольку все пространство поиска проблемы известно, то на каждом шаге мы можем использовать эвристическую информацию, чтобы выделить лучших кандидатов на ре-зольвирование. Для повышения эффективности вывода используются различные стратегии упрощения графа связей, такие как удаление чистых дизъюнктов, тавтологий и поглощенных дизъюнктов. [15]
Страницы: 1