Theoretical foundation for solving search problems by the method of maximum entropy
DOI:
https://doi.org/10.21638/11701/spbu10.2023.304Abstract
The traditional problem of search theory is to develop a search plan for a physical object in the sea or on land. Known algorithms for the optimal distribution of search resources mainly use the exponential detection function. If we consider the search problem more broadly — as a problem of searching for various information, then the detection function can differ significantly from the exponential one. In this case, the solutions obtained using traditional algorithms may be correct from the point of view of mathematics, but unacceptable from the point of view of logic. In this paper, this problem is solved on the basis of the maximum entropy principle. The theorems are proved, as well as their consequences for four types of detection functions, which make it possible to create algorithms for solving various search problems based on the principle of maximum entropy.
Keywords:
information theory, search theory, uniformly optimal search plan, detection function, maximum entropy principle
Downloads
References
Акоф Р., Сасиени М. Основы исследования операций / пер. с англ.; под ред. И. А. Ушакова. М.: Мир, 1971. 533 с.
Альсведе Р., Вегенер И. Задачи поиска / пер. с нем. В. А. Душского; ред. М. Б. Малютов. М.: Мир, 1982. 367 с.
Information theory, combinatorics, and search theory: In memory of Rudolf Ahlswede / eds by H. Aydinian, F. Cicalese, C. Deppe. Vol. 7777 of Lecture Notes in Computer Science. Cambrige: Springer, 2013. 773 p. https://doi.org/10.1007/978-3-642-36899-8
Jaynes E. T. Entropy and search theory // Maximum-entropy and Bayesian methods in inverse problems. Fundamental theories of physics. Dordrecht, Netherlands: Springer, 1985. Vol. 14. P. 1–18.
Прокаев А. Н. Принцип максимума энтропии в теории поиска // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2023. Т. 19. Вып. 1. С. 27–42. https://doi.org/10.21638/11701/spbu10.2023.103
Stone L. D., Royset J. O., Washburn A. R. Optimal search for moving targets. Switzerland: Springer, 2016. 312 p. (International Series in Operations Research & Management Science no. 237). https://doi.org/10.1007/978-3-319-26899-6_1
Prokaev A. N. Search efforts optimal distribution based on the posteriori entropy analysis // ResearchGate. Online publication. February 20, 2016. https://doi.org/10.13140/RG.2.1.1446.1209/1.
Pierce J. G. A new look at the relation between information theory and search theory // The maximum entropy formalism. Cambridge: MIT Press, 1978. P. 339–402.
References
Ackoff R. L., Sasieni M. W. Fundamentals of operations research. New York, John Wiley & Sons, Inc. Publ., 1967, 455 p.
Ahlswede R., Wegener I. Suchprobleme (eng. Search Problems). Stuttgart, Teubner Verlag Publ., 1979, 273 p.
Information theory, combinatorics, and search theory: In memory of Rudolf Ahlswede. Eds by H. Aydinian, F. Cicalese, C. Deppe. Vol. 7777 of Lecture Notes in Computer Science. Cambrige, Springer Publ., 2013, 773 p. https://doi.org/10.1007/978-3-642-36899-8
Jaynes E. T. Entropy and search theory. Maximum-entropy and Bayesian methods in inverse problems. Fundamental theories of physics. Dordrecht, Netherlands, Springer Publ., 1985, vol. 14, mboxpp. 1–18.
Prokaev A. N. Printsip maksimuma entropii v teorii poiska [The maximum entropy principle in search theory]. Vestnik of Saint Petersburg University. Applied Mathematics. Computer
Science. Control Processes, 2023, vol. 19, iss. 1, pp. 27–42. https://doi.org/10.21638/11701/spbu10.2023.103 (In Russian)
Stone L. D., Royset J. O., Washburn A. R. Optimal search for moving targets. Switzerland, Springer Publ., 2016, 312 p. (International Series in Operations Research & Management Science no. 237). https://doi.org/10.1007/978-3-319-26899-6_1
Prokaev A. N. Search efforts optimal distribution based on the posteriori entropy analysis. ResearchGate. Online publication, February 20, 2016. https://doi.org/10.13140/RG.2.1.1446.1209/1.
Pierce J. G. A new look at the relation between information theory and search theory. The Maximum Entropy Formalism. Cambridge, MIT Press, 1978, pp. 339–402.
Downloads
Published
How to Cite
Issue
Section
License
Articles of "Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.
