Журнал вычислительной математики и математической физики, 2019, T. 59, № 5, стр. 905-910
Быстрый алгоритм решения простейшей задачи поиска
В. Н. Малозёмов 1, *, Г. Ш. Тамасян 1, **
1 С.-Пб гос. ун-т
199034 С.-Петербург, Университетская наб., 7/9, Россия
* E-mail: v.malozemov@spbu.ru
** E-mail: g.tamasyan@spbu.ru
Поступила в редакцию 23.03.2018
После доработки 11.01.2019
Принята к публикации 11.01.2019
Аннотация
Предлагается быстрый алгоритм решения задачи Данскина. Анализируется зависимость решения от параметров. Библ. 6. Фиг. 4. Табл. 1.
1. ВВЕДЕНИЕ
Рассматривается простейшая задача поиска в следующей постановке. Пусть имеется $X$ единиц времени для обнаружения некоторого объекта. Объект может находиться в одном из $n$ мест, причем известна вероятность его нахождения в каждом из этих мест. Известна также вероятность обнаружения объекта, если он находится в $i$-м месте при всех $i$ от 1 до $n$. Разумеется, эта вероятность зависит от времени поиска. Требуется разбить общее время поиска $X$ на $n$ частей (по числу мест возможного нахождения объекта) так, чтобы максимизировать вероятность обнаружения объекта. Частный случай этой задачи рассмотрел Дж. М. Данскин в своей книге, посвященной теории максимина [1, с. 22–24]. С помощью леммы Гиббса он вывел необходимое условие максимума и в общих чертах описал метод решения задачи. В данной заметке предложен быстрый алгоритм решения задачи Данскина и проанализирована зависимость решения от параметров.
2. ПОСТАНОВКА ЗАДАЧИ
Пусть в нашем распоряжении имеется $X$ единиц времени на поиск некоторого объекта. Этот объект может находиться в одном из $n$ мест. Если объект находится в $i$-м месте, то, потратив ${{x}_{i}}$ единиц времени, мы можем обнаружить его с вероятностью $1 - {{e}^{{ - {{b}_{i}}{{x}_{i}}}}}$. Параметр ${{b}_{i}}$ можно интерпретировать как уровень условий, благоприятствующих поиску объекта в $i$-м месте. Вероятность того, что объект находится в $i$-м месте, равна ${{a}_{i}}$. Как разбить общее время поиска $X$ на сумму ${{x}_{i}}$ так, чтобы максимизировать вероятность обнаружения интересующего нас объекта?
Приходим к экстремальной задаче, которую будем называть задачей Данскина:
(1)
$\begin{array}{*{20}{c}} {F(x): = \sum\limits_{i = 1}^n \,{{a}_{i}}(1 - {{e}^{{ - {{b}_{i}}{{x}_{i}}}}}) \to max,} \\ {\sum\limits_{i = 1}^n \,{{x}_{i}} = X,\quad {{x}_{i}} \geqslant 0\quad \forall i \in 1:n.} \end{array}$Целевая функция $F(x)$ строго вогнута на ${{\mathbb{R}}^{n}}$, а множество планов (векторов, удовлетворяющих ограничениям экстремальной задачи) компактно. Это гарантирует существование и единственность решения задачи (1).
3. УСЛОВИЯ ОПТИМАЛЬНОСТИ. РЕШЕНИЕ ЗАДАЧИ
По лемме Гиббса [1] (см. также препринт [2]) план $x = \left( {{{x}_{1}},\; \ldots ,\;{{x}_{n}}} \right)$ задачи (1) будет оптимальным тогда и только тогда, когда при некотором вещественном $\lambda $ выполняются соотношения
(2)
${{a}_{i}}{{b}_{i}}{{e}^{{ - {{b}_{i}}{{x}_{i}}}}} = \lambda ,\quad {\text{е с л и }}\quad {{x}_{i}} > 0,$На основании (2) формулу (4) можно переписать в виде
(6)
${{x}_{i}} = \frac{1}{{{{b}_{i}}}}ln\frac{{{{a}_{i}}{{b}_{i}}}}{\lambda },\quad {\text{е с л и }}\quad {{a}_{i}}{{b}_{i}} > \lambda .$Равенство (2) гарантирует положительность $\lambda $, поэтому условия ${{a}_{i}}{{b}_{i}} > \lambda $ и ${{a}_{i}}{{b}_{i}} \leqslant \lambda $ равносильны тому, что $\tfrac{{{{a}_{i}}{{b}_{i}}}}{\lambda } > 1$ и $\tfrac{{{{a}_{i}}{{b}_{i}}}}{\lambda } \in (0,1]$. Данное замечание позволяет объединить формулы (6) и (5) следующим образом:
гдеОбозначим ${{c}_{i}} = ln{{a}_{i}}{{b}_{i}}$, $u = ln\lambda $ и покажем, что
Условия $\tfrac{{{{a}_{i}}{{b}_{i}}}}{\lambda } > 1$ и $\tfrac{{{{a}_{i}}{{b}_{i}}}}{\lambda } \in (0,1]$ равносильны соответственно неравенствам ${{c}_{i}} - u > 0$ и ${{c}_{i}} - u \leqslant 0$. Согласно (7) получаем
Таким образом, решение задачи (1) сводится к решению скалярного уравнения (9) и вычислению компонент оптимального плана по формуле (8).
4. ОПИСАНИЕ АЛГОРИТМА
Опишем быстрый алгоритм решения уравнения (9).
Начнем с того, что упорядочим пары $({{b}_{i}},{{c}_{i}})$, $i \in 1:n$, по невозрастанию второй компоненты. Получим последовательность
(10)
$\varphi (u) = \sum\limits_{i = 1}^n \frac{1}{{{{{\hat {b}}}_{i}}}}{{({{\hat {c}}_{i}} - u)}_{ + }}.$(13)
$\varphi (u) = \sum\limits_{i = 1}^n \frac{{{{{\hat {с }}}_{i}}}}{{{{{\hat {b}}}_{i}}}} - \left( {\sum\limits_{i = 1}^n \frac{1}{{{{{\hat {b}}}_{i}}}}} \right)u\quad {\text{п р и }}\quad u \leqslant {{\hat {c}}_{n}}.$В силу (12) получаем
(14)
$\varphi (u) = \varphi ({{\hat {c}}_{k}}) + {{p}_{k}}({{\hat {c}}_{k}} - u),\quad u \in [{{\hat {c}}_{{k + 1}}},{{\hat {c}}_{k}}],\quad k \in 1:n - 1.$(15)
$\varphi (u) = \varphi ({{\hat {c}}_{n}}) + {{p}_{n}}({{\hat {c}}_{n}} - u),\quad u \leqslant {{\hat {c}}_{n}}.$На основании (10), (11), (14) и (15) заключаем, что функция $\varphi (u)$ является непрерывной ломаной, выпуклой и строго убывающей от $ + \infty $ до $0$ на полуоси $( - \infty ,{{\hat {c}}_{1}})$ (см. фиг. 2).
Отметим, что ломаная $\phi (u)$ на отрезке $[{{\hat {c}}_{n}},{{\hat {c}}_{1}}]$ полностью определяется своими значениями $\varphi ({{\hat {c}}_{k}})$ в узлах ${{\hat {c}}_{k}}$, $k \in 1:n$. В силу (14) эти значения связаны формулой
Нас интересует решение $u{\text{*}}$ уравнения $\varphi (u) = X$. Из свойств функции $\varphi (u)$ следует, что такое решение существует и единственно. Для его нахождения будем последовательно вычислять значения ${{\varphi }_{1}},\;{{\varphi }_{2}},\; \ldots $ по формулам (16), пока не встретим индекс ${{k}_{0}}$, на котором
В этом случае $u{\text{*}}$ принадлежит отрезку $\left[ {{{{\hat {c}}}_{{{{k}_{0}} + 1}}},{{{\hat {c}}}_{{{{k}_{0}}}}}} \right]$ (см. фиг. 3).Согласно (14) имеем
(17)
$u* = {{\hat {c}}_{{{{k}_{0}}}}} - \frac{1}{{{{p}_{{{{k}_{0}}}}}}}(X - {{\varphi }_{{{{k}_{0}}}}}).$Если ${{\varphi }_{n}} < X$, то $u* < {{\hat {c}}_{n}}$. В силу (15), $u{\kern 1pt} *$ вычисляется по той же формуле (17) при ${{k}_{0}} = n$.
На основании (8) для компонент решения $x* = (x_{1}^{ * },\; \ldots ,\;x_{n}^{ * })$ задачи (1) получаем представление
Замечание 1. Описанный алгоритм сходится не более, чем за $n$ шагов. И в общем случае требует сортировку элементов массива длиной $n$ и не более $6n - 2$ арифметических операций, т.е. имеет сложность порядка $O(nlo{{g}_{2}}(n))$.
Замечание 2. Используя специфику алгоритма, можно минимизировать его трудоемкость. Действительно, для последовательного нахождения значений ${{\varphi }_{k}}$, $k = 1:n$, (см. (16)) необязательно иметь всю отсортированную по невозрастанию последовательность ${{\hat {c}}_{1}} \geqslant {{\hat {c}}_{2}} \geqslant \; \ldots \; \geqslant {{\hat {c}}_{n}}$. Достаточно находить лишь одно значение из этой последовательности для каждой следующей итерации (см. [3]).
Замечание 3. В работах [4], [5] предложены алгоритмы решения скалярного уравнения вида (9), имеющие линейный порядок сложности [6]. Однако численные эксперименты показали их малую эффективность с точки зрения временных затрат (см. [3]).
5. ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ
Напомним, что параметр ${{b}_{i}}$ интерпретируется как уровень условий, благоприятствующих поиску объекта в $i$-м месте. Представляет интерес проанализировать влияние параметров ${{b}_{i}}$ на оптимальное распределение $\{ x_{i}^{ * }\} $.
Возьмем конкретные данные. Пусть $n = 4$, ${{a}_{1}} = 0.4$, ${{a}_{2}} = 0.3$, ${{a}_{3}} = 0.2$, ${{a}_{4}} = 0.1$, $X = 3$. При ${{b}_{1}} = {{b}_{2}} = {{b}_{3}} = {{b}_{4}} = 1$ оптимальное распределение $x* = (x_{1}^{ * },x_{2}^{ * },x_{3}^{ * },x_{4}^{ * })$ имеет вид
Теперь при каждом фиксированном $i \in 1:4$ будем изменять значения ${{b}_{i}}$, сохраняя остальные ${{b}_{k}}$ равными единице. На фиг. 4 изображены четыре графика, которые показывают, как изменяются $x_{i}^{ * }$ в зависимости от ${{b}_{i}}$.На каждом графике выделяются два значения параметра ${{b}_{i}}$:
В табл. 1 представлена более полная информация об изменении всего оптимального распределения $x{\text{*}}$ при изменении ${{b}_{2}}$.
Список литературы
Данскин Дж.М. Теория максимина и ее приложение к задачам распределения вооружения. Пер. с англ. М.: Сов. радио, 1970. 200 с.
Малоземов В.Н., Тамасян Г.Ш. Лемма Гиббса и ее приложения // Семинар “CNSA & NDO”. Избранные доклады. 10 октября 2017 г. URL: http://www.apmath.spbu.ru/cnsa/reps17.shtml#1010 (дата обращения: 01.03.2018).
Tamasyan G., Prosolupov E. Orthogonal projection of a point onto the standard simplex: algorithms analysis // Proc. 2015 Int. Conf. “Stability and Control Processes” in Memory of V. I. Zubov (SCP) (St. Petersburg, Russia, Oct. 5–9, 2015). IEEE, 2015. P. 353–356. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7342137
Brucker P. An $O(n)$ algorithm for quadratic knapsack problems // Oper. Res. Lett. 1984. V. 3. № 3. P. 163–166.
Maculan N., Galdino de Paula G., Jr. A linear-time median-finding algorithm for projecting a vector on the simplex of ${{\mathbb{R}}^{n}}$ // Oper. Res. Lett. 1989. V. 8. № 4. P. 219–222.
Просолупов Е.В., Тамасян Г.Ш. Оценка трудоемкости алгоритма по поиску нуля одной выпуклой кусочно-линейной функции // Дискрет. анализ и исслед. операций. 2018. Т. 25. № 2. С. 82–100.
Дополнительные материалы отсутствуют.
Инструменты
Журнал вычислительной математики и математической физики