Научная литература
booksshare.net -> Добавить материал -> Психология -> Сальвенди Г. -> "Человеческий фактор. Том 3. Часть 1" -> 41

Человеческий фактор. Том 3. Часть 1 - Сальвенди Г.

Сальвенди Г. Человеческий фактор. Том 3. Часть 1 — М.: Мир, 1991. — 487 c.
ISBN 5-03-001815-8
Скачать (прямая ссылка): chelovecheskiyfactort3ch11991.djvu
Предыдущая << 1 .. 35 36 37 38 39 40 < 41 > 42 43 44 45 46 47 .. 198 >> Следующая

100 Глава 2
Легко видеть, что алгоритм А* — это по своей сути алгоритм поиска на графе, в котором для упорядочения узлов используется функция оценивания /(«). Отметим, что, поскольку величины g(n) и h(n) складываются, важно, чтобы h(n) характеризовало стоимость перехода из узла п в целевой узел.
Цель процедуры поиска заключается в нахождении пути в пространстве состояний задачи от исходного состояния к целевому. Такой поиск может осуществляться в двух направлениях: 1) вперед — из исходных состояний и 2) назад — из целевых состояний. Правила в продукционной системе могут использоваться для построения прямых рассуждений из исходных состояний и для обратных рассуждений — от целевых состояний. При построении прямого логического вывода левые части или предусловия сравниваются с текущим состоянием, а правые части (результаты) используются для формирования новых узлов, до тех пор пока не будет достигнута цель. При обратном логическом выводе с текущим состоянием сравниваются правые части, а левые используются для формирования новых узлов, представляющих новые целевые состояния. Процесс продолжается до тех пор, пока одному из этих целевых состояний не будет соответствовать известное исходное состояние.
Если процесс поиска представлять в виде процедур применения некоторого набора правил, то конкретные алгоритмы поиска можно легко описывать безотносительно к направлению поиска. Конечно, существует и другая возможность, а именно ведение поиска одновременно вперед из исходного состояния и назад из целевого состояния, до тех пор пока два пути не встретятся где-то посередине. Эта стратегия называется двунаправленным поиском.
2.3. Упрощение постановки задачи
Другой подход к решению проблем заключается в упрощении исходной постановки задачи. Основная идея здесь заключается в обратном рассуждении от поставленной задачи с последовательным разукрупнением задачи на подзадачи все меньшего размера, до тех пор пока первоначальная задача не будет, наконец, сведена к набору элементарных задач, решения которых очевидны. Оператор упрощения постановки задачи преобразует описание задачи в набор упрощенных описаний или опи-саний-преемников. Для каждого данного описания задачи может существовать множество операторов упрощения, применимых к этому описанию. Каждый из них генерирует свой собственный набор подзадач. Некоторые из этих подзадач, од> нако, могут не иметь решений, поэтому может потребоваться опробование нескольких операторов с целью формирования на-*
Искусственный интеллект
101
бора, все члены которого имеют решения. Таким образом, здесь вновь необходим процесс поиска.
Сведение задачи к нескольким наборам задач-преемников можно изобразить в виде графоподобной структуры. Предположим, что исходную задачу А можно решить путем решения всех ее подзадач В, С и D; тогда входящие дуги узлов В, С и D получают метку AND, а узлы В, С и D называются И-узламв. В то же время, если задача В может быть решена в результате решения любой из двух подзадач Е и F, то появляется ИЛИ-дуга. Эти взаимосвязи представлены в виде И/ИЛИ-графа1*, показанного на рис. 2.5. Легко видеть, что методы поиска, которые обсуждались в разд. 2.2, относятся к ИЛИ-графам, в каждом из которых требовалось найти один путь от начального узла к целевому.
Пример 3
Конъюнктивно - дизъюнктивный граф для задачи об обезьяне и бананах показан на рис. 2.6. Здесь конфигурация задачи представлена в виде тройки (S, F, (?),где S — множество начальных состояний, F — множество операторов, G — множество целевых состояний. Поскольку множество операторов F в данной задаче не изменяется, а исходным состоянием является (Л, О, В,
0), символ F можно опустить и обозначить задачу просто как ({(Л, 0, В, 0)}, G). Один из способов выбора операторов упрощения задачи заключается в использовании понятия «невязки»2).
Как следует из примера 1, в данном случае F={fi, f2, /з, /4} = = {GOTO([/), PUSHBOX(V), CLIMBBOX, GRASP}. Сначала мы вычисляем величину различия для исходной задачи. Причина, почему список (Л, 0, В, 0) не удовлетворяет целевому тесту, состоит в том, что последний элемент не равен 1. Оператором, который обеспечивает уменьшение этой невязки, является f4=GRASP. Используя f4 для упрощения исходной за-
?> Удобно называть И-элементы конъюнктивными, ИЛИ-элементы — дизъюнктивными, а И/ИЛИ-граф — конъюнктивно-дизъюнктивным. — Прим. ред.
2> Нестрого говоря, невязка для (S, G, F) — это частичный список причин, по которым члеи S не проходит целевой тест, определяющий множество Q. (Если некоторый элемент S принадлежит С, то задача решена и разницы нет.)
граф.
Элементарная Элементарная Элементарная Элементарная задача задача задача задача,
Рис 2 6 Представление задачи об обезьяне и бананах в виде И/ИЛИ-графа.
Искусственный интеллект
103
дачи, мы получаем следующие две подзадачи: ({(Л, 0, В, 0)}, Gft) и ({Msi)}> G), гДе Gf*—множество описаний состояний, к которому применим оператор /4, a — состояние в Gf4, которое получено в результате решения ({(Л, 0, В, 0)}, Gf4).
Для решения задачи ({(А 0, В, 0)}, Gf4) мы сначала определяем ее невязку. Состояние, описываемое с помощью {А, 0,
Предыдущая << 1 .. 35 36 37 38 39 40 < 41 > 42 43 44 45 46 47 .. 198 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed