ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 202
Скачиваний: 1
ПОИСК БЕЗ САМООБУЧЕНИЯ
|
|
99 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таким образом, автомат рабочих шагов A( P> пред |
|
||||||||||||||||||
ставляет |
собой |
а в т о м а т |
|
с о г р а н и ч е н и я м и |
|
н а |
|
||||||||||||
в х о д е . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
На рис. 1.8.2 показаны графы переходов из |
одного со |
|
|||||||||||||||||
стояния в другое для автомата пробных шагов Л ( П ) и для |
|
||||||||||||||||||
автомата |
|
рабочих |
|
шагов |
Л<Р> |
при |
|
с = 0; |
с = 1 ; |
Cj |
|
= |
|
||||||
= (ci<J>,..., cn{i)) |
• Из |
|
этого |
рисунка |
получаем следую |
|
|||||||||||||
щие матрицы переходных |
вероятностей: |
|
|
|
|
|
|
||||||||||||
1) для |
|
автомата |
|
пробных |
|
шагов |
(переходные |
мат |
|
||||||||||
рицы штрафа и нештрафа |
совпадают) |
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
0 |
1 0 |
0 ••• 0 |
0 |
|
|
|
|
|
|
|
|
|
|||
л , |
л |
, |
, |
О 0 |
1 |
0 ••• 0 |
0 |
I . |
|
|
|
/ f |
. |
|
. ч |
|
|||
Л,(п)=Л0 |
(п ) = : |
|
_ |
0 |
0 |
0 |
л |
|
\ \ п + 1 |
|
(1.8.4) |
|
' |
||||||
|
|
|
• |
i 0 |
••• 0 |
1 |
' ' |
|
|
v |
|
|
|
||||||
|
|
|
|
1 |
о |
о |
о ••• о |
о |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
п+1 |
|
|
|
|
|
|
|
|
|
|
|
|
2) для автомата |
рабочих шагов |
|
|
|
|
|
|
|
|
||||||||||
|
10 |
0 ••• 0 |
0 ••• 0 |
1 |
|
|
|
|
|
|
|
|
|
|
|||||
|
|
0 |
0 ••• 0 |
0 - |
0 |
1 |
|
|
|
|
|
(1.8.5) |
|
||||||
Л ; ( р > = |
|
|
|
|
|
|
|
|
|
тп+1 |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
m+l —j |
|
|
|
|
|
|
|
|
|
|
|
||
а) |
о- |
|
|
|
|
|
|
|
|
|
|
|
|
с-0 |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
П+1 |
с-1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(р) |
|
|
|
|
Рис. |
1.8.2. Графы |
переходов |
автомата |
пробных |
тагов |
|
|
|
|
||||||||||
(а) |
и автомата рабочих |
шагов |
(б). |
|
|
|
|
|
|
|
|
||||||||
7*
ГЛАВА I
100
Здесь индекс у обозначает состояние рабочего авто мата, на которое он переходит из фиктивного состояния. При этом у совпадает с номером вектора штрафа Cj =
= ( с 1 0 ) , . . . , с „ « ) ) .
Объединяя автомат пробных и автомат рабочих ша
гов, получаем |
автомат, количество |
состояний которого |
|||
равно п + т и переходные матрицы |
имеют вид |
||||
0 • • 0 0 • • 1 0 0 • • 0 |
|
||||
0 • • 0 0 • • 1 |
0 |
0 • • 0 |
|
||
0 • • 0 |
0 • • 1 |
0 |
0 • • 0 |
(1.8.6) |
|
0 • • 0 0 • • 0 1 0 • • 0 |
|||||
|
|||||
0 • • 0 |
0 • • 0 |
0 |
0 • • 1 |
|
|
0 • • 1 |
0 • • 0 0 0 • • 0 |
|
|||
j |
п |
т |
|
Среда задается |
вероятностями появления векторов |
C j = ( c i ^ , . . . , c„(i>), |
т. е. вероятностями qj выбора у'-го |
рабочего шага после окончания пробных шагов. Вектор
вероятностей |
Q = (q\,..., |
q2n), |
согласно |
нумерации век |
торов ДХ<э"> (1.8.1) и переходных матриц |
(1.8.3), опреде |
|||
ляется формулой |
|
|
|
|
п |
|
|
|
|
Q = Q0)JJ |
[SNA, (N) + |
(1 - sN) |
Л 0 (N) ]. |
(1.8.7) |
Л'=1 |
|
|
|
|
Здесь Q< 0 ) — 2п -мерный начальный вектор состояний автомата «памяти» (1.8.3); Q ( 0 , = (1, 0,...
. . . . 0);
s,v — вероятность штрафа iV-ro пробного шага;
sN=Bep |
( A Q V ^ 0 ) = у [ 1 + Ф ( ^ ) ] ' |
( 1 ' 8 - 8 ) |
где <xN (N=\,...,n) — направляющие косинусы гради ента функции Q(X).
ПОИСК БЕЗ САМООБУЧЕНИЯ
10!
Функционирование объединенного автомата в случай ной среде (1.8.8) описывается цепью Маркова со следу ющей циклической переходной матрицей:
0 |
••• 0 |
1 0 |
0 |
••• 0 ; |
|
О |
••• 0 |
1 0 |
0 ••• 0 |
S т |
|
|
|
|
|
|
|
0 |
••• 0 |
1 0 |
0 |
••• 0 |
|
А о = Л , = || 0 |
••• 0 |
0 1 |
0 ••• 0 j |
(1.8.9) |
|
О ••• 0 |
0 0 0 |
••• 1 |
|
||
<7i ••• qm |
0 0 |
0 ••• О |
|
||
Предельные вероятности этой цепи находятся как ре шение системы алгебраических уравнений
Pi = qiPm+n ( t = l , • • • ,m);
Pm+l |
|
|
|
(1.8.10) |
|
i=l |
|
|
|
|
|
Pm+2~Pm+l', • • • ' Pm+n |
= |
Pm+n-1- |
|||
Решением этой системы |
является |
||||
Яг |
(t = l |
, . |
. . , |
m); |
|
1 + tt |
|||||
|
|
|
Xl.8.11) |
||
|
|
|
|
||
l + n |
(i = m+\,..., |
m + n). |
|||
|
|
|
|
||
Тогда |
средний вектор рабочего шага в пространстве {X} |
||||
равен |
|
|
|
|
|
М[АХ] = |
^ р |
г А Х |
^ = |
{ [ ( < 7 H W 2 - ? I ) + . |
|
|
|
i = |
l |
|
|
|
+ |
( 0 2 + 7 П / 2 |
- 9 2 ) + |
••• + { q m - q m l 2 ) \ 1+n ' |
|
ГЛАВА I
102
|
|
[{o\+mh—qi)+ |
••• + ( |
M W |
2 - W 2 ) - |
••• |
||||
|
|
|
|
|
|
|
|
|
|
I |
|
|
|
{QrnU+l+mh — QmU+l) |
~~ |
(am |
— (]mh)h ' l + n ' |
||||
|
|
• • • . [ (4\+m/2 |
- <7l) - |
(?2+m/2 ~ |
<7г) + |
(Яз+т/2 |
~ Яз) ~ |
|||
|
|
- |
(<74+m/2-94) + ••• - |
(qn~qml2)\~^ |
} |
• |
||||
|
|
|
|
|
|
|
|
|
|
(1.8.12) |
Среднее |
изменение |
показателя |
качества |
равно |
||||||
A f [ A Q ] = - - j 4 — [(<7i+m/2-<7i) |
(0С1 + 0С2+ |
••• + « „ ) + |
||||||||
|
|
|
1 + n |
|
|
|
|
|
|
|
|
|
+ |
(^2+m/2 — Яг) ( a i + a 3 |
+ |
••• +an-i |
— a n ) + |
||||
|
|
+ |
( 9 3 W 2 — <7з) («i + |
|
+an-2 — a n - i + a n ) + |
|||||
|
|
+ |
(<74+m/2 — 94) (0Ci+ |
••• +<Xn-2 —OCn-1 — a n ) + - " |
||||||
|
|
••• + (qm-i — qmi2-i) ( a i |
|
a n - i + a n ) + |
||||||
|
|
+ |
[q-m-qmh) |
(ai |
|
a „ _ i - a„)]. |
|
(1.8.13) |
||
Для |
двумерного |
случая |
(n = 2) |
из формул |
(1.8.11) и |
|||||
(1.8.7) |
имеем: |
|
|
|
|
|
|
|
||
Pi= |
J- |
( l - s i ) ( 1 - « 2 ) ; Рг= ^ - ( 1 - S i ) s 2 |
; |
|
||||||
Рз= |
J-S1S2; р 4 = — s i ( l - s 2 ) ; |
|
|
|
|
|||||
Р 5 = у ; |
Р е = у ; |
|
|
|
|
|
|
(1.8.14) |
||
Р с Р = |
y [ s ' i ( l - s ( ) |
(l - Sa)+s'a(l - Si)s2 + |
|
|||||||
|
|
+ |
s/ 3 Si52 + s V i ( l - s 2 ) ] ; |
|
|
|
(1.8.15) |
|||