close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
УДК 519.71
Вестник СПбГУ. Сер. 1, 2004, вып. 1 (№ 1)
А. Ю. Пономарева, М. К. Чирков
ОПТИМАЛЬНЫЕ ФОРМЫ ЗАДАНИЯ ОБОБЩЕННЫХ
КОНЕЧНО-НЕСТАЦИОНАРНЫХ АВТОМАТНЫХ МОДЕЛЕЙ∗
Введение. В настоящее время стационарные автоматы достаточно успешно используются в качестве математических моделей стационарных дискретных систем и
процессов определенного вида. Однако дальнейшее расширение сферы их применения
для целей математического моделирования более сложных дискретных систем и процессов сталкивается с непреодолимыми трудностями, особенно при попытке их использования для математического моделирования множеств нестационарных одновременно
действующих взаимосвязанных дискретных систем и протекающих в них процессов. В
этих случаях требуется существенное усложнение самого понятия конечного автомата прежде всего за счет введения нестационарности и неоднозначности его структуры,
причем необходимость сохранения концепции конечности автомата требует такого его
определения, чтобы обеспечивалась конечность задания параметров его абстрактной
структуры на бесконечном отрезке времени.
В работе [1] был предложен новый удовлетворяющий этим условиям способ реализации нестационарных конечно-автоматных моделей, основу которого составляет задание
конечного множества стационарных автоматов и специального закона их распределения
во времени. Подобный способ, в частности, был успешно использован ранее в работах
по построению теории и методов оптимизации обобщенных автоматов с периодически
меняющейся структурой [2–6]. Он же использован в данной работе при определении
принципиально более сложной нестационарной конечно-автоматной модели — конечнонестационарного, обобщенного над частично упорядоченным полукольцом автомата, у
которого все параметры абстрактной структуры неоднозначно меняются во времени в
соответствии со специальным законом, описываемым структурным графом, который
может содержать разветвления, параллельные ветви и циклы. Естественным первым
шагом на пути построения теории таких нестационарных автоматов, представляющих
существенно большие возможности при решении задач математического моделирования, является исследование проблемы приведения заданного конечно-нестационарного
обобщенного автомата к некоторой оптимальной стандартной (канонической) форме.
Именно этой проблеме и посвящена данная работа
1. Исследуемая автоматная модель. Условимся в дальнейшем обозначать для
краткости символом R любое заданное частично упорядоченное полукольцо. Введем
также обозначение Rm,n для множества всех (m × n)-матриц с элементами из полукольца R.
Пусть X, A, Y есть алфавиты (конечные, непустые упорядоченные множества), соответственно, входных символов, состояний и выходных символов. Условимся называть
элементарной автоматной структурой, заданной над частично упорядоченным полукольцом R, систему
Aν = Xν , Aν , Aν , Yν , {R(ν) (x, y)},
(1)
∗
Работа выполнена при финансовой поддержке РФФИ (грант № 01-01-00334).
c А. Ю. Пономарева, М. К. Чирков, 2004
33
где Xν ⊆ X, Aν , Aν ⊆ A, |Aν | = mν , |Aν | = mν , Yν ⊆ Y , и {R(ν) (x, y)} есть совокупность матриц весов переходов из состояний алфавита Aν в состояния алфавита Aν , где
R(ν) (x, y) ∈ Rmν ,mν есть матрица, соответствующая паре (x, y), x ∈ Xν , y ∈ Yν .
Пусть задано конечное упорядоченное множество
элементарных
n
n автоматных
n структур A = {A1 , A2 , . . . , An } вида (1), такое, что ν=1 Xν = X, ν=1 Yν = Y , ν=1 (Aν ∪
Aν ) = A, |A| = m, и конечное упорядоченное множество финальных распределений
Q = {q(1) , q(2) , . . . , q(k) } (векторов-столбцов с элементами из R) весов состояний в ал
фавитах A(σ) ⊆ A, σ = 1, k.
Конечно-нестационарным обобщенным автоматом, заданным над частично упорядоченным полукольцом R, назовем систему
f, ϕ), Q,
A = X, A, Y, r, G(G, C, c0 , C,
(2)
где G есть структурный граф автомата (конечный, ориентированный, нагруженный
граф), имеющий:
— конечное множество вершин C = {c0 , c1 , . . . , cd −1 }, d ≥ k, с выделенными начальной вершиной c0 , для которой заданы алфавит состояний A(0) ⊆ A и начальное
распределение r (вектор-строка с элементами из R) весов этих состояний, и подмноже ⊆ C конечных вершин C
= {cj1 , cj2 , . . . , cj }, k ≤ d ≤ d ;
ством C
d
— конечное множество направленных ребер G, соединяющих вершины графа;
— однозначную функцию f : G → A, приписывающую каждому ребру одну из
элементарных автоматных структур;
→ Q, приписывающую каждой конечной вершине
— однозначную функцию ϕ : C
графа одно из финальных распределений весов состояний.
2. Спектр обобщенных отображений. Пусть задан конечно-нестационарный
обобщенный автомат (2). Выделим в структурном графе G какую-либо конечную вер и пусть этой вершине приписан вектор q(σ) ∈ Q. Рассмотрим один из
шину ci ∈ C
путей Ω0i , ведущий из начальной вершины c0 в вершину ci графа, и выпишем последовательность элементарных автоматных структур, отмечающих ребра, образующие
этот путь. Пусть это будут Aν1 , Aν2 , . . . , Aνt , то есть путь проходит через t отмеченных ребер графа. Рассмотрим любую пару слов (w, v), w = xs1 xs2 . . . xst , xsj ∈ X,
v = yl1 yl2 . . . ylt , ylj ∈ Y , одной длины t в алфавитах X и Y (множество всех таких пар
слов при t = 0, 1, 2, . . . обозначим (X × Y )∗ ). Весом отображения слова w в слово v, порождаемого путем Ω0i структурного графа G автомата A при заданном распределении
r, назовем величину
t
(νj ) (xsj , ylj )
R
Φi (w, v) = r
q(σ) ,
(3)
j=1
(νj ) (xsj , ylj ) получена из матрицы
где при xsj ∈ Xνj , ylj ∈ Yνj , j = 1, t, матрица R
(νj )
R (xsj , ylj ) дополнением нулевыми строками, соответствующими состояниям, присутствующим в алфавите Aνj−1 и отсутствующим в алфавите Aνj , и нулевыми столбцами, соответствующими состояниям, присутствующим в алфавите Aνj+1 и отсутствую(σ) получены путем такой же корректировrиq
щим в алфавите Aνj (при этом вектора (σ)
ки векторов r и q , условно считая, что элементам r соответствует алфавит Aν0 =
= A(0) , а элементам q(σ) алфавит Aνt+1 = A(σ) ), а при xsj ∈Xνj или ylj ∈Yνj ,
(νj ) (xsj , ylj ) ≡ O.
R
34
0i множество всех путей в структурном графе автомата, веОбозначим символом Ω
(t) — множество
дущих из начальной вершины c0 в конечную вершину ci , и символом Ω
0i
всех таких путей, имеющих длину t. Обобщенным отображением, индуцируемым конечной вершиной ci структурного графа автомата A при заданном r, назовем отображение:
i : (X × Y )∗ → R,
Φ
определяемое выражением
i (w, v) =
Φ
(t)
(t)
Ωoi ∈Ωoi
0,
Φi (w, v),
(t) = Λ,
при Ω
oi
(t)
при Ω = Λ,
(4)
oi
где |w| = |v| = t, t = 0, 1, . . . , и Λ — пустое множество. Будем говорить, что обобщенное
i является нулевым отображением Φ
i = 0, если для всех пар слов (w, v) ∈
отображение Φ
∗
i (w, v) = 0.
(X × Y ) имеем Φ
В целом автомат A будет индуцировать спектр взаимосвязанных обобщенных отображений
j2 , . . . , Φ
j },
= {Φ
j1 , Φ
(5)
Φ
d
соответствующих различным конечным вершинам cji , i = 1, d, его структурного графа.
договоримся в дальнейшем не учитывать.
При этом нулевые отображения в спектре Φ
Таким образом, в отличие от стационарных обобщенных автоматов, каждый из автоматов типа (2) описывает не один, а конечное множество взаимосвязанных и взаимодействующих друг с другом последовательных процессов «нечеткого» отображения
множества слов в алфавите X в множество слов в алфавите Y , результатом которых
является соответствующий спектр обобщенных отображений (5), индуцируемых автоматом (2). При этом задание конечно-нестационарного обобщенного автомата A (2) может, в частности, служить автоматным способом задания соответствующих спектров
обобщенных отображений (5).
3. Постановка задачи. Пусть над частично упорядоченным полукольцом R заданы два конечно-нестационарных обобщенных автомата, имеющих одинаковые входной
X и выходной Y алфавиты, — автомат A (2) и автомат
, f , ϕ ), Q ,
A = X, A , Y, r , G (G , C , c0 , C
(6)
.
индуцирующий при заданном r спектр взаимосвязанных обобщенных отображений Φ
Автоматы (2) и (6) эквивалентны, если они индуцируют одни и те же спектры
=Φ
.
взаимосвязанных обобщенных отображений, то есть, если Φ
В определении конечно-нестационарных обобщенных автоматов типа (2) форма их
задания сформулирована в самом общем виде. Вместе с тем в целях построения теории
таких автоматов и использования их при решении задач математического моделирования целесообразно выработать некоторую единую оптимальную форму задания этих
автоматов, к которой с помощью специально разработанной процедуры можно было бы
свести любой автомат типа (2), произвольно заданный в соответствии с приведенным
определением.
Условимся говорить, что конечно-нестационарный обобщенный автомат A находится в канонической форме, если выполняются следующие условия:
а) любые вершины ci , cj ∈ C структурного графа автомата не имеют ни одной пары
однонаправленных соединяющих их ребер;
35
б) множество элементарных автоматных структур A (множество финальных распределений весов состояний Q) содержит все элементы, встречающиеся в отметке ребер (конечных вершин) структурного графа, и не содержит одинаковых элементов и
элементов, не встречающихся в отметке ребер (конечных вершин) структурного графа
автомата A;
в) для каждой из элементарных автоматных структур (1), а также начального r и
финальных q(σ) , σ = 1, k, распределений весов состояний выполняются условия:
— если ai ∈ Aν , то существуют такие x ∈ Xν , y ∈ Yν , что строка матрицы R(ν) (x, y),
соответствующая состоянию ai , содержит хотя бы один ненулевой элемент;
— если aj ∈ Aν , то существуют такие x ∈ Xν , y ∈ Yν , что столбец матрицы R(ν) (x, y),
соответствующий состоянию aj , содержит хотя бы один ненулевой элемент;
— начальное r и финальные q(σ) , σ = 1, k, распределения весов состояний не содержат нулевых элементов;
г) если в вершину ci структурного графа автомата входят h ребер, отмеченных
символами элементарных автоматных структур Aν1 , Aν2 , . . . , Aνh , а выходят h ребер,
отмеченных символами Aw1 , Aw2 , . . . , Awh , то
h
Aνj =
j=0
h
Awj ,
j=0
где
Aν0 =
A(0)
Λ
при ci = c0 ,
при ci = c0 ,
Aω0
=
A(σ)
Λ
ϕ(ci ) = q(σ) ,
при ci ∈ C,
при ci ∈ C;
д) структурный граф автомата не содержит заведомо «неэффективных» ребер,
удаление которых не меняет индуцируемого автоматом спектра взаимосвязанных обобщенных отображений;
е) структурный граф автомата не содержит ни одной вершины ci ∈ C, «недостижимой» из вершины c0 (в графе отсутствует путь из c0 в ci ), и ни одной вершины
из которой «недостижима» ни одна конечная вершина графа.
ci ∈ C\C,
Канонической формой конечно-нестационарного обобщенного автомата (2) будем называть любой эквивалентный ему автомат (6), находящийся в канонической форме.
Таким образом, задача приведения любого заданного конечно-нестационарного обобщенного автомата A (2) к канонической форме заключается в исследовании и разработке таких методов преобразования его абстрактной структуры, которые приводят к
построению эквивалентного ему автомата, находящегося в канонической форме.
4. Метод решения задачи. Перейдем к рассмотрению совокупности операций эквивалентного преобразования абстрактной структуры произвольно заданного конечнонестационарного обобщенного автомата (2), которая позволяет решить сформулированную задачу и привести абстрактную структуру этого автомата к виду, соответствующему условиям, которым должна удовлетворять его каноническая форма.
4.1. Объединение параллельных ребер. Пусть в структурном графе автомата (2)
(1) (2)
(1)
есть два параллельных ребра gij , gij , соединяющих вершины ci , cj , и f (gij ) = Ai1 ,
(2)
f (gij ) = Ai2 . В таком случае каждому пути Ω0h в структурном графе автомата, ве и проходящему по
дущему из начальной вершины графа c0 в любую вершину ch ∈ C
(1)
ребру gij , будет обязательно соответствовать путь Ω0h из c0 в ch , отличающийся от
36
(1)
(2)
Ω0h только тем, что вместо ребра gij он проходит по ребру gij . Однако в таком слу(1)
(2)
чае, учитывая выражения (3), (4), можно объединить эти пути, заменив ребра gij , gij
одним ребром gij , введя дополнительную элементарную автоматную структуру An+1 и
положив f (gij ) = An+1 . При этом An+1 (1) будет иметь следующие характеристики:
Xn+1 = Xi1 ∪ Xi2 , An+1 = Ai1 ∪ Ai2 , An+1 = Ai1 ∪ Ai2 , Yn+1 = Yi1 ∪ Yi2 ,
(i1 ) (x, y) + R
(i2 ) (x, y), x ∈ Xn+1 , y ∈ Yn+1 ,
R(n+1) (x, y) = R
(i1 ) (x, y), R
(i2 ) (x, y) получены из матриц R(i1 ) (x, y), R(i2 ) (x, y) путем их
где матрицы R
дополнения нулевыми строками и столбцами, соответствующими состояниям из алфавитов An+1 и An+1 , отсутствующим в алфавитах Ai1 , Ai1 , и Ai2 , Ai2 , а также дополнения
множеств {R(i1 ) (x, y)}, {R(i2 ) (x, y)} нулевыми матрицами, соответствующими тем парам (x, y) ∈ Xn+1 × Yn+1 , которые отсутствуют в множествах пар Xi1 × Yi1 и Xi2 × Yi2 . В
h , индуцируемое конечной веррезультате данной операции обобщенное отображение Φ
шиной ch структурного графа автомата, и, соответственно, спектр обобщенных отобра не изменяются, то есть будет получен конечно-нестационарный обобщенный
жений Φ
автомат, эквивалентный исходному.
Используя данное правило, можно последовательно объединить любое конечное
множество параллельных ребер, отмеченных символами из A и соединяющих одну и ту
же пару вершин. В результате получим автомат (6), который эквивалентен исходному
и структурный граф которого удовлетворяет условию «а». При дальнейших преобразованиях структурного графа с помощью рассматриваемых ниже операций данную
процедуру повторять не приходится, так как эти операции не приводят к появлению в
графе новых ребер.
4.2. Операция изменения множества элементарных автоматных структур (множества финальных распределений весов состояний). В соответствии с определением
(2) конечно-нестационарного обобщенного автомата A вполне естественным является
требование к заданному для него множеству элементарных автоматных структур A
(множеству финальных распределений весов состояний Q), заключающееся в том, чтобы оно содержало те и только те элементарные автоматные структуры Aν (вектора
q(σ) ∈ Q), которые встречаются в отметке ребер (конечных вершин) структурного графа автомата, причем элементарные автоматные структуры, входящие в A (вектора
q(σ) ∈ Q), должны быть отличны друг от друга. Таким образом, если после выполнения какого-либо преобразования структурного графа в отметке его ребер (конечных
вершин) появится новая элементарная автоматная структура (новый финальный вектор весов состояний), не входящая в множество A (в множество Q), то она должна быть
включена в множество элементарных автоматных структур A (в множество финаль В то же время, если после этого
ных распределений весов состояний Q) автомата A.
преобразования какой-либо из символов Aν (векторов q(σ) ) больше не встречается в
отметке ребер (конечных вершин) структурного графа, то соответствующая элементарная автоматная структура (вектор q(σ) ) может быть удалена из множества A (из
множества Q). В общем случае данная операция выполняется неоднократно в сочетании
с другими операциями каждый раз, когда в ней возникает необходимость. В результате
абстрактная структура автомата A всегда будет удовлетворять условию «б».
4.3. Операция удаления несущественных состояний из алфавитов состояний. Для
более оптимального задания конечно-нестационарных обобщенных автоматов целесообразно удалить из алфавитов состояний элементарных автоматных структур и ал
фавитов A(0) , A(σ) , σ = 1, k, те состояния, которые заведомо не влияют на величину
37
(3). Для этого достаточно выполнить следующие действия: а) если в элементарной автоматной структуре Aν какому-либо состоянию ai ∈ Aν при всех x ∈ Xν , y ∈ Yν в
матрицах R(ν) (x, y) соответствуют нулевые строки, то состояние ai удаляется из алфавита Aν , а соответствующие ему нулевые строки в матрицах R(ν) (x, y) вычеркиваются;
б) если в элементарной автоматной структуре Aν какому-либо состоянию aj ∈ Aν при
всех x ∈ Xν , y ∈ Yν в матрицах R(ν) (x, y) соответствуют нулевые столбцы, то это
состояние aj удаляется из алфавита Aν , а соответствующие ему нулевые столбцы в
матрицах R(ν) (x, y) вычеркиваются; в) если в начальном распределении весов состояний r какому-либо состоянию aj ∈ A(0) соответствует нулевой элемент, то состояние aj
удаляется из алфавита A(0) , а соответствующий ему нулевой элемент в начальном распределении r вычеркивается; г) если в финальном распределении весов состояний q(σ)
какому-либо состоянию ai ∈ A(σ) соответствует нулевой элемент, то состояние ai уда(σ)
ляется из алфавита A , а соответствующий ему нулевой элемент в этом финальном
распределении q(σ) вычеркивается.
Данная операция является очевидной, поскольку при подсчете величин (3), (4) эти
строки, столбцы и элементы в случае необходимости восстанавливаются. В результате
выполнения этой операции, в том числе и в сочетании с другими операциями, абстрактная структура автомата A будет удовлетворять условию «в».
4.4. Согласование алфавитов состояний в вершинах структурного графа. Данная
операция выполняется последовательно для всех вершин структурного графа автомата A начиная с вершины c0 с последующей корректировкой множества элементарных
автоматных структур до тех пор, пока не будет выполнено условие «г».
Рассмотрим вершину ci структурного графа автомата. Пусть в эту вершину входят h
ребер, отмеченных символами Aν1 , Aν2 , . . . , Aνh , и выходят h ребер, отмеченных симво может быть приписано
лами Aω1 , Aω2 , . . . , Aωh . Кроме того этой вершине (если ci ∈ C)
(σ)
финальное распределение весов состояний q
∈ Q, ненулевым элементам которого
множество Aω
соответствуют состояния, образующие алфавит Aω0 (для вершин ci ∈ C
0
условимся считать пустым), и начальной вершине c0 – начальное распределение весов
состояний r, ненулевым элементам которого соответствуют состояния, образующие алфавит Aν0 (условимся считать, что для других вершин множество Aν0 пусто). Образуем
объединения алфавитов
h
h
Aνj = A(i),
j=0
Aωj = A (i),
(8)
j=0
и найдем пересечение
A(i)
!
A (i) = A (i).
(9)
Рассмотрим любое состояние ag ∈ A(i) A (i), ag ∈A (i). Если ag ∈ A(i), то ag ∈A (i),
и в таком случае ag ∈Aωj для всех j = 0, h . Следовательно для любого пути в структурном графе, проходящем через вершину ci (заканчивающегося в вершине ci ), в вы (ωj ) (x, y) элементарной автоматной
ражении (3) в любой матрице весов переходов R
(σ) )
структуры Aωj , отмечающей выходящее из ci ребро (в финальном распределении q
состоянию ag будет соответствовать нулевая строка (нулевой элемент). В этом случае
значения элементов столбца любой матрицы R(νj ) (x, y), соответствующего состоянию
ag в элементарной автоматной структуре Aνj , отмечающей входящее в ci ребро (элемента начального распределения r, соответствующего состоянию ag ), согласно выражению
38
(3) не влияют на значение веса отображения и могут быть обнулены и удалены вместе
с состоянием ag из Aνj .
Если ag ∈ A (i), то ag ∈A(i), и в таком случае ag ∈Aνj для всех j = 0, h. Следовательно для любого пути в структурном графе, проходящем через вершину ci (заканчи (νj ) (x, y)
вающегося в вершине ci ) в выражении (3) в любой матрице весов переходов R
элементарной автоматной структуры Aνj , отмечающей входящее в ci ребро (в начальном распределении r) состоянию ag будет соответствовать нулевой столбец (нулевой
элемент). В этом случае значения элементов строки любой матрицы R(ωj ) (x, y), соответствующей состоянию ag в элементарной автоматной структуре Aωj , отмечающей
выходящее из ci ребро (элемента финального распределения q(σ) , соответствующего
состоянию ag ), согласно выражению (3) не влияют на значения веса отображения и
могут быть обнулены и удалены вместе с состоянием ag из Aωj .
Таким образом элементарные автоматные структуры Aνj , j = 1, h, отмечающие
входящие в ci ребра, могут быть преобразованы путем удаления из их алфавитов состояний Aνj , j = 1, h, всех тех состояний, которые отсутствуют в A (i), с удалением
соответствующих столбцов из матриц весов переходов. Соответственно элементарные
автоматные структуры Aωj , j = 1, h , отмечающие выходящие из ci ребра, могут быть
преобразованы путем удаления из их алфавитов состояний Aωj , j = 1, h , всех тех
состояний, которые отсутствуют в A (i), с удалением соответствующих строк из матриц весов переходов. Кроме того из распределений r и q(σ) , отмечающих вершину ci ,
могут быть также удалены элементы, соответствующие состояниям, отсутствующим
в A (i).
Выполнение данных преобразований с последующей корректировкой множества A
элементарных автоматных структур (и множества Q финальных распределений весов
состояний) приводит автомат A к форме, удовлетворяющей условию «г».
4.5. Удаление заведомо неэффективных ребер. Условимся называть ребро структурного графа неэффективным, если любой проходящий через него путь для заданного начального распределения r и любой пары слов (v, w) ∈ (X × Y )∗ приводит к
нулевому значению величины (3). Некоторые из таких заведомо неэффективных ребер могут быть удалены с помощью следующего простого правила, основанного на
результатах выполнения предыдущей операции согласования алфавитов состояний в
вершинах структурного графа.
Рассмотрим вершину ci , для которой выполнена операция согласования алфавитов. Вполне очевидно, что если в результате этой операции в элементарной автоматной
структуре Aνj , отмечающей входящее в ci ребро, будут удалены из алфавита Aνj все
состояния, т.е. получим Aνj = Λ, то это ребро окажется заведомо неэффективным и
может быть удалено. При этом для вершины, из которой удаляемое ребро исходило,
должна быть повторно выполнена операция согласования алфавитов состояний. Аналогично, если в результате операции согласования алфавитов в элементарной автоматной
структуре Aωj , отмечающей исходящее из ci ребро, будут удалены из алфавита Aωj
все состояния, т.е. получим Aωj = Λ, то это ребро также окажется заведомо неэффективным и может быть удалено, при этом для вершины, в которую удаляемое ребро
входило, необходимо повторить операцию согласования алфавитов состояний.
В общем случае операция определения заведомо неэффективных ребер несколько
сложнее и состоит в следующем.
В соответствии с выражением (3) любое ребро, исходящее из начальной вершины
c0 и отмеченное символом Aν , будет заведомо неэффективным, если для всех xs ∈ Xν
39
и yl ∈ Yν будет выполняться условие
(ν) (xs , yl ) = O.
rR
(10)
Для внутренней (т.е. не начальной) вершины ci структурного графа, в которую
входят h ребер, отмеченных символами Aνi , i = 1, h, исходящее из нее ребро Aω будет
заведомо неэффективным, если для всех Aνi , i = 1, h, при всех xsi ∈ Xνi , yli ∈ Yνi
и всех xs ∈ Xω , yl ∈ Yω для произведений пар матриц весов переходов, входящих в
выражение (3), выполняется
(νi ) (xsi , yli )R
(ω) (xs , yl ) = O.
R
(11)
и не имеет исходящих ребер, эффективность вхоВ случае, если вершина ci ∈ C
(ν) (xs , yl ), xs ∈ Xν , yl ∈ Yν ,
дящего ребра Aν проверяется умножением всех матриц R
на отмечающий эту вершину финальный вектор весов состояний q(σ) . Если во всех
случаях выполняется условие
(ν) (xs , yl )
R
q(σ) ≡ O,
(12)
то входящее ребро Aν будет заведомо неэффективным.
Для вершины ci структурного графа, из которой выходят h ребер, отмеченных
символами Aωj , j = 1, h , входящее в нее ребро Aν будет заведомо неэффективным,
если для всех Aωj , j = 1, h , при всех xsj ∈ Xωj , ylj ∈ Yωj и всех xs ∈ Xν , yl ∈ Yν для
произведений пар матриц переходов, входящих в выражение (3), выполняется
(ν) (xs , yl )R
(ωj ) (xsj , ylj ) = O
R
(13)
то также выполняется (12).
и при этом, если ci ∈ C,
Таким образом проверка на заведомую неэффективность каждого входящего в вершину и исходящего из вершины графа ребра сводится к последовательной проверке
равенства нулю соответствующих произведений (10)–(13). При этом получение ненулевого произведения для любой пары сомножителей сразу прерывает процесс проверки
данного ребра на неэффективность и позволяет перейти к проверке следующего. Если
же для какого-либо входящего (исходящего) ребра соответствующее из условий (10)–
(13) выполняется, то это ребро заведомо неэффективно и может быть сразу удалено,
при этом для вершины, в которую удаляемое ребро входило (из которой исходило),
необходимо повторить операцию согласования алфавитов состояний.
Выполнение операций удаления заведомо неэффективных ребер для всех ребер графа позволяет получить структурный граф, удовлетворяющий условию «д».
4.6. Удаление недостижимых и неэффективных вершин. Всякая вершина графа cj ,
для которой множество любых путей в графе из c0 в cj пусто, является недостижимой
и может быть удалена из структурного графа автомата вместе со всеми входящими в
нее и исходящими из нее ребрами.
" производится последовательно, наОпределение множества достижимых вершин C
чиная с вершины c0 , которая считается достижимой, если r = O и, следовательно,
Aν0 = Λ. В этом случае исходное «нулевое» приближение множества достижимых
" (0) = {c0 }. Далее, следуя по ребрам, исходящим из c0 , определявершин имеет вид C
ется множество вершин C (1) , непосредственно достижимых из c0 . В результатебудет
" (0) .
" (1) = C (1) C
получено «первое» приближение множества достижимых вершин C
40
Дальнейшие приближения находят, используя следующую рекуррентную процедуру.
"(i−1) ,
" (i) = C (i) C
Если получено i-е приближение множества достижимых вершин C
(i)
(i−1)
"
"
, определяется множество
то для каждой вершины cj , такой, что cj ∈ C , cj ∈C
вершин, непосредственно достижимых из cj . Объединение всех вершин, достижимых
" (i−1) , образует множество C (i+1) , и (i + 1)-е приближение
"(i) \C
из вершин множества C
(i)
" . В случае, если
" (i+1) = C (i+1) C
множества достижимых вершин определяется как C
(i+1)
(i)
(i+1)
"
"
"
"
C
= C , получаем множество всех достижимых вершин C = C
. Все вершины,
" будут недостижимыми.
не входящие в C,
Всякая вершина графа ci , для которой множество любых путей в графе из ci в конечные вершины пусто, является неэффективной и может быть удалена из структурного
графа автомата вместе со всеми входящими в нее и исходящими из нее ребрами.
"
Определение множества C
вершин структурного графа, из которых достижима хотя бы одна конечная вершина, также производится последовательно, но в обратном
порядке, начиная с конечных вершин. В этом случае исходное «нулевое» приближение
" (0)
Отсюда, следуя в обратном направ= C.
искомого множества вершин имеет вид C
определяется множество
лении по всем ребрам, входящим в вершины множества C,
(1)
В ревершин C , из которых непосредственно достижимы вершины множества C.
"(1)
" (0)
(1) ∪ C
зультате будет получено «первое» приближение искомого множества C = C
.
Дальнейшие приближения находятся с помощью следующей реккурентной процедуры.
"(i)
"(i−1)
"
(i) ∪ C
Если получено i-е приближение C
= C
искомого множества вершин C,
" (i)
" (i−1)
то для каждой вершины ci , такой, что ci ∈ C
, ci ∈ C
, определяется множество
вершин, из которых непосредственно достижима вершина ci . Объединение удовлетво" (i) " (i−1)
ряющих этому условию множеств вершин для всех ci ∈ C
\C
образует множество
(i+1) , а (i + 1)-е приближение искомого множества будет определяться выражением
C
" (i+1)
" (i)
"(i+1)
" (i)
(i+1) ∪ C
C
=C
. В случае, если C
=C
, получим искомое множество вер" " (i+1)
шин C = C
, из которых достижима хотя бы одна конечная вершина структурного
"
будут неэффективными.
графа. Все вершины, не входящие в множество C,
Отметим, что ребра, связанные с недостижимыми и неэффективными вершинами
и удаляемые вместе с ними, представляют собой еще один вид неэффективных ребер.
4.7. Порядок выполнения операций. Полная процедура решения поставленной в п.3
задачи приведения любого заданного конечно-нестационарного обобщенного автомата
A к канонической форме заключается в последовательном выполнении над ним описанных выше операций, при этом все операции (кроме первой) итеративно повторяются до
тех пор, пока параметры абстрактной структуры автомата не перестанут изменяться.
В результате такого преобразования исходного автомата A будет построен эквивалентный ему автомат A , находящийся в оптимальной стандартной (канонической) форме,
то есть, являющийся по определению одной из канонических форм этого исходного
автомата.
Summary
Ponomareva A. Yu., Tchirkov M. K. Optimal forms of a generalized finitely-nonstationary automata models set-up.
The problem of reducing a finitely-nonstationary automaton generalized over a partial by ordered semi-ring, inducing a finite spectrum of interactive generalized operators to a special optimal
standard form is solved.
41
Литература
1. Пономарева А. Ю., Чирков М. К. Обобщенные автоматные модели с конечнонестационарной и регулярно-нестационарной структурой // Проблемы оптимизации дискретных систем. СПб., 2001. С. 28–38.
2. Пономарева А. Ю., Чирков М. К. О матричном методе редукции состояний обобщенного
автомата с периодически меняющейся структурой // Вестн. С.-Петерб. ун-та. Сер. 1. 1998.
Вып. 3 (№ 1). С. 67–70.
3. Пономарева А. Ю., Чирков М. К. Обобщенные конечно-автоматные модели с периодически меняющимися параметрами и проблемы их оптимизации // Дискретные модели. Анализ,
синтез и оптимизация. СПб., 1998. С. 3–26.
4. Пономарева А. Ю. О минимальных формах автоматных моделей с периодически меняющейся структурой // Вестник молодых ученых. Прикладная математика и механика. СПб.,
1999. № 1. С. 33–39.
5. Ponomareva A. Yu., Tchirkov M. K. Nonstationary Generalized Automata with Periodically Variable Parameters and Their Optimization // Advances in Stochastic Simulation Methods.
Birkhauser, Boston, 2000. P. 315–335.
6. Пономарева А. Ю., Чирков М. К. Оптимизация обобщенных автоматов с периодически
меняющейся структурой. СПб., 2000.
Статья поступила в редакцию 10 июня 2003 г.
42
Документ
Категория
Без категории
Просмотров
7
Размер файла
224 Кб
Теги
оптимальное, задание, обобщенные, автоматные, моделей, формы, конечно, нестационарные
1/--страниц
Пожаловаться на содержимое документа