Метасистемный подход в управлении - часть 72

 

287 

   

Таблица Г.12 - Число G-структур в &

n

+

 и &

n

, 

С-структур и их 

классов i-эквивалентности и классов 

l

-эквивалентности для n ≤ 7 

n 

1 

2 

3 

4 

5 

6 

7 

|

G

n

+

| 

1 

4  18  166 

7,579  7,828,352 2,414,682,040,996

|

G

n

| 

1 

2 

9 

114 

6,894  7,785,062 2,414,627,396,434

|&

n

| 

1 

2 

8 

64 

1,024 

32,768 

2,097,152 

|

G

n

+

/

i

|  1 

3 

8 

28 

208 

 

 

|

G

n

/

i

 |

  

1 

2 

5 

20 

180 

 

 

|&

n

/

i

 |  1 

2 

4 

П 

34 

156 

1,044 

|

G

n

+

/

l

|  1 

3 

7 

15 

31 

63 

127 

|

G

n

/

l

 |  1 

2 

5 

12 

27 

58 

121 

|&

n

/

l

 |  1 

2 

4 

7 

11 

16 

22 

где показатель 

п(п 

— 1)/2 — общее число возможных ребер в графе, опреде-

ленном  на 

N

n

. 

Ясно  также,  что  |

G

п

/1|=п(п—1)/2+1. 

Вычисление  |

R

n

/i

|  для 

заданного более сложно, но эта задача уже решена в теории графов (смотри 
раздел  Г.11).  Приведенные  в  таблице  Г.12  значения  |

G

+

n

|, |

G

+

n

/i

|

, 

|

G

+

n

/

l

|, 

|

G

п

|, |

G

n

/i

|

 

и |

G

n

/l

|

 

известны только для 

п≤7.

 

Введем  упоминавшиеся  уже  структуры  еще  одного  типа.  Это  такие 

структуры,  для  которых  при  работе  с  вероятностными  системами для опре-
деления  несмещенной  реконструкции  не  нужна  итеративная  процедура  со-
единения. Обычно их называют 

ациклическими структурами.

 

Для  решения  задачи  реконструкции  наибольший  интерес  представля-

ют ациклические структуры особого типа, которые можно было бы назвать 

строго  ациклическими  структурами 

или L-структурами. G-структура 

G

i

∈G

n

 

является 

L

-структурой тогда и только тогда, когда не существует 

такой пары (

а

, 

b

)

∈N

2

n

, что она входит в некий элемент G

i

 и связана через 

несколько  соединенных  элементов.  Будем  множество L-структур  для  не-
коего 

п 

обозначать 

L

n

. 

Определим  множество 

L

п

 

формально.  Пусть  дана G-структура 

G

i

∈&

n

. 

Для любой пары (

a

, 

b)

∈N

2

n

 

пусть 

X

a,b

={x

|

x

∈G

i

, 

{

а

, 

b

⊂ х}.

 

Тогда 

G

i

 

является L-структурой 

(G

i

∈L

n

) 

тогда и только тогда, когда не суще-

ствует пары (a, b)

∈

N

2

n

, являющейся элементом транзитивного замыкания 

r

n

(G

i 

- 

Х

а,b 

).

 

Очевидно, например, что все структуры из множества 

G

3 

(рисунок 

Г.16),  за  исключением  структуры 

G

2

={{1, 2}, {2, 3}, (3, 1}}, явля-

ются L-структурами. В  множестве 

G

4

 только три структуры не  являются 

L-структурами.  Они  принадлежат  к  одному  и  тому  же  классу 

i

-эквива-

лентности,  который  можно,  например,  представить  С-структурой 
С={{1, 2}, {2, 3}, {3, 4}, {4, 1}}. В  самом  деле,  транзитивное  замыка-
ние  r

4

(С - 

X

1,2

)

-  это  N

4

,  и,  следовательно,  пара (1, 2) является  ее  элемен-

том. 

 

288 

   

L-структуры отличаются тем, что для них не нужно использовать ите-

ративную процедуру соединения независимо от порядка, в котором объеди-
няются элементы рассматриваемой L-структуры. Ациклические структуры, 
не являющиеся L-структурами, этим замечательным  свойством не обла-
дают.  Для  таких  структур,  чтобы  избежать  применения  итеративной  про-
цедуры  соединения,  нужно  применять  базовую  процедуру  соединения  к 
элементам,  расположенным  в  определенном  порядке.  Определение  таких 
порядков  требует  сложных  вычислений  и  проверок,  так  что  методологиче-
ское значение таких структур существенно уступает значению L-структур. 

С  помощью  различных  понятий,  введенных  в  этом  разделе,  можно 

более конкретно сформулировать задачу реконструкции. Дана обобщенная 
система  и  множество  заданных  пользователем  реконструктивных  гипотез 
(базирующихся на множестве 

G

п

, &

п

, P

п

 

или 

L - 

cтpyктyp). Решение зада-

чи  реконструкции  сводится  к  выбору  подмножества  данного  множества  в 
соответствии  с  некоторыми  требованиями.  Обычно  требуется,  чтобы: 1) 
расстояния,  соответствующие  выбранным  гипотезам,  были  как  можно 
меньше  и 2) сами  гипотезы  были,  возможно,  более  уточненными.  Оба  эти 
требования  предполагают  упорядочение  множества  реконструктивных  гипо-
тез.  Упорядочение  в  соответствии  с  требованием 2 фиксировано - это  час-
тичное упорядочение по структурному уточнению с решеткой, свойства кото-
рой описаны выше. Упорядочение согласно требованию 1 - его можно назвать 

упорядочением по расстоянию 

— не фиксировано. Оно зависит от данной 

обобщенной системы и выбранного типа расстояния и определяется только вы-
числением несмещенных реконструкций и расстояний отдельных реконструк-
тивных гипотез. 

Если  используется  расстояние,  определяемое  по  формуле  (Г.40) 

для  вероятностных  систем  [или  по  формуле  (Г.42)  для  возможностных  сис-
тем], которое является мерой количества информации, потерянной при замене 
обобщенной  системы  реконструктивной  гипотезой,  то  существует  опреде-
ленное 

предупорядочение по расстоянию: 

информационное расстояние моно-

тонно  не  убывает  с  увеличением  уточнения  реконструктивных  гипотез. 
Кроме  того,  оба  варианта  информационного  расстояния 

аддитивны 

для 

любого пути на используемой решетке уточнения. Это значит, что 

D 

(

f 

x

, 

f 

z

) 

=D 

(

f 

x

, 

f 

y

) + D (f 

y

, f

 

z

) (Г.43) 

для любых трех реконструктивных гипотез 

х, у, z 

одной обобщенной сис-

темы, таких, что 

x ≥ y ≥ z. 

Свойства предупорядоченности и аддитивности 

очень  полезны  при  решении  задачи  реконструкции  и  придают  особую  важ-
ность информационному расстоянию. В дальнейшем при обсуждении задачи 
реконструкции всегда будет предполагаться, что используется соответст-
вующая  версия  информационного  расстояния  (то  есть  вероятностная  или 
возможностная, базовая или порождающая). 

Сочетание  упорядочения  по  расстоянию  с  упорядочением  по  уточнению 

образует  объединенное  упорядочение  для  задачи  реконструкции.  Теперь 
множество решений задачи реконструкции характеризуется с помощью этого 
комбинированного упорядочения следующим образом: это множество пред-

 

289 

   

ставляет собой такое подмножество реконструктивных гипотез, в которое не 
входят  гипотезы,  худшие,  чем  любая  другая  гипотеза.  Слово  «худшие»  ис-
пользуется здесь в обычном смысле: гипотеза 

h

1

 

хуже гипотезы 

h

2

 тогда 

и  только  тогда,  когда  или 

h

1

 

является  менее  уточненной  и  ее  расстояние 

не меньше, чем у 

h

2

 

или у 

h

1

, 

большее расстояние, чем у 

h

2

, и в то же время 

она не является более уточненной, чем 

h

2

. Элементы этого множества реше-

ний будем называть 

подходящими реконструктивными гипотезами.

 

Теперь  видно  совершенное  сходство  задачи  реконструкции  с  дву-

мя рассмотренными выше задачами - задачей определения подходящих сис-
тем с поведением (раздел В.4 и В.6) и задачей определения подходящих уп-
рощений заданной системы с поведением (раздел В.9). Если упорядочение 
по  нечеткости  и  упорядочение  по  сложности  из  этих  задач  сопоста-
вить  соответственно  с упорядочением по расстоянию и упорядочением 
по  уточнению  из задачи реконструкции, то сходство этих трех задач станет 
очевидным.  Предоставляем  читателю  использовать  это  сходство  для  фор-
мального определения комбинированного упорядочения и множества реше-
ний для задачи реконструкции. 

 

                                              Структурные                                       Обобщенная  
                                                ограничения                                      система В

 

                       Средстда порождения

 

 

 

 
 
 
 
 
 
Рисунок Г.25 - Общая схема процесса решения задачи реконструкции 

Мы видим, что задачи, связанные с подъемом по эпистемологической ие-

рархии систем, а также с упрощением систем, образуют важнейшую кате-
горию задач, имеющих следующие общие черты: 
ДАНО: 
множество 

X 

рассматриваемых систем; 

Процедура  порождения 

реконструктивных гипотез

 

Реконструктидные 

гипотезы

Процедуры  оценки рекон-

структивных гипотез

 

Средства оценки и критерии

Вывод

 

Реконструктивная система 

и ее характеристики

 

Процедуры принятия ре-

шения

 

Критерии принятия решения

Продолжение работы с 

множеством реконст-

руктидных гипотез X 

X 

Стоп

 

290 

   

множество отношений порядка 

≤

≤

≤

c

b

a

,

,

 на 

X.  

МНОЖЕСТВО РЕШЕНИИ: 

)},

y

x

x

y

)(

X

y

(

|

X

x

{

X

*

*

s

≤

≤

⇒

∈

∀

∈

=

 

где 

≤

*

 - объединенный порядок предпочтения на 

X, 

определенный для 

всех 

х, у

∈Х 

следующим образом: 

y

x

*

≤

 тогда и только тогда, когда 

y

x

a

≤

, 

и 

y

x

a

≤

, и 

y

x

c

≤

, и ... 

В процессе решения задачи реконструкции необходимы три 

набора процедур: 

1) процедуры порождения всех нужных реконструктивных гипотез; 
2)  процедуры  оценки  и  сравнения  порожденных  реконструктивных  ги-

потез с точки зрения целей задачи реконструкции; 

3)  процедуры,  которые  на  соответствующих  этапах  процесса  решения 

задачи принимают решение о том, какие из порожденных реконструктив-
ных гипотез должны быть включены в множество решений, какие исполь-
зованы  для  дальнейшего  порождения  реконструктивных  гипотез  и  должен 
ли процесс решения продолжаться или закончиться. 

На  рисунке  Г.25  показано,  каким  образом  эти  три  набора  процедур 

объединяются в единый процесс решения. Ядром процесса является порож-
дение  всех  подходящих  реконструктивных  гипотез.  Удобно  это  делать, 
порождая  соответствующие  структуры,  которые  затем  интерпретируются 
как  реконструктивные  гипотезы  для  заданной  обобщенной  системы.  Ин-
терпретация  эта  сводится  к  установлению  соответствия  между  перемен-
ными обобщенной системы и целыми числами, которыми идентифицированы 
узлы структур, а также к вычислению, если нужно, проекций обобщенной 
функции  поведения.  Порожденные  структуры  можно  разными  способами 
сократить, что уменьшает время вычислений и их цену, а также, возможно, 
и по другим соображениям. Например, можно выбрать подмножество со-
ответствующих G-, С-  или L-структур  или  ограничиться  рассмотрением 
только  тех  уровней  уточнения  (классов 

l

-эквивалентности),  для  которых 

потеря информации не превышает некоторого заданного пользователем зна-
чения.  Таким  образом,  процесс  порождения  реконструктивных  гипотез  мо-
жет  быть  ограничен  либо  набором  рассматриваемых  структур,  либо  огра-
ничениями на способ порождения. 

Для  достижения  гибкости  в  решении  задачи  реконструкции  УРСЗ 

должен  располагать  разнообразным  набором  способов  порождения,  но 
этот вопрос находится за пределами проблем, связанных с архитектурой 
УРСЗ.  Это  способы  порождения  соответствующих  уточнений  (или  укрупне-
ний)  имеющихся  реконструктивных  гипотез,  примерами  чему  служат RG-
процедура и RС-процедура (и их укрупняющие аналоги). 

Как  уже  говорилось  выше,  порождение  структур  также  может  быть 

организовано  на  нескольких  уровнях  вычислений.  Так,  например, RС-