Научная литература
booksshare.net -> Добавить материал -> Физика -> Арратуна Р. -> "Оптические вычисления" -> 112

Оптические вычисления - Арратуна Р.

Арратуна Р. Оптические вычисления — М.: Мир, 1993. — 441 c.
Скачать (прямая ссылка): opticheskievichesleniya1993.pdf
Предыдущая << 1 .. 106 107 108 109 110 111 < 112 > 113 114 115 116 117 118 .. 175 >> Следующая

методика "от цели к фактам".
Процесс поиска может быть осуществлен путем следования либо по структуре
направленного графа, изображенного на рис. 10.7, а, либо по
соответствующей древовидной структуре, показанной на рис. 10.7,6. Поиск
методом направленного графа позволяет вернуться к одной из ранее
пройденных вершин графа и продолжить поиск цо другому маршруту. С другой
стороны, дерево поиска может совершить повторы при реализации стратегий.
Например, при поиске устойчивых решений узел "С" может быть пройден
повторно (например, через вершины А С F...), если первая попытка (через А
В Е С) не позволила достичь цели. Очевидным недостатком древовидной
структуры
Рис, 10.6, Иерархия стратегий поиска,
Глава 10. Оптика и символьные вычисления
285
является избыточность числа проходов, а одним из преимуществ -
использование намного меньшего объема памяти из-за того, что запоминать
предыдущую стратегию в данном случае не требуется. Выбор древовидной
структуры или графа часто определяется характером решаемой задачи, т. е.
тем, насколько велика вероятность возникновения повторения ситуаций.
Ресурсы памяти будут также являться решающим фактором.
Схемы поиска также могут отличаться порядком поиска вершин. Строго
последовательный поиск, известный как перебор в глубину, следует заданной
стратегии (например, ветви или дереву) до тех пор, пока стратегия не
приведет к успеху в достижении цели, или не будет выявлено, что пора
прекратить безуспешный поиск. В последнем случае происходит возврат к
последней пройденной вершине, имеющей еще непроверенные ветви. Такая
процедура поиска экономит ресурсы памяти, поскольку оказавшиеся
бесполезными ветви исключаются из рассмотрения, однако, если проблемная
область характеризуется длинными процедурами поисков, то перебор в
глубину может потребовать слишком больших затрат времени. Приведенный на
рис. 10.7,6 пример поиска перебором в глубине осуществляется по узлам
ABDBECACFC...
С другой стороны, в методе поиска перебором в ширину все состояния,
связанные с начальным, проверяются на соответствие поставленной цели, и
лишь после этого осуществляется переход на более глубокий уровень дерева
или графа. Если цель не была достигнута, тогда эти состояния (или
вершины) на первом уровне расширяют, т. е. генерируют и тестируют все
возможные связанные с ними состояния. Например, поиск в ширину,
осуществляемый по дереву целей, изображенному на рис. 10.7,6, происходит
в порядке прохождения вершин, А В С D Е F Н С ... до тех пор, пока не
будет достигнуто состояние цели. Данный тип поиска может оказаться очень
полезным в
Рис. 10.7, а -поиск с помощью направленного графа; б - дерево поиска,
а
6
286
Часть IV. Символьные вычисления и искусственный интеллект
системах параллельной обработки, которые будут обсуждаться в разд. 10.4.
До этого места в изложении процедуру решения проблемы и процесс
проведения рассуждений представляли как последовательность событий,
выполняемую из начального состояния в направлении состояния (состояний)
цели. Другой способ, которым иногда пользуются, исходит из заданной цели
и выполняется в обратном порядке, при этом стараются удовлетворить
начальным условиям. В обратной процедуре проведения рас-суждений,
известной среди специалистов по ИИ как способ рас-суждений "от цели к
фактам", сначала находят одно или более состояний, которые могут привести
к определению цели, и проверить, достигнуто ли соответствие с начальным
состоянием (состояниями). Если нет, то поиск продолжается. Для систем
продукций это означает, что в этом случае части "тогда" согласуются между
собой и соответственно части "если" запускаются в действие (например,
если часть "тогда" используется для нахождения более отдаленной вершины).
Конкретно выбор либо процедуры от "цели к фактам", либо процедуры "от
фактов к цели" определяется прежде всего двумя факторами - соотношением
случаев ветвления с переходом назад по телу программы и случаев ветвления
с переходом вперед, а также соотношением числа состояний цели и числа
начальных состояний. Другими словами, если сформированное дерево поиска в
конкретной проблемной области разветвляется в значительно большей степени
при прямой процедуре поиска, чем при обратной процедуре поиска, то в этом
случае процедура "от цели к фактам" будет более целесообразной. Если
разветвление в обоих направлениях приблизительно одинаково, решающее
значение приобретат число состояний. Процедура "от цели к фактам"
выглядит более привлекательной при решении задач синтеза сложных
объектов, когда существует широкий спектр исходных объектов, на основе
которых приводится синтез. Примером служит задача определения того, какие
характеристики материала необходимы для оптимального изготовления
конкретного устройства. Здесь лучше было бы начать процедуру поиска с
состояния цели (требований к устройству), чем с поисков наборов
характеристик для всех возможных материалов.
С другой стороны, в шахматах проведение рассуждений никогда не может быть
Предыдущая << 1 .. 106 107 108 109 110 111 < 112 > 113 114 115 116 117 118 .. 175 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed