Рис. 3. Зависимость среднего времени по-
иска от ОСШ для параметров:
m
= 1024
,
N
= 0
,
5
;
T
= 55
— кривая
1
,
T
= 45
— кривая
2
,
T
= 40
— кривая
3
рис. 3 видно, что с ростом
ОСШ среднее время поиска
стремится к некоторому асим-
птотическому значению
A
≈
T
m
2
,
(10)
где первый множитель — это
время анализа каждой ячейки,
а второй — среднее число яче-
ек, проанализированных до за-
вершения поиска.
Сравнение эффективно-
сти различных систем по-
иска.
Использую изложенную
методику, можно исследовать
и качественно сравнить раз-
личные системы поиска. В работе [2] описан алгоритм поиска с про-
веркой результатов (верификацией). Исходя из аппаратных затрат [2, 9]
данный алгоритм наиболее близок к системе двухэтапного поиска [3],
что позволяет говорить о целесообразности применения изложенной
методики для сравнения рабочих характеристик этих алгоритмов.
Передаточная функция системы с двухэтапным поиском из началь-
ного состояния в состояние успешного завершения поиска может быть
получена аналогично выражению (2). На рис. 4 представлен напра-
вленный граф системы с двухэтапным поиском.
После применения формулы Мэйсона и методики сокращения на-
правленных графов [1, 5], получаем выражение для передаточной
функции (начальные условия, аналогичны случаю простого цикли-
ческого поиска)
H
2
(
z
) =
=
(1
−
β
)(1
−
β
)
z
T
1
+
T
2
m
−
1
i
=0
(1
−
α
)
z
T
1
+
α
(1
−
α
)
z
T
1
+
T
2
i
m
1
−
(
βz
T
1
+(1
−
β
)
β z
T
1
+
T
2
) ((1
−
α
)
z
T
1
+
α
(1
−
α
)
z
T
1
+
T
2
)
m
−
1
,
(11)
где
α
и
β
— вероятности ложной тревоги и пропуска при анализе каж-
дой ячейки неопределенности на втором этапе [3]. Эти вероятности
также вычисляются по формулам (7) и (8). Разница в параметрах для
первого и второго этапов — это длительность анализа:
T
1
— на первом
этапе,
T
2
— на втором.
На рис. 5 приведен направленный граф системы поиска ШПС с
верификацией [2].
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4 83
