Материал: Теория скрытности. Часть 1, Основы теории скрытности. Каневский З.М., Литвиненко В.П

Таблица 5.5

Рис. 5.6

Для дерева поиска на рис.5.6 и вероятностей из табл.5.5 значение потенциальной скрытности равно

X (1,1)

весьма близко к 0 . Если бы алгоритм поиска остался последовательным, то алгоритмическая скрытность была бы равна 3,402 диз, что заметно выше потенциальной.

Как видно, при выравнивании распределения вероятностей состояний объекта в оптимальном дереве поиска появляются дихотомические фрагменты (рис. 5.6), оно трансформируется от последовательного (рис. 5.4б) до дихотомическо-

го (рис. 5.3б).

49

5.4.2. Влияние ограничения ветвей на продолжительность поиска

При проектировании оптимальной поисковой процедуры могут налагаться ограничения на ее максимальную продол-

то величина l0 не влияет на алгоритм поиска. Таким образом,

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

во поиска представлено на рис. 5.4б (последовательный алгоритм). Максимальная длина ветви равна 7 диз, а минимально допустимое значение l0 равно 3 диз.

На рис. 5.7а показано оптимальное дерево поиска при l0 6 , а на рис. 5.7б – при l0 5 . При l0 4 дерево принимает вид, показанный на рис. 5.6.

Рис.5.7

50

Как видно, укорочение ветвей дерева поиска приводит к появлению в нем дихотомических фрагментов, а если задано l0 3 диз (минимально возможное значение), то дерево поис-

ка становится полностью дихотомическим (рис. 5.3б).

вии ограничений) до S 3 диз (при минимальном l0 ). При

больших значениях A рассмотренные эффекты проявляются намного сильнее.

51

Глава 6. КРИВЫЕ СНЯТИЯ НЕОПРЕДЕЛЕННОСТИ

6.1. Изменение неопределенности в процессе поиска

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

Информационные характеристики поиска рассмотрены в главе 4. Общее описание дерева поиска приведено на рис.2.3. При выполнении N -го измерения проверяется наличие реа-

Продвижение по ветвям дерева поиска рис. 2.1 (перебор индексов k , k1 и q ) зависит от значения реасобытия xr , и для каждого из них можно записать

N 1

то есть, как отмечалось в главе 4, сумма декрементов неопределенности равна энтропии множества состояний объекта.

Усредняя (6.2) по всем реасобытиям, с учетом равенства единице суммы их вероятностей можно записать

а изменив порядок суммирования по r и N , получим

N 1 r X ( N )

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

измерения. Согласно главе 4 эта величина не более единицы. После N -го измерения при заданном реасобытии xr ос-

где индексы k и q определяется составом множества X (N) .

6.2. Кривая снятия неопределенности

Назовем кривой снятия неопределенности (КСН) гра-

фически выраженную зависимость средней остаточной неопределенности (энтропии) состояния объекта H (N) от числа

53

выполненных двоичных измерений N согласно (6.6).

При отсутствии ошибочных измерений функция H (N) из (6.6) не возрастает при увеличении N и стремится к нулю при N lmax .

Вычисление КСН при заданном дереве поиска проводится следующим образом.

После первого измерения выделяются два подмножества

и среднюю остаточную энтропию после первого двоичного измерения

Далее процесс продолжается аналогично. При N -м измерения определяется множество X (N) реасобытий, поиск которых не заканчивается после (N 1) измерений, для каждой части ветви дерева поиска длиной не менее (N 1) диз выде-

54

ляются пары подмножеств X 0( N ,q) и X 1( N ,q ) ( q 1,2... - индек-

сы подмножеств) и вычисляются вероятности вида (6.7) и условные энтропии (6.8). Остаточная энтропия после N измерений равна

Помимо усредненной КСН H (N) можно рассматривать частные кривые снятия неопределенности в виде зависимостей H ( X k( N ,q) ) для определенных значений реасобытия., от выбора которого зависят значения индексов k и q .

6.3. Примеры КСН

6.3.1. Показательный закон распределения вероятностей состояний объекта и последовательный поиск

Обратимся к рассмотренному ранее закону распределения вероятностей состояний объекта (5.21) и (5.22),

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

Рис. 6.2

Исходная энтропия множества X для рассматриваемого распределения вероятностей из(4.1) с учетом (6.11) и (6.12) равна

Далее расчет проводится аналогично, а если реасобытием являются xA 1 или xA , то после измерения с номером N A 1

поиск завершится, и неопределенность состояния объекта будет равна нулю.

На рис. 6.4 представлены зависимости условной энтропии H ( X1( N ,1) ) и усредненной энтропии H (N) от номера измерения N при A 8 . Условная энтропия H ( X 0( N ,1) ) 0 , так как в состав подмножества X 0( N ,1) xN входит только один элемент,

переход к ней показан на рис. 6.4 пунктирными линиями.

Как видно, первое измерение снижает среднюю энтропию

57

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

Условная энтропия H ( X1( N ,1) ) уменьшается с ростом N существенно медленнее, чем средняя H (N) . Это обусловлено

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

Рис. 6.4

Среднее число измерений (потенциальная скрытность) в рассматриваемом примере определяется выражением (5.26) и при A 8 равна S 1,965. Максимальное число измерений

для последовательного алгоритма равно lmax A 1 и сущест-

венно больше S . Это означает, что продолжительность поиска может быть различной в зависимости от реасобытия.

Для оценки этого эффекта целесообразно рассматривать