ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ

Том 55

2019

Вып. 4

УДК 621.391.1 : 519.1

А.В. Лебедев, В.С. Лебедев

ПОИСК ДВИЖУЩЕГОСЯ ЭЛЕМЕНТА

С МИНИМАЛЬНОЙ СУММАРНОЙ МОЩНОСТЬЮ ТЕСТОВ¹

Рассматривается задача поиска движущегося элемента с минимальной сум-

марной мощностью тестов. В качестве пространства поиска рассматривается

множество целых точек отрезка длины n. Доказывается, что суммарная мощ-

ность тестов асимптотически оптимальной адаптивной стратегии равна n+2√n.

Ключевые слова: комбинаторный поиск, тест, адаптивная стратегия, оптималь-

ный алгоритм.

DOI: 10.1134/S0555292319040053

§ 1. Введение

В 2010 году на конференции, посвященной задачам комбинаторного поиска (Гер-

мания, Билефельд, 25-29 октября, ZIF Workshop Search Methodologies II), Р. Алсведе

предложил рассмотреть комбинаторную модель поиска движущегося объекта. Раз-

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

комбинаторному поиску участникам конференции известно не было.

В работах [1,2] была поставлена следующая задача поиска объекта, движущегося

по вершинам графа. Определим пространство поиска как вершины графа G(V, E),

V = {v₁,...,v_n}. Объект поиска (дефектный элемент) находится в одной из вершин

графа G. Тестом T, T ∈ V , называется подмножество вершин графа, а мощностью

теста - число вершин в нем. Результатом теста (ответом) ρ(T) является правильный

ответ на вопрос, находится ли дефектный элемент в вершине, входящей в тест. Если

дефектный элемент находится в вершине, входящей в тест, такой тест называется

позитивным. Положим

