Принцип максимума энтропии в теории поиска

Александр Николаевич Прокаев

doi:10.21638/11701/spbu10.2023.103

Авторы

Александр Николаевич Прокаев Санкт-Петербургский институт информатики и автоматизации Российской академии наук, Научно-техническое бюро высоких технологий, Российская Федерация, 199178, Санкт-Петербург, 14-я линия В. О., 39 https://orcid.org/0000-0002-9843-0417

DOI:

https://doi.org/10.21638/11701/spbu10.2023.103

Аннотация

В исследовании операций задачей теории поиска является разработка плана поиска физического объекта в море или на суше. Оптимальным решением традиционно считается так называемый «равномерно оптимальный поисковый план», обеспечивающий равномерное распределение апостериорной вероятности местонахождения объекта по мере ведения поиска. Вместе с тем достижение оптимальности одновременно по критериям максимума вероятности обнаружения и равенства апостериорной вероятности возможно только для экспоненциальной функции обнаружения. Для функций обнаружения другого вида оптимальные решения по указанным критериям не совпадают. Описана связь теории поиска с теорией информации. Подход к указанной проблеме рассмотрен на основе принципа максимума энтропии. Для ситуации дискретного распределения показано, что в рамках теории информации задача поиска имеет более простое решение, не зависящее от вида функции обнаружения.

Ключевые слова:

теория информации, теория поиска, равномерно оптимальный поисковый план, функция обнаружения, принцип максимума энтропии

Скачивания

Данные скачивания пока недоступны.

Библиографические ссылки

Литература

Ackoff R. L., Sasieni M. W. Fundamentals of operations research. New York, USA: John Wiley & Sons, Inc., 1967. 455 p.

Mela D. F. Letter to the editor - information theory and search theory as special cases of decision theory // Operations Research. 1961. Vol. 9(6). P. 907-909.

Koopman B. O. Search and information theory // Part of final report on stochastic processes in certain naval operations. New York, USA: Columbia University, 1967. P. 126-134.

Barker W. H. Information theory and the optimal detection search // Operations Research. 1977. Vol. 25. N 2. P. 304-314.

Pierce J. G. A new look at the relation between information theory and search theory // The maximum entropy formalism. Cambridge, USA: MIT Press, 1978. P. 339-402.

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-8.

Shannon C. E. A mathematical theory of communication // Bell System Techn. Journal. 1948. Vol. 27. N 4. P. 623-656.

Ahlswede R., Wegener I. Suchprobleme (Eng. Search Problems). Stuttgart, Germany: Teubner Verlag, 1979. 273 p.

Information theory, combinatorics, and search theory: in memory of Rudolf Ahlswede. Eds 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

Stone L. D. Theory of optimal search. New York, USA: Academic Press, 1975. 260 p.

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, N 237). https://doi.org/10.1007/978-3-319-26899-6_1

Koopman B. O. Search and screening. Operations evaluation group report. Alexandria, USA: Center for Naval Analyses. 1946. Vol. 56. 176 p.

Koopman B. O. The theory of search. The optimum distribution of searching effort // Operations Research. 1957. Vol. 5. P. 613-626.

De Guenin J. Optimum distribution of effort: An extension of the Koopman basic theory // Operations Research. 1961. Vol. 9. P. 1-7.

References

Ackoff R. L., Sasieni M. W. Fundamentals of operations research. New York, John Wiley & Sons Inc. Publ., 1967, 455 p.

Mela D. F. Letter to the editor - information theory and search theory as special cases of decision theory. Operations Research, 1961, vol. 9(6), pp. 907-909.

Koopman B. O. Search and information theory. Part of final report on stochastic processes in certain naval operations. New York, Columbia University Press, 1967, pp. 126-134.

Barker W. H. Information theory and the optimal detection search. Operations Research, 1977, vol. 25, no. 2, pp. 304-314.

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.

Jaynes E. T. Entropy and search theory. Maximum-entropy and Bayesian methods in inverse problems. Fundamental theories of Physics. Dordrecht, Springer Publ., 1985, vol. 14, pp. 1-18.

Shannon C. E. A mathematical theory of communication. Bell System Techn. Jornal, 1948, vol. 27, no. 4, pp. 623-656.

Ahlswede R., Wegener I. Suchprobleme [ Search problems ]. Stuttgart, Germany, Teubner Verlag Publ., 1979, 273 p.

Information theory, combinatorics, and search theory: in memory of Rudolf Ahlswede. Vol. 7777 of Lecture Notes in Computer Science. Eds H. Aydinian, F. Cicalese, C. Deppe. Cambrige, Springer Publ., 2013, 773 p. https://doi.org/10.1007/978-3-642-36899-8

Stone L. D. Theory of optimal search. New York, USA, Academic Press, 1975, 260 p.

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, N 237). https://doi.org/10.1007/978-3-319-26899-6_1

Koopman B. O. Search and screening. Operations evaluation group report. Alexandria, Center for Naval Analyses Publ., 1946, vol. 56, 176 p.

Koopman B. O. The theory of search. The optimum distribution of searching effort. Operations Research, 1957, vol. 5, pp. 613-626.

De Guenin J. Optimum distribution of effort: An extension of the Koopman basic theory. Operations Research, 1961, vol. 9, pp. 1-7.