вероятностей ошибки единичного измерения. Общее время комбини-
рованного поиска составляет
T
кп
(
i
) = (
i
−
1)
T
∗
шд
(
i
) + 2
n
−
i
T
∗
шп
(
i
)
.
(17)
Определим теперь номер шага
i
∗
, на котором выгоднее всего пе-
рейти от дихотомического поиска к последовательному. Очевидно, что
задача нахождения величины
i
∗
является целочисленной задачей опти-
мизации, где критерием оптимальности будет разность между време-
нем “чистого” дихотомического поиска и временем комбинированного
поиска. Чем больше эта разность, тем больше выигрыш во времени
при переходе от дихотомического поиска к комбинированному. Таким
образом, задача оптимизации сводится к задаче отыскания максимума
следующей целевой функции:
F
ц
(
i
) =
T
дп
−
T
кп
(
i
) =
nT
шд
−
(
i
−
1)
T
∗
шд
(
i
) + 2
n
−
i
T
∗
шп
(
i
)
.
(18)
При этом выигрыш по времени при использовании данного метода
вместо дихотомического поиска можно оценить по значению коэффи-
циента
μ
=
T
дп
T
пп
.
(19)
Рассмотрим решение данной задачи для нескольких частных случа-
ев. Положим значение базы сигнала равным
N
=
{
2
5
,
2
10
,
2
15
,
2
20
,
2
30
}
.
Тогда, максимизировав
F
ц
(
i
)
методом перебора по всем целочислен-
ным значениям
i
, получаем
i
∗
=
{
2
,
7
,
11
,
16
,
25
}
соответствен-
но. При этом выигрыш по времени составит
μ
= {1,68, 1,42, 1,32,
1,25, 1,18}, т.е. для сигналов с базами
N
= (2
10
. . .
2
30
)
применение
комбинированного метода поиска вместо дихотомического позволяет
сократить на 42. . . 18% время поиска.
Далее приведены графики зависимости коэффициента
μ
от номера
шага
i
, на котором осуществляется переход от дихотомического поиска
к последовательному, для различных баз ПБП.
Изрис. 1 видно, что слишком ранний переход от дихотомического
поиска к последовательному крайне нежелателен, так как при
i < i
∗
комбинированный поиск требует б´ольших временных затрат, чем “чи-
стый” дихотомический поиск. Такой характер зависимости
μ
(
i
)
в
области малых значений
i
является интуитивно понятным, так как
с уменьшением
i
общее число измерений, производимых в процессе
комбинированного поиска, экспоненциально возрастает согласно фор-
муле (12). При
i
= 1
комбинированный поиск вырождается в “чистый”
последовательный поиск.
Поздний переход от дихотомического поиска к последовательному
(при
i > i
∗
)
также нежелателен. Как указывалось ранее, при достаточ-
но больших значениях
i
становится существенным тот факт, что время
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 3 51
