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

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

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

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

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

Добавлен: 19.06.2024

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

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

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

ВВЕДЕНИЕ

 

 

19

 

 

 

 

Отсюда

 

следует,

что существует функция

 

д{и,х)

такая, что

 

 

 

 

 

/ //

\

П ,

если ы' = 6 (и,х) ;

/ n q i q \

р (и /и,

х)

-

| о — в противном случае.

^

1 6 >

Это означает, что состояние автомата вполне регу­ лярно зависит от его входа и предыдущего состояния. Стохастичность автомата образуется за счет функции

выхода.

 

 

 

 

 

 

 

 

 

Марковский

 

автомат [21, 25]. Вероятностный автомат

называется

 

марковским

(с

детерминированной

функ­

цией выходов), если он является

автоматом

типа

Мили

и условная

вероятность

р(у/и,х)

принимает

только два

значения:

 

0

или 1. Следовательно, существует такая

функция %(и,х),

что

 

 

 

 

 

/ /

v

-

J

1, если # = Л(ы,х);

 

 

.

P {У/и, х)

<у 0 _ в П р 0

Т И В Н 0

М случае,

 

(U.d. 14)

т. е. вход и состояние детерминированно определяют вы­

ход автомата; случайно лишь

состояние

автомата.

Д е т е р м и н и р о в а н н ы й

автомат

является част­

ным случаем вероятностного автомата и получается из определения (0.3.1), где условная вероятность р {и', у/и, х) принимает только два значения: 0 или 1.

ВИДЫ ЭКВИВАЛЕНТНОСТИ В ТЕОРИИ ВЕРОЯТНОСТНЫХ АВТОМАТОВ

Ниже будут рассмотрены вопросы эквива­ лентности различных поисковых алгоритмов. При этом эквивалентность алгоритмов поиска будет сформулиро­ вана как эквивалентность их автоматного представле­ ния. Поэтому приводим определение и основные свойства эквивалентности автоматов [21, 23, 26, 27].

Эквивалентность состояний вероятностного автомата.

Предположим, что вначале автомат находится в состоя­ нии щ и на его вход подается последовательность вход­ ных символов (0.3.7) длиной N. Тогда на выходе авто­ мата получаем последовательность выходных символов

2*

ВВЕДЕНИЕ

20

той же длины (0.3.8). Вероятность появления последова­ тельности (0.3.8), согласно определению (0.3.2), равна

N

 

 

 

 

 

2

П

p(yk,

Uk/Uk-i, xh).

 

 

 

 

 

 

uh^U

h=l

 

 

 

 

(0.3.15)

 

 

 

 

 

 

 

 

 

 

 

Если для Uoi^U,

UQ2^U

 

И для любого

положительного

N имеет место равенство

 

 

 

 

 

 

 

 

Р и т {У\У2

• • • W * l * 2 ...XN)=

Р и ю

{У\У2

• • • yN/XiX2

...XN)

 

 

 

 

 

 

 

 

 

 

 

(0.3.16)

для всех

 

 

 

 

 

 

 

 

 

 

 

 

ftel;

 

yh(=Y

 

 

 

 

 

 

 

(0.3.17)

 

 

 

( £ = 1 , 2 , . . . , АО,

 

 

 

 

 

 

 

то состояния ы01 и «02 называются эквивалентными. Фи­

зически это означает, что состояния

uoi и и02 неразли­

чимы как внутренние начальные условия, поскольку они

приводят к одному и тому же внешне наблюдаемому по­

ведению, или соотношению вход—выход.

 

 

 

 

 

Эквивалентность

начальных

распределений

 

вероят­

ностного

автомата. Для каждой

пары (х, у)

входного и

выходного

символов

данного

автомата

через

T(yjx)

обозначим матрицу, //-элементом

которой

является

 

in (у/х)

= р (у, щ/щ, х),

 

 

 

 

 

(0.3.18)

 

т. е. вероятность перехода из состояния

i

в

состояние

/

и появления на выходе сигнала

у при подаче на вход

сигнала

х.

Тогда

{Т(у/х)},

где x e l ,

y^Y,

является се­

мейством

mXtn

матриц

с неотрицательными

элемен­

тами, где m — количество внутренних состояний авто­

мата. Из условия (0.3.4) следует, что матрицы

Т(у,х)

должны быть такими, чтобы для каждого входного сиг­

нала х^Х

 

переходная

матрица состояний

 

 

 

 

Т(х) = 2т(у/х)

 

 

 

 

 

 

(0.3.19)

 

у

являлась стохастической. Переходная матрица для по­ следовательностей входных (0.3.7) и выходных (0.3.8) символов определяется равенством

ВВЕДЕНИЕ

 

 

 

2!

 

 

 

 

 

 

 

Т{у\У2.

• • У^ххх2..

.xN)

=

TiyJx^Tiyz/xz)...

T(yN/xN).

 

 

 

 

 

 

 

 

 

(0.3.20)

Если

P<°)= ( p i ( 0 ) , . . . , p m ( 0 )

)

— любое

начальное

рас­

пределение

внутренних

состояний

Ui,u2,...,um

авто­

мата, то число

 

 

 

 

 

 

 

Р Р ( 0 )

{У\У2

• • • У'n/XM

...XN)

 

=

 

 

 

 

 

=

eT'(yiy2...yN/xlx2...xN)PW

 

 

(0.3.21)

обозначает

вероятность

появления

последовательности

У1У2 • • .yN

 

на выходе, когда на вход подается последова­

тельность

 

xiX2...xN

при

начальном распределении Р ( 0 ) .

Здесь

е

является

m-мерным

вектором,

элементы

кото­

рого равны единице; Т — транспонированная матрица Т. Два начальных распределения P i ( 0 ) и Р2( 0 ) называются ^-эквивалентными, если для любых последовательнос­

тей (0.3.7) и (0.3.8) длины N имеем

Рр,(») (У1Уг---Уя1х\Х2...хя)

=

 

 

 

= / % „ ) {У1У2 • • • Ук/xiXz

...xN).

