Теоретические основы решения задач поиска методом максимума энтропии
DOI:
https://doi.org/10.21638/11701/spbu10.2023.304Аннотация
Традиционной задачей теории поиска является разработка плана поиска физического объекта в море или на суше. Известные алгоритмы оптимального распределения поисковых ресурсов используют преимущественно экспоненциальную функцию обнаружения. Если рассматривать задачу поиска шире — как задачу поиска информации различного вида, то функция обнаружения может существенно отличаться от экспоненциальной.
В этом случае решения, полученные с помощью традиционных алгоритмов, могут быть корректными с точки зрения математики, но неприемлемыми с точки зрения логики. В данной работе указанная проблема решается на основе принципа максимума энтропии. Приведено доказательство теорем, а также следствий из них для функций обнаружения четырех видов, позволяющих создать алгоритмы решения различных задач поиска на основе принципа максимума энтропии.
Ключевые слова:
теория информации, теория поиска, равномерно оптимальный поисковый план, функция обнаружения, принцип максимума энтропии
Скачивания
Библиографические ссылки
Акоф Р., Сасиени М. Основы исследования операций / пер. с англ.; под ред. И. А. Ушакова. М.: Мир, 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.
Загрузки
Опубликован
Как цитировать
Выпуск
Раздел
Лицензия
Статьи журнала «Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.
