ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 213
Скачиваний: 1
ПОИСК С САМООБУЧЕНИЕМ
153 |
|
|
На рис. 2.1.5 показана нумерация |
внутренних |
состоя |
ний автомата для случая, когда т>2п, |
т. е. когда |
коли |
чество внутренних состояний WW автомата больше, чем |
||
количество его выходов ДХО'). На рис. 2.1.6 показаны най |
||
денные по формулам (2.1.50) и (2.1.51) переходы |
такого |
|
автомата из одного состояния в другое в зависимости от его выходов ДХ( ^ при нештрафе (AQ'<0) . Под каждым
графом в скобках |
указан выход, которому соответствует |
||||||
этот граф переходов в случае штрафования этого выхода. |
|||||||
По изображенному на рис. 2.1.6 графу получаем следую |
|||||||
щие матрицы |
переходных вероятностей автомата: |
||||||
|
при нештрафе |
|
|
|
|
|
|
|
P(i) |
0 |
0 •• • 0 |
0 |
|
||
|
P(i) |
0 |
0 • • |
0 |
0 |
2fe + l |
|
|
А>(/) = |
0 |
P(j) |
о. • |
0 |
0 |
|
|
|
||||||
|
|
0 |
0 |
0 • •P(j) |
0 |
|
|
|
|
|
|
2ft + I |
|
|
|
|
|
|
|
|
|
|
(/=1,2); |
о |
о |
|
|
2k. |
|
|
|
|
|
о |
|
|
|
||
|
2k2, |
|
|
|
|
|
|
4k$3M |
4kik |
2ti 2k*1 |
3k*2 |
k+t ) |
\ |
|
|
|
i |
о |
о— |
|
|
|
|
|
|
2k |
AX<«> / |
• (Z) |
|
|
|
О |
|
|
|
|
|
|
О |
|
|
|
О |
О |
О |
о |
о |
|
|
<2Ы}г |
2к3+2* |
2кг+3к,1 |
ик+2 |
2к+1 |
|
|
Рис. |
2.1.5. Нумерация состояний W(*> и выходов ДХ<Я автомата при |
п = 2 |
и т>2п. |
ГЛАВА II
154
О P(j) |
о |
о |
о |
|
О О |
P(j) |
о |
о |
|
Ml) |
|
|
} 2h + l |
|
|
|
|
|
|
|
2ft + I |
(/ = 3,4); |
(2.1.61) |
|
|
|
|
||
^ Ч ! ч Ч Ч i Ч ^
а - АХ'" |
их-АХ'") |
АХ=АХ,!) |
(АХ~АХ'3>) |
С-J |
(С-1) |
с-О |
(с=1) |
|
11% |
|
|
С
2т
217,-Л
|
|
|
^171*2 |
АХАХ"' |
(АХ=АХ'г>) |
АХ-АХа> |
(АХ=ДХГ") |
с-О |
(с-1) |
с*0 |
(с-1) |
Рис. 2.1.6. Переходы автомата для т>2п |
(п=<2). |
|
|
ПОИСК С САМООБУЧЕНИЕМ
155
|
|
|
|
|
|
(2.1.62) |
|
В матрицах Ac{j) (с = 0, |
1; |
/ = 1,...,4) |
нулями обозна |
||||
чены |
матрицы |
порядка |
(2k |
+1) X (2k +1), |
элементы |
ко |
|
торых |
равны |
нулю; P(j) |
( / = 1 , 2, 3, 4) |
— |
матрицы |
по |
|
рядка |
(2k +1) X (2k +1) следующего вида: |
|
|
||||
1 0 0 ••• О О О
1 0 0 ••• О О О
О1 0 ••• О О О
О0 0 ••• 1 О О
О 0 0 ••• 0 1 О
О 1 О 0 ••• О О !
О 0 |
1 о ••• О |
О |
|
Р ( 2 ) = Р ( 4 ) |
0 0 |
••• 1 |
(2.1.64) |
О 0 |
О |
||
О 0 |
0 0 |
••• 0 1 |
|
О 0 |
0 0 |
••• 0 1 |
|
В матрице AQ(j) физический смысл блоков P(j) таков, что он характеризует переход за один шаг из и-го столбца состояний на и-й столбец графа, изображенного на рис. 2.1.6. Если блок P(j) равен нулю, это означает, что за один шаг невозможен переход из и-го столбца со стояния на v-и столбец состояния.
Элементы t'-й строки блока P(j) являются вероят ностями перехода из г-го состояния «-го столбца в со стояния, принадлежащие v-му столбцу.
Теперь построим матрицу А. Поскольку выполнены условия (2.1.62), то имеют место равенства (2.1.56) и матрицу А можно строить по формуле (2.1.57). Введем
диагональные матрицы (2.1.65) порядка |
(2k+\)X |
X(2k + l), элементы которых вычисляются по |
формуле |
(2.1.59). |
|
ГЛАВА II
156 |
|
|
|
|
|
Qu(j) |
|
|
|
|
|
ftu-ixaft+iH-i (/) |
|
О |
|
О— |
О |
О |
9(u-I)(2h+l)+2 0') |
0 |
0 |
||
|
|
О |
|
О ••• ^(„_1)(2fe+l)+2h+l•(/) |
|
|
|
|
|
|
(2.1.65) |
Затем, используя блоки |
Qu(j), |
матрицу |
Q(j) перепи |
||
сываем в виде |
|
|
|
|
|
Q,(y) |
О |
О - |
О |
|
|
О |
Q2(j) |
О - |
О |
|
(2.1.66) |
<3(/) = |
|
|
|
|
|
О |
О |
О-«32 ft+i(j) |
|
||
По формуле (2.1.57), учитывая вид матрицы A0(j) и блочное представление матрицы Q(j), находим матрицу
Рп |
|
|
0 |
0 |
- |
0 |
|
0 |
0 |
|
0 |
Р2з |
0 |
0 |
- |
0 |
|
0 |
0 |
0 |
РЪ2 0 |
^34 |
0 |
- |
О |
|
0 |
0 |
|
0 |
0 |
0 |
0 |
0 - |
|
|
|
^2k,2h+\ |
|
|
|
|
|
|
|
"2fc,2ft-l |
U |
||
О |
0 |
0 |
0 |
0 - |
|
0 |
P2h+l,2k |
P2k+l,2h+l |
|
(2.1.67.)
где блоки Puv (и, v= 1, . . . , 2k+1) равны
ПОИСК С САМООБУЧЕНИЕМ
157 |
|
|
|
Pii = |
Qi(l)P(l)+Ql(2)P(2); |
|
|
Pu,u-1 = |
Qu(l)P(\)+Qu(2)P(2) |
|
|
|
(u = |
2,...,2k+l); |
(2.1.68) |
Pu,u+1 — Qu |
|
|
|
|
(u=l,...,2k); |
|
|
*2fc+l,2ft+l = |
Q2h+1(3)P(3)+Q2h+l(4)P(4). |
|
|
Учитывая матрицы (2.1.63) и (2.1.64) имеем матрицы
(2.1.69) — (2.1.72). Элементы |
этих |
матриц |
q(u-\)(2h+\)+i{}) |
|||
(i=l,...,2k; |
/ = 1,...,4) определяются |
по формуле |
||||
(2.1.59). Следовательно, матрицы Pu,u-i |
имеют |
вид |
||||
(2.1.73) и (2.1.74). Матрицы |
Ри, и+1 И P2k+l, 2fc+l МОЖНО |
|||||
<5u<i)P(i) |
= |
|
|
|
|
|
+i)+i(l) |
о |
|
|
О |
о |
|
:+i)+ 2 (l) |
о |
|
|
о |
о |
|
О |
^(м—l)(2ft+l)+3 ( 1 ) |
|
о |
о |
||
о |
о |
|
|
|
|
|
|
|
|
|
|
(2.1.69) |
|
QU(3)P(3) |
= |
|
|
|
|
|
<7(u-i)(2fc+o+i (3) |
О |
о |
- |
О |
О |
|
<7(u-l)(2ft+l)+2(3) |
О |
о |
- |
О |
О |
|
О |
^(и_1)( й+1)+з(3) |
О |
- |
О |
О |
|
|
2 |
|
||||
О |
|
0 |
0 ••• <7(U_i)(2M-i)+2fe+i(3) |
0 || |
||
|
|
|
|
|
(2.1.70) |
|
ГЛАВА II
158
<3u(2)P(2) =
О |
fttt_J)(2fc+I)+1 |
(2) |
О |
|
О - |
|
О |
О |
О |
&u-ix2ft+iH*(2) |
|
О - |
|
О |
|
О |
О |
|
О |
О ••• |
?(u-I)(2ft+l)+2h(2) |
||
0 |
0 |
|
О |
0 |
••• С/(и-\)(2к+1)+2к+1 (2) |
||
|
|
|
|
|
|
|
(2.1.71) |
QU(4)P(4) = |
|
|
|
|
|
|
|
О 4f(U_1)(2ft+i)+i (4) |
О |
|
0 ••• |
О |
|||
О |
0 |
^(U _1 )( 2ft+ i) + 2 (4) |
|
О— |
|
О |
|
О |
О |
|
О |
0 ••• |
<7(u_i)(2M-i)+2ft(4) |
||
0 |
0 |
|
О |
0 ••• ^(„_i)(2fc+i)+2ft+i(4) |
|||
|
|
|
|
|
|
|
(2.1.72) |
Ри,и—\ |
— |
|
|
|
|
|
|
<7(u-l)(2k+l)+l (1) <7(u-l)(2fe+l)+I (2) |
О |
О |
|||||
<?C«-l)(2fe+l)+2(l) |
0 9( u _1 )(2ft+ i)+ 2 (2) |
О |
|||||
|
О |
9(u-l)(2ft+I)+3 (1) |
0 |
|
^(«—1)<2^+1)+3 (2) |
||
|
О |
|
О |
|
О |
|
О |
|
О |
|
О |
|
О |
|
О |
О ••• |
О |
|
о |
о |
|
0 |
- |
0 |
|
о |
о |
0 |
- |
0 |
|
о |
о |
О ••• <7(M-l)(2M-l)+2k(l) |
0 |
?(«-l)(2ft+l)+2ft(2) |
|||
О " - |
|
0 |
^(U_i)(2ft+i)+2ft+j (О 9(u-l)(2fc+l)+2fc+l (2) |
||
(2.1.73)