Учебное пособие 800326

по дереву поиска.

Рассмотренное дерево поиска соответствует наиболее простому случаю отсутствия ошибок в каждом двоичном измерении. Если возникают ошибочные измерения, то в общем случае возможен возврат к ранее проверенным событиям. При этом дерево поиска усложняется, появляются новые варианты разбиения подмножеств и соответствующие им ветви, возможен возврат к ранее принятым решениям (появляются петли). Это приводит к удлинению ветвей дерева вплоть до бесконечности.

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

2.3. Вероятности посещения узлов дерева поиска

Вероятности попадания поисковой процедуры в узел дерева поиска зависят от состава приписываемых узлам подмножеств и распределения вероятностей состояний объекта.

В состав корневого узла Х входят все элементы множества Х, определяемые числом исчерпывающих возможных несовместных состояний объекта xi . Так как по условию какое

либо из состояний всегда реализуется, вероятность посещения входного узла в соответствии с теоремой сложения вероятностей несовместимых событий равна

Вероятность попадания в узел, соответствующий подмножеству X ( N ,q ) равна

19

Например, вероятность посещения первого узла (N,q) при

N=1 q=1 (рис. 2.3) равна

а для альтернативного подмножества соответственно

20

Глава 3. ОПРЕДЕЛЕНИЕ СКРЫТНОСТИ И ЕЕ МЕРА

3.1. Подходы к определению скрытности

При оценке скрытности объекта используются два подхода. В первом (условно назовем его вероятностным) скрыт-

ность определяется как вероятность успешного выявления

реасобытия в заданное время. Однако это прежде всего мера успеха разведки, а не усилий, направленных на выявление состояния объекта. Кроме того, вероятностная мера скрытности неудобна численно, например, значения вероятностей успеха 0,94 и 0,99 близки, однако для их достижения могут потребоваться различные временные затраты.

Второй подход предполагает оценивать скрытность объ-

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

Таким образом при раскрытии неопределенности состояния объекта необходимо произвести соответствующие временные и аппаратные затраты.

Очевидно, что при использовании для каждого состояния своего отдельного устройства обнаружения (параллельное одновременное измерение) результат будет получен наиболее быстро, но при максимальных аппаратных затратах.

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

Теоретический анализ показывает, что параллельное и последовательное обнаружение реасобытия имеют общие

21

свойства и аппаратные затраты можно связать с временными и наоборот. Для обеспечения единообразия при оценке скрытности различных объектов целесообразно в качестве

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

3.2. Длина пути от корневого до финального узла дерева поиска

Переход от одного узла к другому по дереву поиска (рис. 3.1.) сопровождается одним двоичным измерением, которое будем сокращенно обозначать через ДИЗ. Его мы будем использовать также в качестве единицы оценки скрытности состояния объекта.

число двоичных измерений, необходимых для выявления реасобытия при заданном алгоритме поиска. Оно равно средней

22

длине ветвей l дерева поиска от корня к финальным узлам,

Алгоритмическая скрытность характеризует средние затраты в диз’ах на выявление реасобытия при заданном алгоритме поиска. В определении (3.1) полагается, что ошибки отсутствуют и все измерения имеют единичную стоимость независимо от порядка их выполнения в процедуре поиска.

3.4. Влияние алгоритма поиска

В минувшую мировую войну в США всех призывников проверяли на отсутствие венерических заболеваний посредством реакции Вассермана. Сначала исследовалась кровь каждого призывника в отдельности. Затем было предложено объединить их в группы, смешивать кровь и проверять ее целиком. Группы с общей отрицательной реакцией от дальнейших исследований в этом направлении освобождались. Экономичность второго пути очевидна.

Объединение проверяемых состояний в группы кроме медицины и технической диагностики, рассматривается также применительно к разведке сигналов в частотном диапазоне. На рис. 3.2а приведены результаты вычисления значений R( ) при двух алгоритмах поиска .

В первом алгоритме ( 1 ) производится последователь-

ный перебор состояний от первого до последнего, пока не встретится реасобытие. Дерево поиска показано на рис. 3.3а.

Второй алгоритм поиска ( 2 ) предполагает разделение

всего множества состояний пополам, проверку наличия реасобытия в каждой из этих частей, затем разделение выбранной половины множества X на две равные части с проверкой наличия в них реасобытия и так далее. Поиск заканчивается,

23

когда в выделенном подмножестве оказывается одно событие. Дерево поиска показано на рис. 3.3б.

Расчеты выполнены при равномерном распределении вероятностей состояний объекта.

Рис. 3.2

Рис. 3.3

На рис. 3.2б показана зависимость отношения

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

