This article is cited in 1 paper

Large Systems

Search for a moving element with the minimum total cardinality of tests

A. V. Lebedev, V. S. Lebedev

Kharkevich Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow, Russia

Abstract: We consider the moving element search problem with the minimum total cardinality of tests. As a search space, we consider the set of integer points of a segment of length $n$. We prove that the total test cardinality of an asymptotically optimal adaptive strategy is $n+2\sqrt{n}$.

Keywords: combinatorial search, test, adaptive strategy, optimal algorithm.

UDC: 621.391.1 : 519.1

Received: 07.03.2019
Revised: 15.10.2019
Accepted: 12.11.2019

DOI: 10.1134/S0555292319040053

 English version: Problems of Information Transmission, 2019, 55:4, 396–400

Bibliographic databases:

• 
• 
•