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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

42
1, 2, 3: A
→
C
1, 2: A
→
B
3: A
→
C
1, 2: B
→
C
2: B
→
C
1: A
→
C
1: B
→
A
1: A
→
C
2: A
→
B
1: C
→
B
Рис. 11
При решении задач методом редукции, как и при решении в про-
странстве состояний, может возникнуть необходимость перебора. Дей-
ствительно, на каждом этапе редукции может оказаться несколько
применимых операторов (т.е. способов сведения задачи к подзадачам)
и, соответственно, несколько альтернативных множеств подзадач. Не-
которые способы, возможно, не приведут к решению исходной задачи,
поскольку обнаружатся неразрешимые подзадачи, другие же способы
могут дать окончательное решение. В общем случае для полной ре-
дукции исходной задачи необходимо перепробовать несколько опера-
торов. Процесс редукции продолжается, пока исходная задача не будет
сведена к набору элементарных задач, решение которых известно.
Аналогично представлению в пространстве состояний, формали-
зация задачи в рамках подхода, основанного на редукции задач, вклю-
чает определение следующих составляющих:
− формы описания задач
/
подзадач и описание исходной задачи;
− множества операторов и их воздействий на описания задач;
− множества элементарных задач.
Эти составляющие задают неявно пространство задач, в кото-
ром требуется провести поиск решения задачи.
Что касается формы описания задач
/
подзадач, то часто их удобно
описывать в терминах пространства состояний, т.е. задавая начальное
состояние и множество операторов, а также целевое состояние или его
свойства. В этом случае элементарными задачами могут быть, к при-
меру, задачи, решающиеся за один шаг перебора в пространстве
состояний.
В дополнение отметим, что подход с использованием пространст-
ва состояний можно рассматривать как вырожденный случай подхода,
основанного на редукции задач, так как применение оператора в про-
странстве состояний сводит обычно исходную задачу к несколько

Страницы