возрастает в 200 раз при A 5000. Рассмотренный пример говорит о наличии значительных резервов в сокращении времени поиска за счет надлежащего выбора алгоритма.

24

3.5. Потенциальная скрытность

Назовем потенциальной скрытность S, численно равную минимально достижимому (минимум – миниморум по всем реализуемым алгоритмам поиска) среднему числу двоичных измерений, необходимому и достаточному для раскрытия всех возможных состояний объекта, определив ее равенством

Речь идет о согласованном с объектом алгоритме поиска, обеспечивающем искомый минимум зависимости R от K . В

ряде случаев может существовать несколько алгоритмов, эквивалентных в смысле (3.3).

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

Сравнение практически используемых алгоритмов поиска с потенциальным позволяет судить о степени их совершенства.

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

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

25

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

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

В рассмотренном примере системы радиосвязи и разведки участвуют в игре, в которой каждая сторона стремится уменьшить потери и максимизировать свой выигрыш. Эти вопросы решаются в рамках математической теории игр.

26

Глава 4. ИРФОРМАЦИОННЫЕ АСПЕКТЫ ПОИСКОВОЙ ПРОЦЕДУРЫ

4.1.Неопределенность возможных состояний объекта, их энтропия

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

Базовым понятием теории информации является энтропия. Она зависит от закона распределения вероятностей состояний Pi и определяется выражением

i1

иизмеряется в двоичных единицах – битах.

Энтропия является мерой неопределенности поступающих сообщений или состояний наблюдаемого объекта. Ее величина равна нулю, если одна из вероятностей Pi 1, а ос-

тальные равны нулю. Это означает, что объект всегда находится только в одном заранее известном состоянии xi и неоп-

ределенность его состояний отсутствует.

Энтропия максимальна при равновероятном распределе-

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

27

4.2. О количестве информации в сообщении

Результат определения состояния объекта xi можно рассматривать как сообщение. Количество информации, заключенное в сообщении xi , зависит от его неожиданности или, иначе говоря, от его вероятности Pi . Чем меньше вероятность

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

Количество информации в одном передаваемом сообще-

и измеряется, как и энтропия, в битах. Знак минус обусловлен тем, что логарифм вероятности Pi 1 отрицателен, тогда ве-

личина I i оказывается положительной.

Среднее количество информации I(X ) в расчете на одно передаваемое сообщение из множества Х определяется матожиданием I i ,

Как видно, выражения (4.1) и (4.4) совпадают, то есть количество информации, содержащееся в состояниях объекта, равно их исходной неопределенности I (X ) H(X ) . Если со-

стояние xi заранее известно (его вероятность равна единице), то I (X ) 0 . Максимальное количество информации поступа-

28

ет от объекта с равновероятным распределением состояний.

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

В процессе поиска после каждого очередного двоичного измерения от объекта поступает некоторое количество информации и снижается неопределенность его состояний.

Если исходная (априорная) энтропия равна H (X ) , то после измерения и принятия решения y о наличии реасобытия в

выбранном подмножестве апостериорная (послеопытная) условная энтропия равна

Например, если при A 8 исходное распределение вероятностей равномерно (рис. 4.1а) и первое безошибочное измерение выявляет наличие реасобытия в подмножестве

29

ностей принимает вид рис. 4.1б и определяется по формуле

В рассматриваемом случае исходная неопределенность H(X ) 3 бита, а после измерения условная энтропия

равна H ( X / X 1(1) ) 2 бита. Как видно, после первого измерения неопределен-

Рис.4.1 ность состояния объекта уменьшилась на 1 бит.

После n-го двоичного измерения реасобытие обнаруживается в одном из подмножеств X 1(n,q) или X 2(n,q) , вероятности этого соответственно равны

На рис. 4.2 показан фрагмент дерева поиска для рассмотренного двоичного измерения. При этом поступающая информация снижает условную неопределенность состояния объекта на величину H , определяемую выражением

Рис. 4.2

30

H [ p log2 p (1 p) log2 (1 p)]. (4.11)

Назовем эту величину локальным декрементом неопреде-

ленности данного двоичного измерения.

На рис. 4.3 приведена вычисленная по формуле (4.11) за-

наиболее информативно двоичное измерение, для которого условные вероятности нахождения реасобытия в

Рис. 4.3 каждом из подмножеств одинаковы и равны 0,5.

Это обстоятельство необходимо иметь в виду при планировании и оптимизации поисковых процедур по критерию максимума декремента неопределенности при каждом следующем двоичном измерении.

4.4. Связь между неопределенностью состояний (энтропией) и потенциальной скрытностью

