Человеческий фактор. Том 3. Часть 1 - Сальвенди Г.
ISBN 5-03-001815-8
Скачать (прямая ссылка):
3. Стратегия управления, которая указывает, какие применимые правила следует использовать, и приводит к прекращению вычислений, когда удовлетворяется условие завершение операций над базой данных.
'Зб Глава 2
Таким образом, если воспользоваться терминологией продукционных систем, граф, показанный на рис. 2.4,— это продукт применения принятой стратегии управления. Узлами на графе представлены различные базы данных, формируемые в процессе применения правил. Стратегия управления поиском на графе— это средство нахождения пути от (начального) узла, представляющего исходную базу данных, до (целевого) узла, представляющего базу данных, которая удовлетворяет условию завершения (или цели) принятой системы продукций.
В общем виде процедуру поиска на графе можно описать следующим образом.
Шаг 1. Создать граф поиска G, состоящий только из одного начального узла s. Включить s в список с именем OPEN (открытый).
Шаг 2. Создать список, называемый CLOSED (замкнутый); этот список вначале пустой.
Шаг 3. LOOP (петля): если OPEN является пустым, то осуществить выход из процедуры, сформулировав сообщения об ошибке.
Шаг 4. Выбрать первый узел в списке OPEN, вывести его из этого списка и включить в список CLOSED. Назвать этот узел узлом п.
Шаг 5. Если п является целевым узлом, осуществить выход из процедуры (успешный исход); решение получается посредством построения пути вдоль указанной от п к s в G. (Указатели формируются на шаге 7.)
Шаг 6. Расширить узел п путем генерации множества М его преемников, не являющихся предками п. Присвоить этим элементам М статус преемников п в G.
Шаг 7. Сформировать указатели на п в тех элементах М, которых еще не было ни в OPEN, ни в CLOSED. Добавить их в список OPEN. Для каждого элемента М, который уже был включен в OPEN или CLOSED, решить, изменять ли направление его указателя на п. По каждому элементу М, который уже имеется в CLOSED, решить для каждого из его потомков в G, изменять ли направление действия его указателя1*.
Шаг 8. Переупорядочить список OPEN в соответствии с произвольным критерием или эвристическим правилом.
Шаг 9. Перейти к шагу 3 (метка LOOP).
*> Если граф, на котором производится поиск, представляет собой дерево, то ии одии из преемников, формируемых иа шаге 6, ие был сформирован ранее. Поэтому элементов М нет еще ни в OPEN, ни в CLOSED. В этом случае каждый элемент М добавляется к OPEN и в дереве поиска ему присваивается статус преемника п. Если граф поиска ие является деревом, то некоторые элементы М, возможно, уже сформированы, т. е. уже присутствуют в OPEN или CLOSED.
Искусственный интеллект
97
Если при упорядочении узлов в OPEN не используется никакой эвристической информации из проблемной области, то на шаге 8 необходимо использовать некоторый произвольный критерий. Результирующая процедура поиска называется неинформированной или слепой. Процедура слепого поиска первого типа упорядочивает узлы в OPEN по возрастанию их глубины в дереве поиска1). Поиск, являющийся результатом такого упорядочения, называется поиском преимущественно в ширину. Уже показано, что поиск преимущественно в ширину гарантирует нахождение кратчайшего пути к целевому узлу при условии, что такой путь существует. При слепом поиске второго типа узлы в OPEN упорядочиваются по убыванию их глубины в дереве поиска. Узлы с наибольшей глубиной помещаются в этом списке первыми. Узлы равной глубины располагаются в произвольном порядке. Поиск, являющийся результатом такого упорядочения, называется поиском преимущественно в глубину. Для того чтобы поиск не зацикливался по одному и тому же безрезультатному пути, устанавливается граница по глубине. Узлы, глубина которых в дереве поиска превышает эту границу, никогда не формируются.
В описанных выше стратегиях слепого поиска нахождение путей от начального узла к целевому осуществляется методом полного перебора. Во многих задачах для суждения области поиска можно использовать информацию, зависящую от задачи. Этот класс поисковых процедур называется эвристическим поиском, или поиском по наилучшему совпадению, а информация, зависящая от задачи, называется эвристической информацией. На шаге 8 процедуры поиска на графе эвристическую информацию можно использовать для такого упорядочения узлов в списке OPEN, чтобы область поиска охватывала только наиболее перспективные части графа. В одном из известных методов для вычисления степени «перспективности» узлов (в аспекте кратчайшего пути) применяется вещественная оценочная функция, а узлы в OPEN упорядочиваются по возрастанию соответствующих им значений оценочной функции. Связи между узлами располагаются в произвольном порядке, но предпочтение здесь всегда отдается целевым узлам. Результаты поиска очень сильно зависят от выбранной функции оценивания. Ниже представлен полезный алгоритм поиска по наилучшему совпадению— так называемый алгоритм А*.
Пусть оценочная функция f в любом узле п имеет вид
f(n) = g(n) + h(n),
г> Для обеспечения скорейшего завершения поиска целевые узлы следует помещать в самое начало списка OPEN.
