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

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

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

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

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

Добавлен: 19.06.2024

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

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

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

ОПТИМАЛЬНЫЕ АЛГОРИТМЫ

311

 

Л1[Дх/ау = ш<г>] = Вер(Дл:== 1/да = ш(4')) —

 

- Вер(Дх = - 1/ш = аЛ*>) = Л - О -

= 2Л— 1,

 

(3.3.25)

а среднее смещение, осредненное по всем состояниям ав­

томата

(i=l,...

,2k),

определяется формулой

 

2k

 

 

 

2h

 

М[Ах}= £

ptM[Ax/w = wW]= ^Pi(2Fi-l).

(3.3.26)

 

i=i

 

 

 

i=i

 

Для

случая

k=\

с учетом

формул (3.3.24), (3.3.18) и

(3.3.16)

из формулы (3.3.26)

имеем

 

 

2

 

 

 

 

 

Л*[Д*] = ^V<(2F<-l) =

( 2 F , - l ) ( l - 2 u i )

=

 

г=1

 

 

 

 

 

 

= - ( l - 2 f , ) 2 ( s 1 - s 2 ) ( r 1 - r 2 ) .

(3.3.27)

Видно, что Л1[Дх] будет минимально, если

(1— 2F 1 ) 2 (ri —

— г2) будет равен

своему максимальному значению, т. е.

единице. Здесь возможны два случая:

 

1) d=w{^q;

 

 

 

 

(3.3.28)

в этом случае по формуле (3.3.4) находим:

^ = 4 - (

1 + - ) ;

1 - 2 ^

= -

— ;

(3.3.29)

2 \

q I

 

 

q

 

М[Ах)=

d2

 

 

 

 

r ( s i - s 2 ) ( r , - r 2 ) ;

 

(3.3.30)

 

q2

 

 

 

 

2) q^Wi=d;

 

 

 

(3.3.31)

в этом случае по формуле

(3.3.4) имеем:

 

Fi = l;

1 - 2 Л = - 1 ;

 

 

(3.3.32)

M[Ax]=-(Si~s2)(ri-ra).

 

 

 

(3.3.33)

ГЛАВА III

312

-d -q

0

q a

-q -d

0

й q

Рис. 3.3.1. Функция выхода автомата в зависимости от па­ раметра q.

На рис. 3.3.1 показаны вид функции (3.3.4) и расположе­ ние точек d и q для первого и второго случаев. Из фор­ мул (3.3.30) и (3.3.33) видно, что алгоритм поиска будет оптимальным, если

r, = l ; r2 = 0; q^wu

(3.3.34)

Это означает, что в случае линейной функции Q(X) оп­ тимальным алгоритмом поиска по среднему быстро­ действию будет алгоритм с детерминированной функ­ цией переходов (3.3.1), (3.3.2) и детерминированной функцией выходов (3.3.4).

Приведем формулы для определения дисперсии ус­ ловной случайной величины Ax/w и безусловной диспер­ сии величины Ах. Нетрудно показать, что имеет место

D[Ax/w = wW] = 4Fi(l-Fi);

 

(3.3.35)

D[Ax]= (2F,-1)2[1 -

(s,-s2 )

( г , - г 2 ) ] .

(3.3.36)

Из этих формул находим, что

 

 

1) при d = w^q

 

(Fi = ~

[ \ + ~ ) ,

\-2Fi=-~)

имеем:

 

 

 

 

0[Дх/да = ш ^ ] =

( l

- ~ ) ;

 

(3.3.37)

 

 

Я

 

 

d2

 

 

 

 

D[Ax]=—-2[ 1 -

(s, -

s2 ) (r, -

r2 ) ];

(3.3.38)

ОПТИМАЛЬНЫЕ АЛГОРИТМЫ

313

 

 

