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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

47
(S
I
, O, S
G
), где S
I
и S
G
– соответственно начальное и целевое состояния,
или же как двойки (S
I
, S
G
), если предполагать неизменным при поиске
множество O операторов преобразования состояний.
Часто при поиске в пространстве состояний нетрудно обнаружить
один оператор, который обязательно должен входить в решение задачи
(по сути, применение этого оператора есть необходимый шаг решения
этой задачи). В графе-пространстве состояний этому оператору обыч-
но соответствует дуга, связывающая две практически отдельные части
графа. Такой оператор и называется ключевым оператором в про-
странстве состояний. К примеру, в задаче о пирамидке ключевым опе-
ратором был оператор переноса на нужный колышек самого большого
диска 3.
Ключевой оператор может быть использован для следующего
способа сведения исходной задачи к подзадачам. Пусть:
Op – найденный в пространстве состояний задачи ключевой опе-
ратор (Op ∈ O);
S
Op
– множество состояний, к которым применим ключевой опе-
ратор Op;
Op(s) – состояние, полученное в результате применения ключево-
го оператора Op к состоянию s (s ∈ S
Op
).
Тогда исходную задачу можно свести к трем подзадачам:
− первая задача (S
I
, S
Op
) состоит в поиске пути от начального со-
стояния исходной задачи к одному из состояний, к которому приме-
ним ключевой оператор Op;
− вторая задача является элементарной, она заключается в при-
менении этого ключевого оператора;
− третья задача (Op(s), S
G
) состоит в поиске пути от состояния,
полученного применением ключевого оператора, к целевому состоя-
нию исходной задачи.
Порядок решения перечисленных задач существен (третья задача
не может быть решена раньше первой и второй, также как вторая –
раньше первой). Для решения первой и третьей задач может быть при-
менен опять метод редукции с помощью ключевого оператора, или же
их решение может быть найдено непосредственным поиском в про-
странстве состояний.
Для большинства задач не удается всегда однозначно выделить
ключевой оператор, гораздо чаще удается найти множество операто-
ров-кандидатов в ключевые (т.е. операторов, с большой вероятностью
могущих стать ключевыми). Таким образом, в общем случае необхо-
дим процесс перебора операторов-кандидатов, каждый из которых

Страницы