Задачей поисковой процедуры является снятие неопределенности H (X ) относительно текущего состояния. После ка-

ждого двоичного измерения неопределенность уменьшается на величину H (4.11).

Допустим, что поиск организован таким образом, что величина H при каждом шаге максимальна и равна H =1. При этом исходная неопределенность снизится до нуля при минимальном числе диз S, равном

31

ся при безошибочных измерениях и симметричном (гл.2) множестве возможных состояний объекта. Можно доказать, что в общем случае минимально необходимое число диз может превышать значение (4.12), но не более, чем на единицу

В дальнейшем будем пользоваться в качестве нижней оценки потенциальной скрытности при H(X ) 1 нижней границей (4.13),

Вычисляемую по формуле (4.13) скрытность будем назы-

вать энтропийной.

4.5. Баланс неопределенностей

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

Рассмотрим пример с показанным на рис.4.4 деревом поиска. Первое измерение проверяет эле-

и может быть существенно больше единицы. Вероятность та-

и эта величина не более единицы, что полностью соответствует полученным ранее результатам.

При отсутствии ошибочных измерений поиск всегда проходит по последовательности ветвей дерева, оканчивающихся в финальном узле, соответствующем реасобытию xr . Тогда

сумма частных декрементов неопределенности H n (xr ) по

всем n -м измерениям, n 1,lr , lr - длина соответствующей ветви дерева поиска для заданного реасобытия, равна исходной энтропии H (X ) ,

n 1

Умножая обе части равенства (4.18) на P(xr ) и суммируя

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

33

A lr

r 1 n 1

Назовем статистическим декрементом неопределенности произведение

Величина (4.19) равна удельному вкладу результата n -го двоичного измерения при реасобытии xr в снижении неопре-

деленности до нулевого уровня в конце поиска. Тогда получим

A lr

r 1 n 1

Соотношения (4.17), (4.18) и (4.20) назовем балансом неопределенностей. Из них видно, что в процессе поиска неопределенность о состоянии объекта постепенно снижается, а поисковая система получает порции информации в ходе каждого двоичного измерения.

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

34

5. МИНИМИЗАЦИИ ПРОДОЛЖИТЕЛЬНОСТИ ДВОИЧНОЙ ПОИСКОВОЙ ПРОЦЕДУРЫ

5.1. Двоичная индексация узлов дерева поиска

Будем пользоваться следующими правилами обозначения (адресации) узлов на дереве поиска (рис. 5.1).

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

Рис. 5.1 ла 0, смещенный вправо – добавлением символа 1, и так

далее.

В такой постановке получим дерево, в котором число разрядов в индексе финального узла указывает на его расстояние в диз’ах относительно корня дерева или, иначе гово-

ря, длину ветви li , i 1, A, от корня до данного узла.

5.2. Минимальное среднее число двоичных измерений

При заданном алгоритме поиска и отсутствии ошибочных измерений скрытность определяется соотношением (3.1),

где Pi - вероятность состояния xi , а li - число измерений для

его выявления.

Представим закон распределения вероятностей состояний

что всегда можно обеспечить изменением нумерации состояний объекта

Длины всех ветвей дерева поиска ограничены и существует такая величина l0 , для которой

Дополним двоичные коды ветвей всеми возможными комбинациями символов 0 и 1 до длины l0 , то есть добавим к

коду каждой ветви ki l0 li элементов. Тогда к дереву поиска всего будет добавлено

дополнительных ветвей, а их общее число не может быть больше 2l0 . С учетом (5.4) получим важное неравенство

A

i 1

которое устанавливает связь между длинами ветвей дерева и является условием реализуемости алгоритма поиска. Подобное соотношение известно в теории информации [3] как нера-

36

венство Крафта.

Тогда задачу минимизации алгоритмической скрытности

(5.1), то есть определения потенциальной скрытности объек-

та при отсутствии ошибочных двоичных измерений, математически можно записать в виде

Это классическая задача минимизации функции (5.6) при ограничениях типа неравенств (5.7) и (5.8), являющихся регулярными (задача имеет решение), если обеспечивается выполнение условия

Для минимизации алгоритмической скрытности целесообразно использовать известный в теории выпуклого программирования метод неопределенных множителей Лагранжа [4]. Решение задачи приведено в [1], где показано, что значение S равно

где m - наибольшее целое число, удовлетворяющее неравенству

37

m

Pi

PA - наименьшая из вероятностей состояний объекта.

В результате длины ветвей дерева поиска определяются выражениями

Как видно, в рассматриваемом случае минимальное значение алгоритмической скрытности (потенциальная скрытность) равно энтропии состояний объекта и его энтропийной

38