(0.3.22)

Два

начальных распределения

Pi<°> и Рг( 0 ) называ­

ются

эквивалентными,

если

они

jV-эквивалентны для

всех N.

 

 

 

Когда распределения Р^0 * и Р2( 0 ) являются вырожден­ ными, т. е. элементы векторов Pi<0) и Р2< 0 ) равны нулю или единице, тогда эквивалентность начальных распре­ делений совпадает с эквивалентностью состояний.

Достаточным условием {23] эквивалентности началь­ ных распределений P i ( 0 ) и Рг( 0 ) является их (пг— ^ - э к в и ­ валентность, где m — количество внутренних состояний автомата.

Эквивалентность

двух вероятностных

автоматов по

за­

данным

начальным

распределениям.

Пусть даны два

ве­

роятностных

автомата

Ах

и А2

с

матрицами

переходов

Т\(у/х)

и

Т2(у/х).

Пусть

автомат

А\

имеет m t

внутрен­

них

состояний,

а автомат

А2

т2

 

внутренних состояний.

Предположим,

что

P i ( 0 )

есть

начальное

распределение

состояний

для

автомата

Л ь

а

Рг( 0 ) — то

же

для авто­

мата

А2.

 

Обозначим

вероятность

появления на выходе

автомата

Л;

последовательности

У\у2...ук

при

условии,

ВВЕДЕНИЕ

 

 

 

22

 

 

 

 

 

 

 

 

что

на

вход

была подана последовательность

ххх2...

 

xN

и начальное распределение состояний автомата

было

равно

Pj ( 0 ) , величиной р р ( 0 ) т >

(уху2...

yN/xiX2...

xN);

 

PP.mTi

 

(У1У2

• • • Ук1ххх2 ...XN)

=

 

 

 

 

 

 

 

 

= ej'i

(У1у2...

yN\x,x2

...xN) P<«»,

 

(0.3.23)

где

e*

— mj-мерный вектор, элементы которого равны

 

T'i

 

единице;

 

 

 

 

 

 

 

 

 

— транспонированная матрица 7,-

(/=1,2) .

 

 

Если для всех входных последовательностей

Х \ Х 2

. . . xN

и

выходных

последовательностей у\у2...

г/я,

имеющих

длину

 

N,

 

 

 

 

 

 

 

 

РP i m

T l

(У1У2

• • • yN/xiX2

...xN)

=

 

 

 

 

 

 

 

 

= P P

J 2 (У1У2

• • • Уп1х{х2 ...xN),

 

 

(0.3.24)

то начальное

распределение

Pi < 0 ) для

автомата

А\

назы­

вается

JV-эквивалентным

начальному

распределению

Р 2 (

0 ) для автомата А2.

Или, иначе, система

( Г ь

P i ( 0 ) ) ,

т.е.

система «переходная матрица Т\ и начальное распреде­

ление

Р^ 0 '»,

называется Л^-эквивалентной системе

(Г2 , Р 2

( 0 ) ) ,

т. е.

системе «переходная матрица Т2 и на­

чальное распределение Р2<°Ь>.

 

 

 

Системы

(T'i, Pi ( 0 ) )

и

{Т2, Р 2

( 0 ) )

называются

эквива­

лентными,

если

они iV-эквивалентны

для всех JV.

 

Достаточным

условием

123]

эквивалентности

систем

(TuPi{0))

 

и

(Т2,

Р2<°>)

является

их

( m , + m 2 - 1 ) - э к в и в а ­

лентность, где Ш\ — количество внутренних состояний

автомата Л ь а т2 — автомата

А2.

состояниям.

Автоматы

А\

Эквивалентность

автоматов

по

и Л 2 называются эквивалентными по состояниям {22],

если для каждого

и^{иА>}

существует такое

и^{11Аг),

что

 

 

 

 

 

 

РщЛ' {У\У2 ...Ук---

/ХХХ2 . . . x N . . . )

=

 

 

= ри^{У\У2..

. y N .

• .\Х\Х2.

. .xN...),

(0.3.25)

и

наоборот, для

каждого

Uk^.{UA*}

существует такое

 

что

 

 

 

 

 

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