Введение в теорию игр. Жариков И.А - 48 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

48
образует свое множество результирующих задач (этот перебор и озна-
чает поиск на И/ИЛИ-графе задачи).
Самый важный вопрос при таком способе редукции задач состоит
в том, как найти кандидаты в ключевые операторы. Один из способов,
предложенных и опробованных впервые в одной из наиболее извест-
ных систем искусственного интеллекта GPS, заключается в выявлении
различий для начального и целевого состояний задачи.
Различие легче всего формализовать как несоответствие различ-
ных элементов описаний начального и целевого состояний. Если на-
чальное состояние является целевым, то различий между ними нет, и
задача решена.
К примеру, в задаче об обезьяне и банане различием можно счи-
тать неравенство соответствующих элементов списков, описывающих
два состояния. Тогда при сравнении состояний (Т
О
, П, Т
Я
, О) и (Т
Я
, П,
Т
О
, 1) выявляются три различия – соответственно в первых, третьих и
четвертых элементах списков.
С каждым различием в системе GPS был связан один или не-
сколько операторов, призванных устранять или уменьшать это разли-
чие. Эти операторы и являлись по сути кандидатами в ключевые.
На каждом этапе работы система определяла различие между текущим
состоянием (объектом) задачи и целевым состоянием (объектом), а
затем выбирала и пыталась применить оператор для уменьшения най-
денного различия. В общем случае операторы включали в себя преду-
словия (условия применимости), выполнение которых было необходи-
мо для их применения, тогда GPS сводила исходную задачу к задаче
достижения нужного условия.
В задаче об обезьяне естественно связать различия и операторы-
кандидаты в ключевые следующим образом:
• различие в первом элементе списка-описания состояния (по-
ложение обезьяны в плоскости пола) – операторы Перейти и Передви-
нуть;
• различие во втором элементе (положение обезьяны по верти-
кали) – оператор Взобраться;
• различие в третьем элементе (положение ящика) – оператор
Передвинуть;
• различие в четвертом элементе (содержимое руки обезьяны) –
оператор Схватить.
Ясно, что для реализации рассмотренных идей в виде алгоритма
или программы должна быть, во-первых, специальная процедура срав-
нения описаний состояний и вычисления различий. Во-вторых, необ-

Страницы