Файл: Растригин Л.А. Автоматная теория случайного поиска.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 19.06.2024

Просмотров: 199

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

ПОИСК БЕЗ САМООБУЧЕНИЯ

 

81

 

 

 

 

 

 

 

 

 

 

 

A(S)

=

 

 

 

 

 

 

 

 

 

 

 

 

О

а{

0 0 •••

О

О Ь,

О

О

0 •••

О

О

I

О

0

а 2 0 - - -

О

О

О

Ь2

О

О---

О

О

I

О

О

О О -

О

On—1

О

О

О

 

О- •

ьп-iO

 

О О О о -

О

О ап

О 0 0 - • 0

 

 

bn+i

о

О 0 •••

О

О

О

 

0

 

0 - •

0

0

 

О

Ь п + 2 О О - О

О О О ап+20

" • 0 0

 

О

О О О ••• Ь 2 п - \

О

О

О

0 0 " -

0 а 2 п .

 

а2п

О О О •••

0

Ь2п

О

О

О

0 •••

О О

 

где

 

 

 

 

 

 

 

 

 

 

 

(1.6.3)

 

 

 

 

 

 

 

 

 

 

(1.6.4)

(H=\—Si\

bt

= Si.

 

 

 

 

 

 

 

Учитывая

линейность

функции качества и

используя

выражение

(1.5.4), имеем

 

 

 

 

 

(1.6.5)

a n + i =

bi\

b n + i = ai

 

 

 

 

 

 

 

 

 

( t ' = l , . . . ,

п).

 

 

 

 

 

 

 

 

Поэтому матрица (1.6.3) принимает вид

 

 

 

 

 

A(S)

=

 

 

 

 

 

 

 

 

 

 

 

 

0

 

0 0 - • 0

0 Ьг 0 0 0 • • 0

0

 

 

0 0 а2

0 ••• 0

0 0

ь2

0 0 • •• 0

0

 

 

0 0 0 0 ••• 0 On- lO

0 0 0 - •

Ьп-\

0

 

 

0 0 0 0 -

0

0 ап

0 0 0 - • 0

 

 

 

ах

0

0

0 •••

0

0 0

ft.0

о.- •

0

0

 

 

0 «2 0 О - • 0

0 0

0 ь2

0 - • 0

0

 

 

0 0 0 0 • • я п _

0 0

0 0 0 - • 0 Ьп-1

 

 

Ьп 0 0 0 ••• 0

ап 0

0 0 0 " • 0

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(1.6.6)

6—2014

ГЛАВА I

82

 

 

В случае, когда афО (щфО;

Ьгф\),

эта цепь Маркова

эргодическая. По матрице (1.6.6) для нахождения пре­ дельных вероятностей получаем следующую систему ал­

гебраических

уравнений:

 

pi = aipn+i

+

bnp2n

 

p2 = alp1

+

 

d2pn+2

 

Рз = а2р2

+

 

а3рп+3

 

Pi^di-ipi-i+dipn+i

 

рп = CLn-lPn—l + CLnPln

(1.6.7)

 

 

 

 

Рп+2 = Ь2р2

+

Ь]Рп+1

 

Pn+i — bipi-\-

bi-ipn+i-

 

P2n — bnpn +

Ьп-{р2п-\

 

Введем обозначения

 

kx = bnp2n;

 

k2=anpn.

(1.6.8)

Тогда из первого и (п+1) - го уравнений этой системы находим

Pv

axk2+kx

g\2k2+gxxkx

.

 

l — dxbx

U\

'

 

 

 

Pn+l=

k2+bXki

f\2k2

+

f\\k\

 

\—axbx

 

 

 

 

 

 

 

 

 

где

 

 

 

 

 

gi2 = ai; gu = U

b = l ;

fn = bx;

ux = l-axbx.

Из i-го и (п-И)-го уравнений получаем

Pi

gi2k2 + gi\k\

 

 

fi2h +

fi\k\

 

S pn+i — -

 

(1.6.9)

(1.6.10)

(1.6.11)

ПОИСК БЕЗ САМООБУЧЕНИЯ

83

 

Здесь Vi = UiU2.. .щ; щ — Х—аФг,

(1.6.12)

g«; gn', fi2', fn определяются по рекуррентным формулам

gi2—^i-]gi-l,2

+ агЬ <—l/i—1,2;

 

 

= Я г - l g i - l . l +

,

(1.6.13)

gil

dibi-lfi-UU

 

fi2

= biai-\gi-\t2

+

bi-lfi-\,2,

^ g

/ tl = M f - l f f i - M + 6 i - l / i - U

 

 

 

 

( i = 2 , 3 , . . . , n ) .

 

Сравнивая формулы (1.6.10), (1.6.13) и (1.6.14), нетрудно заметить, что выражение для f i 2 получается из формулы для g n , а для fu — из формулы для gi2 при замене а* на

bi

и

bi

— на Ci (i= 1,2,..., п ) . При

i — n из

формул

(1.6.11)

получаем

 

 

 

 

 

 

 

Рга =

gn2^2 +

gnl&l

 

fn2&2 +

fnl&l

•

 

„ « . г ,

 

 

 

'•

Р2п=

 

(1.6.15)

Из

равенств

(1.6.8)

и

(1.6.15) находим

соотношение kx

и кг-

 

 

 

 

 

 

 

 

 

 

 

k2=Gku

k{ = Fk2>

 

 

 

 

 

(1.6.16)

где

 

 

 

 

 

 

 

 

 

 

 

 

п

 

 

 

Qngnl

с

 

bnfП2

 

 

..

_

0 =

 

 

 

;

/*=

т - т - ;

 

 

 

( l . b . l / )

F=

 

~.

 

 

 

 

 

 

 

(1.6.18)

Отсюда видно, что функция F симметрична G относи­ тельно <Xi и bi, т. е. F получается из G, если щ заменить

2га

 

на bi. Из условия нормирования 2 pi—l

находим

H2k2 + Hxk{=\,

(1.6.19)

где

 

н

У§г2±Ы

н

y g U + h

 

'2

 

 

( 1 6 2 0 )

<-1

<-1

6*

ГЛАВА I

 

84-

 

 

Из формул (1.6.16)

и (1.6.19)

получаем

 

1

F

(1.6.21)

 

H2G + Hl

H2 + HXF '

 

 

k2 =

1

G

(1.6.22)

H2 + HXF

H2G+HX

Следовательно, формулы для определения предельных вероятностей имеют вид

P i

Vi\H2

+ HxF +

 

H2G + HXI

 

ы

„

- - 1 /

^

•

Ux

\ _

ЫО+Пх

Pn+i~Vi\H7+H7+

 

 

h2g+hx

i

vi

h

йь

 

 

 

 

(1.6.23)

Поскольку H2 и Hi

симметричны по отношению к а ; и bi,

то

pi и pi+n

также

симметричны, т. е. Рг+п

определяется

из

формул

для Pi

подстановкой а,- и bi на

место bi и а*

соответственно.

Среднее приращение функции качества на одном шаге равно

71

M[AQ]

= 2 0 > 1 - Р » - И ) « « = 2^ ( h2+hxf

 

 

 

 

 

 

 

 

 

 

 

 

 

 

+

 

 

 

, gii-fn

 

\

(1.6.24)

 

 

 

H2G

+ i

 

 

 

 

 

 

Далее

рассмотрим д в у м е р н ы й с л у ч а й (п = 2). Для

этого случая матрица (1.6.3) принимает вид

 

 

 

 

О ах

bi

О

 

A(S)

=

О 0

а2

Ь2

(1.6.25)

ах

0

0

bi

 

 

 

 

 

 

 

Ъ2

а2

О О

 

Исходя из этой матрицы имеем следующую систему ал-

ПОИСК БЕЗ САМООБУЧЕНИЯ

85

гебраических уравнений для определения предельных ве­ роятностей:

p[ = a[p3

+ b2pi;

 

P2=alPl

+ a2p<;

{ { 6 Щ

p3 = b[pi + a2p2\

pi = b2p2 + bxp3.

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

(1.6.5), на­

ходим:

 

 

 

 

 

 

 

 

 

 

 

 

 

Ь2 + аха22

 

 

 

ах + а2Ьх2

 

 

P i =

2 + b2-axbx

+ a2

' Р 2 = 2 + b2-axbx

+ a22'

 

_

 

a2 + bxb22

 

_ _

bx + ax2b2

 

Р з =

2 + b2-a{bx

+ a22

' P i ~ 2 + b2-axbx

+ a22

'

 

 

 

 

 

 

 

 

 

 

 

(1.6.27)

Подставляя

вместо

щ и

Ь\

величины

Si из формул

(1.6.4),

получаем:

 

 

 

 

 

 

 

Pi=

 

-3 S2 + S3S42

 

;

р 2 =

 

S3+S4S1 2

2+

^

SjSj+^+SjSj2

 

 

2+

SjSj+f+SjS

 

 

S4 +

S1S22

 

 

 

 

sx +

s2s32

 

Р з =

 

-ъ

 

 

 

;

р 4 =

 

 

 

 

2 +

J£

SjSj+i'

+

StSi*

 

2 + ^ S j

S J + 1 2 + S4S12

 

 

3=1

 

 

 

 

 

j - l

 

(1.6.28)

 

 

 

 

 

 

 

 

 

 

 

Среднее приращение функции качества равно

M[AQ]=

 

 

 

 

 

 

 

 

 

 

 

 

( S 2

- S 4

+ S 3 S42 - SiS 2 2 )ai+

(S3 - S i + 5 4 S i 2 - S 2 S3 2 ) « 2

 

_

 

 

 

 

 

3

 

 

 

 

 

 

 

 

 

 

2 + ^ , s j s i + 1

2 + s 4 s 1 2

 

 

 

 

 

 

 

 

 

 

 

 

(1.6.29)

Смотрите также файлы