^{1, если тест позитивный,

ρ(T ) =

в противном случае.

Последовательность тестов T₁, T₂, . . ., в которой каждый следующий тест зависит

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

и далее мы рассматриваем только такие стратегии. После каждого теста дефектный

элемент может либо остаться на месте, либо переместиться в соседнюю вершину

графа.

Стратегия поиска называется s-успешной, если для любого первоначального рас-

положения дефектного элемента и любых способов его перемещения она позволяет

после последнего теста указать множество вершин графа мощности не более чем s,

включающих дефектный элемент (обратим внимание, что после последнего теста

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

¹ Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных

исследований (номер проекта 19-01-00364).

107

При этом s-успешная стратегия называется оптимальной, если число тестов в ней

минимально, и σ-оптимальной, если суммарная мощность ее тестов минимальна.

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

сложной задачей. Но в частном случае линейного графа задача может быть ре-

шена, и в работах [1,2] была указана оптимальная стратегия для этого случая.

Здесь мы рассмотрим задачу нахождения σ-оптимальной стратегии для линейно-

го графа L(n), n четно, который отождествим с множеством целых точек отрезка

[-n/2, +n/2], т.е. V = {-n/2, -n/2 + 1, . . . , n/2 - 1, n/2}, любые две соседние точки

которого связаны ребром.

Так как в [1,2] было доказано, что при s < 4 и n > 5 не существует s-успешных

стратегий поиска, то мы рассматриваем только случай s = 4. Суммарная мощность

тестов оптимальной стратегии в указанных работах равнялась 3n/2, и в настоящей

статье мы существенно улучшим этот результат, а именно предложим асимптотиче-

ски σ-оптимальную стратегию для линейного графа при n → ∞.

Заметим, что случай неподвижной дефектной вершины (в этом случае струк-

тура графа уже не важна, и рассматриваются задачи с несколькими дефектами)

эквивалентен классической проблеме группового тестирования (см. [3-6]).

§2. Построение стратегии поиска движущегося элемента

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

соседнее место влево или вправо, или же остаться на месте. Мы хотим локализовать

дефектный элемент, т.е. после какого-то количества тестов указать четыре вершины

линейного графа, в одной из которых находится дефектный элемент. Уточним, что

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

элемент может совершить движение (т.е. сдвинуться на соседнее место влево или

вправо).

Теорема 1. Для линейного графа L(n) существует 4-успешная стратегия с

суммарной мощностью тестов

Δ=n+2√n + o(√n)

при n → ∞.

Доказательство. Рассмотрим следующую стратегию. Первый тест

T₁ = [-(⌊√n⌋ + 1); ⌊√n⌋ + 1].

(Для целых a и b под отрезком [a, b] мы подразумеваем все целочисленные точки

этого отрезка [a, b]. Мощность такого теста равна b - a + 1.)

До тех пор, пока результаты тестов равняются 0, в качестве следующих тестов

T_m, m = 2, 3, . . ., будем брать два отрезка:

T_m = [-X_m, -Xm-1] ∪ [Xm-1, X_m],

где

∑

X_m =

(⌊√n⌋ + 2 - i).

(1)

i=1

Заметим, что в какой-то момент обязательно появится ответ 1, так как X_m ста-

нет больше, чем n/2. Пусть это будет после теста с номером r. Обозначим через ℓ

квадратный корень из длины отрезка [Xr-1, X_r], т.е.

⌋

⌊√

⌋

⌊√

√

ℓ= X_r -Xr-1 +1

⌊

n⌋ - r + 3 .

108

Задаем тесты

[-(Xr-1 + (w + 1)ℓ - 1), -(Xr-1 + wℓ - 1)] ∪ [Xr-1 + wℓ - 1, Xr-1 + (w + 1)ℓ - 1]

для w = 0, 1, 2, 3, . . . до тех пор, пока не получим ответ 1. Это случится, поскольку

за ℓ+3 тестов дефект не сможет сдвинуться от точки Xr-1 (соответственно, -Xr-1,

если он в отрицательной области) дальше чем на (ℓ+1)²+(ℓ+1)+3. Но в тесты войдут

по (ℓ + 3)(ℓ + 1) различных точек с каждой стороны, т.е. ответ 1 точно появится.

После ответа 1 (пусть это будет после теста с номером r+w+1) рассмотрим тест

[Xr-1 + wℓ - 2, Xr-1 + (w + 1)ℓ]

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

общности, будем считать, что дефект окажется в положительной части.

Далее задаем тесты для i = 1, 2, 3, . . .

[Xr-1 + wℓ - 4 + i, Xr-1 + wℓ - 3 + i],

пока не сможем локализовать дефект, прижав его к крайней точке n/2.

Оценим суммарную мощность тестов предложенной стратегии:

Δ(V ) ≤ 2X_r + 2r + 2(w + 1)(ℓ + 2) + ℓ + 1 + 3 + 2(n/2 - Xr-1 - wℓ + 4).

Следовательно,

Δ(V ) ≤ n + 2(X_r - Xr-1) + 2r + 4w + 3ℓ + 20.

Значит, асимптотически

Δ(V ) ≤ n + 2

√n)

(2)

при n → ∞. ▴

§ 3. Доказательство асимптотической σ-оптимальности построенной стратегии

Будем называть “i-й областью нахождения дефекта” подмножество N_i, на кото-

ром после i-го теста и возможного перемещения дефекта может находится дефект-

ный элемент с учетом ответов на тесты.

Будем считать, что любой тест Ti+1 является подмножеством области N_i (иначе

пересечение теста с этой областью дало бы тест меньшей мощности, дающий ту же

информацию). В дальнейшем мы будем рассматривать только такие тесты.

Также будем считать, что все тесты имеют мощность 2 ≤ |T_i| ≤ |Ni-1|/2. Дей-

ствительно, тесты мощности 1 не несут никакой информации, так как область на-

хождения дефекта не содержит изолированных вершин, и при ответе 0 на i-й тест

мощности 1 всегда Ni-1 ⊂ N_i. Кроме того, всегда можно вместо T_i рассмотреть тест,

дополняющий T_i до Ni-1, и поэтому можно считать, что |T_i| ≤ |Ni-1|/2. Тот факт,

что тесты мощности 1 (как и тесты любой мощности, состоящие из изолированных

вершин) не несут никакой информации, в какой-то степени объясняет, почему нель-

зя решить задачу с s = 3 (при n > 5). Действительно, если мы получим ответ 1 на

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

связную компоненту мощности 2, отделенную от краев отрезка, то в области нахож-

дения дефекта всегда будут находиться четыре подряд идущих элемента. Строгое

доказательство этого факта можно найти в [2].

Легко видеть, что N₀ = N, и что для i = 1, . . ., n имеем

^{Γ(T_i),

если ρ(T_i) = 1,

N_i =

Γ(Ni-1 \ T_i), если ρ(T_i) = 0,

109

где Γ(A) := {j ∈ N : ∃i ∈ A (i, j) ∈ E}. Таким образом, N_i является пространством

поиска после i-го теста и возможного перемещения дефектного элемента.

Используя понятие i-й области нахождения дефекта, можно переформулировать

определение успешной стратегии. Стратегия называется s-успешной, если при лю-

бом начальном расположении дефекта и любых способах его перемещения |N_i| ≤ s

для некоторого i.

Для получения нижней оценки суммарной мощности тестов любой 4-успешной

стратегии нам понадобится следующая

Лемма. Пусть ответ на тест T, где |T| > 2, равен 1, и точка k - ближай-

шая к 0 точка из T. Тогда суммарная мощность тестов, которые еще придется

задать, чтобы построить 4-успешную стратегию, не меньше n-2|k|-4 при n ≥ 8.

Доказательство. Действительно, это сразу следует из того, что в [2] была

построена успешная стратегия, в которой после определения, что дефект находит-

ся на отрезке [j, n/2] (без ограничения общности будем считать, что j ≥ -1), тест

[j, j + 1] в случае ответов 0 сдвигался вправо на единицу, пока не доходил на рас-

стояние 3 до края. Было доказано, что нет успешных стратегий с меньшим числом

тестов. Последний тест был [n/2 - 4, n/2 - 3]. Следовательно, в любой успешной

стратегии, начинающейся с теста T , где |T | > 2, ρ(T ) = 1 и точка k - ближайшая к 0

точка из T, число тестов будет не менее n/2 - |k| - 2. Действительно, мы рассмат-

риваем случай, когда все начинается с теста [k - 1, k], а мощность каждого теста не

менее 2. Отсюда получаем требуемую оценку. ▴

Теорема 2. Для любой 4-успешной стратегии сумма мощностей тестов не

меньше n + 2√n + O(1) при n → ∞.

Доказательство. Пусть

∑

m(m + 1)

Y_m =

(√n - 2 - i + pi) = (√n - 2)m -

+ p_i,

i=1

где p₁ = ⌈√n⌉ -√n, p2 = -(√n - ⌊√n⌋), и для i > 2

⎧

∑

^⎨p₁, если

p_j < 0,

p_i =

j=1

⎩

p₂

в противном случае.



∑



Заметим, что Y_m при всех m принимают целочисленные значения и

p_i



^<

i=1

Поскольку мы рассматриваем решение задачи для всех возможных вариантов

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

будут получены следующие ответы:

На тест мощности 2 мы всегда получаем ответ 0. Для остальных мощностей после

теста T_m, где m = 1, 2, . . ., m ≤

√n - 3, получаем такие ответы:

Если еще не было ответа 1 и [-Y_m; Y_m] ∩ Nm-1 ⊆ T_m, то ответ 1, в противном

случае - 0. В случае ответа 0 после m-го теста дефект еще может находиться внутри

отрезка [-Y_m; Y_m]. При нулевом ответе переходим к следующему тесту, а как только

впервые будет ответ 1 (пусть это будет после теста с номером m), оценим сумму

мощностей тестов успешной стратегии с первыми m тестами.

Поскольку на тест Tm-1 был дан ответ 0, то согласно лемме суммарная мощность

тестов еще увеличится не менее чем на n - 2Ym-1 - 4.

Если одна половина отрезка L (например, отрицательная) в какой-то момент це-

ликом оказалась вне области нахождения дефекта, то Δ ≥ n/2 + Y_m + m + n -

- 2Ym-1 - 4, где слагаемое m получается из точек, входивших в тест, но добавля-

ющихся в зону нахождения дефекта, а n - 2Ym-1 - 4 добавляется согласно лемме.

110

Величина Ym-1 не превосходит n/2 - 5/2

√n + 3, поэтому

Δ ≥ n/2 +

√n - 2 - m + m + n - n/2 + 5/2√n - 1 ≥ n + 2√n + O(1)

при n → ∞.

Если же обе половины отрезка имеют непустое пересечение с областью нахож-

дения дефекта, то после каждого теста в область нахождения дефекта добавлялось

не менее двух точек, и тогда получаем Δ ≥ 2Y_m + 2m + n - 2Ym-1 - 4. Имеем

Δ ≥ n + 2m + 2√n - 4 - 2m. Поэтому асимптотически получаем, что

Δ≥n+2√n + O(1)

при n → ∞.

В случае, когда мы дошли до m =

√n - 3 со всеми ответами 0, получаем, что

множество [-Y√n-3, Y√n-3], мощность которого асимптотически равна n-5√n, уже

покрыто предыдущими тестами. Из леммы вытекает, что еще придется рассмотреть

тесты общей суммарной мощности не менее 5√n + O(1) при n → ∞. При этом

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

√n, поэтому добавляется мощность 2√n (либо

√n + 5/2√n, если одна половина отрезка в какой-то момент целиком оказалась вне

области нахождения дефекта).

Поэтому Δ ≥ n + 2√n + O(1) при n → ∞, а значит, теорема доказана. ▴

Также представляют интерес задачи поиска, когда дефектный элемент может

совершить движение не более чем t раз. В случае адаптивного поиска эти задачи

перекликаются с задачей поиска со лжецом (подробнее см. в [4, 7, 8]).

СПИСОК ЛИТЕРАТУРЫ

1. Aydinian H., Cicalese F., Deppe C., Lebedev V. Optimal Strategies for a Model of Combina-

torial Two-Sided Search // Proc. 7th Int. Workshop on Optimal Codes and Related Topics

(OC’2013). Albena, Bulgaria. Sept. 6-12, 2013. P. 7-12.

2. Aydinian H., Cicalese F., Deppe C., Lebedev V. A Combinatorial Model of Two-Sided

Search // Int. J. Found. Comput. Sci. 2018. V. 29. № 4. P. 481-504.

3. Benkoski S.J., Monticino M.G., Weisinger J.R. A Survey of the Search Theory Literature //

Naval Res. Logist. 1991. V. 38. № 4. P. 469-494.

4. Cicalese F. Fault-Tolerant Search Algorithms. Berlin: Springer, 2013.

5. Du D.Z., Hwang F.K. Combinatorial Group Testing and Its Applications. Singapore: World

Sci., 2000.

6. Koopman B.O. Search and Screening // OEG Report № 56. Washington, D.C.: Operations

Evaluation Group, Office of the Chief of Naval Operations, Navy Dept., 1946.

7. Ahlswede R., Deppe C., Lebedev V. Non-binary Error Correcting Codes with Noiseless Feed-

back, Localized Errors, or Both // Ann. European Acad. Sci. 2005. № 1. P. 285-309.

8. Лебедев В.С. Кодирование при наличии бесшумной обратной связи // Пробл. передачи

информ. 2016. Т. 52. № 2. С. 3-14.

Лебедев Алексей Владимирович

Поступила в редакцию

Лебедев Владимир Сергеевич

07.03.2019

Институт проблем передачи информации

После доработки

им. А.А. Харкевича РАН

15.10.2019

al_lebed95@mail.ru

Принята к публикации

lebed37@mail.ru

12.11.2019

111