Premium
How to find a battleship
Author(s) -
Fiat Amos,
Shamir Adi
Publication year - 1989
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230190306
Subject(s) - least squares function approximation , computer science , mathematics , mathematical optimization , algorithm , statistics , estimator
Consider a “sea” of M squares which contains (at some unknown location) a “battleship” of K squares. Both the sea and the battleship can assume any rectangular shape. Our goal is to find the battleship by probing at least one of its squares. In this paper we describe a deterministic strategy for this problem which is guaranteed to locate the battleship in at most c 1 M/K probes, where c 1 ≈ 3.065.