2) при q^w{ = d

(Ft=l;

1 - 2F<= - 1 )

имеем:

 

(3.3.39)

D[Ax/w = wW] = 0;

 

D[Ax]=l-(si-s2)

(ri-r2).

(3.3.40)

Из полученных формул следует, - что разброс поиска также будет минимален при тех же значениях парамет­ ров, т. е. при

r, = l ;

/-2 = 0;

q = w,

 

 

 

 

(3.3.41)

т. е. для случая

линейной

функции

Q(X) минимальный

разброс

результата

поиска

будет при использовании де­

терминированного алгоритма

поиска.

 

 

 

Теперь рассмотрим общий случай, когда k>\.

В этом

случае переходы цепи Маркова, описывающей

переходы

автомата из одного состояния в другое,

задаются

мат­

рицей (3.3.19).

 

 

 

 

 

 

 

 

Предельные

вероятности

этой

цепи

Маркова

нахо­

дятся как решение

следующей системы

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

уравнений:

 

 

 

 

 

 

 

 

Vtpi=

(\-Vi+l)Pi+l

( t = l , . . . , * - l ) ;

 

 

 

 

 

 

 

 

 

 

 

(3.3.42)

( 1 — Vu+i)Ph+i =

Vk+i+lPh+i+l

 

( i =

1).

 

Решая эту систему,

находим:

 

 

 

 

 

i-l

Pi

(i =

2,...,k);

ГЛАВА III

314

 

i-1

 

 

Я

 

 

 

П

(l-Vk+j)

 

 

(3.3.43)

Ph+i

3 = 1

г

h

j - 1

Pi;

 

П vk+j

U

(l-Vj)

 

 

3=1

3=2

 

 

 

П

Pft+i =

Я

3=2

(i = 2,... ,k)

"Pi ,

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

из условия

нормировки:

 

 

 

 

 

 

i-1

 

 

k

 

 

 

 

k

 

Я

 

 

Я

 

 

 

 

 

 

 

 

 

 

 

1 - U l

г -

 

3=1

 

- + -

ft

 

-X

 

 

 

 

 

 

i =2

П

(l-Vj)

П

 

(l~Vj)

 

 

 

 

 

 

 

 

 

3=2

 

j=2

 

 

 

 

 

 

г - 1

 

 

\

 

 

 

 

 

 

 

 

 

 

 

X

-+

 

 

Я yft

 

 

 

 

 

г=2

 

 

 

 

 

 

 

 

 

/ j

 

 

 

 

 

 

 

3 = 1

+3

 

 

 

 

 

 

 

 

 

 

(3.3.44)

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

формулой

(3.3.20). Среднее

смещение

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

формулой

(3.3.26).

 

 

 

На рис. 3.3.2 показано

изменение M[AQ] в зависимости

от Г\ для случаев,

когда

память

автомата

равна k=l,

2,

3, 4, 5 и <7<W( i i

(t'= I , ...,k).

Из рисунка

видно, что с

ростом значения k при линейной функции

качества

быстродействие

поиска

увеличивается.

Графики

на

рис. 3.3.2 подсчитаны на ЦВМ по формуле

(3.4.26) с уче-

ОПТИМАЛЬНЫЕ АЛГОРИТМЫ

315

том

формул

(3.3.43)

и

(3.3.44)

 

при

значении

дисперсии

помехи

 

а =

= 1.

 

 

 

 

 

 

2.

Двумерный

 

случай

(п=2).

Пусть

/г=1 . Тогда

автомат

имеет

четыре

со­

стояния W<*> и четыре вы­

ходных вектора AX(-?>. Ну­

мерация

состояний

и пе­

реходы

из

одного состоя­

ния в другое показаны

на

рис. 3.3.3, а. Нетрудно

по­

лучить

переходные

мат­

рицы

 

состоянии

авто­

мата

 

 

 

 

 

 

-МШ1

Рис. 3.3.2. Изменение М[Д<2] в за­

висимости от вероятности перехода автомата Гу и от памяти авто­ мата к.

/ - 1 2

Г\Г2

Г22

ГуГ2

Г\Г2

/ - 1 2

Г\Г2

Г22

 

 

 

(3.3.45)

 

Г\Г2

г,2

Г\Г2

ГуГ2

Г22

Г\Г2

Гх2

г 2 2

Г\Г2

П 2

Г\Г2

Г\Г2

 

Г\Г2

/ - 1 2

 

 

 

(3.3.46)

Г12

гхг2

Г22

Г\Г2

Г\Г2

ГУ2

Г\Г2

Г22

Функционирование автомата описывается цепью Мар­ кова со следующей матрицей переходных вероятностей:

 

 

1 - й,

b

 

b

v2

b

 

(3.3.47)

l — v3

b

V3

b

 

b 1 — f4 b l>4

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