Главная > Распознавание образов > Лекции по теории образов: Регулярные структуры
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

5.16. Случайная динамика для конфигураций

До сих пор мы изучали статическую случайность в пространстве конфигураций и индуцированные меры на алгебрах изображений. Следующий шаг исследований заключается в том, чтобы позволить мерам на зависеть от времени 1.

Конфигурация может быть описана своим составом и соединителем с. Динамика может, например, заключаться в том, что при фиксированном составе соединения раскрываются и замыкаются на множестве

всех регулярных конфигураций, построение которых из образующих дозволено правилами

С другой стороны, мы будем иногда встречаться с конфигурациями, у которых соединитель о фиксирован по отношению к заданным остовам образующих но где выбор образующих варьируется со временем. Конечно, возможны и комбинации этих случаев, когда и состав, и соединитель могут меняться со временем.

Во всех случаях, изученных до сих пор, с непрерывным или дискретным временем, мы получали марковский процесс на пространстве состояний Более того, процесс обычно был типа «рождение-смерть». Это относилось к образующим, так что на были заданы две интенсивности

Здесь обозначает вероятность, что данная образующая состав будет изъята из конфигурации с на временном интервале длины при условии, что М. позволяет такое изьятие. Аналогично, обозначает вероятность того, что к конфигурации

с добавится новая образующая на временном интервале но мы также должны оговорить, может ли присоединяться к старым образующим в с и как это может быть сделано. Например, возможно ограничение, согласно которому ни одна пара новых связей не может быть замкнута. Или для присоединения к с нужно пользоваться каким-то определенным соединителем. В каждом конкретном случае мы это будем явно оговаривать.

Поясним сказанное на нескольких примерах. Пусть множество. образующих конечное, тип соединения «линейный» и отношение связей «равенство». Положим при произвольном Рассмотрим регулярную конфигурацию где обозначает обычный линейный соединитель слева направо. Выберем некоторую образующую с вероятностью и присоединим ее справа, в результате чего получится конфигурация о но только в том случае, если такая конфигурация регулярна. Другими словами, мы выбираем случайным образом но при условии, что

В частном случае может содержать специальный элемент, скажем, который означает завершение процесса. Например, в синтаксически управляемых автоматных языках это означает конец вывода предложения — см. разд. 2.10 первого тома.

При тех же условиях, но, когда «древовидный», требуется указание о том, к которой выходной связи (в старой конфигурации) входная связь новой образующей должна быть присоединена. Это можно сделать путем случайного выбора с вероятностями, зависящими от опять, конечно, при условии, что выполняются правила

Аналогично тому, как мы пользовались интенейвностями «рождения» и «смерти» для введения новых и удаления старых образующих, введем интенсивности «рождения» и «смерти» для пар связей. Они будут функциями показателей связей

Соответствующие вероятности будут опять обусловлены регулярностью

Например, (5.16.4) может порождать на

процесс «рождения» и «смерти» Все значения принадлежат заданному пространству состояний и имеют один и тот же состав. Однако их топология динамически варьируется случайным образом. Она управляется а также правилами регулярности

Отложим анализ случайной динамики до гл. 7, где будет Детально изучен типичный для этой проблемы частный случай.

<< Предыдущий параграф Следующий параграф >>
Оглавление