Адекватность математических моделей на примере задачи коммивояжера

В статье рассматривается один из возможных подходов к проблеме адекватности математических моделей – на примере входных данных, использующихся при создании и анализе алгоритмов решения задачи коммивояжера для возникающих на практике частных случаев этой проблемы. Авторы считают, что т.н. псевдогеометрическая версия этой проблемы более адекватно описывает множество ее частных случаев, встречающихся в большинстве предметных областей, чем значительно более распространенная геометрическая версия. Это утверждение обусловливается следующими фактами. В ходе разработки алгоритмов (а также в целях оценки их эффективности) для конкретных предметных областей необходимо принимать во внимание, насколько данные, сгенерированные выбранным методом, репрезентативны для исследуемой предметной области. Как правило, тестовые данные задаются набором случайных величин с заданным распределением. При этом используется некая идеализированная модель входных данных, чаще всего – с равномерными или нормальными распределениями значений характеристик. Однако на практике входные данные, как правило, поступают в соответствии с некоторым вероятностным распределением, отличным от равномерного или нормального. В результате производительность алгоритма на реальных данных – причем как в среднем, так и в худшем случае – неадекватна. Самый важный вывод, который хотели бы сделать авторы данной статьи, состоит в следующем. Существуют различные области – как в теоретической информатике, так и в математике, – в которых основные направления исследований, проводимых самыми разными научными группами, в действительности являются мало похожими на реальные задачи, возникающие в различных областях на практике. И «увлечение» многих математиков-программистов последовательным улучшением алгоритмов и программ, предназначенных для решения геометрической версии задачи коммивояжера (вместо псевдогеометрической ее версии), – это один из многих подобных примеров.

математическая модель, адекватность, задача коммивояжера, псевдогеометрическая версия

1. Самарский А., Михайлов А. Математическое моделирование: Идеи. Методы. Примеры. – М.: Физматлит, 2001.

2. Oreskes N., Shrader-Frechette K., Belitz K. Verification, validation, and confirmation of numerical models in the earth sciences // Science. – Vol. 263. – 1994. – P. 641-646.

3. Box G., Draper N. Empirical Model Building and Response Surfaces. – NY: Wiley Series in Probability and Statistics, 1987.

4. Гаспарский В. Праксеологический анализ проектно-конструкторских разработок. – М.: Мир, 1978.

5. Розенберг Г., Шитиков В., Брусиловский П. Экологическое прогнозирование (Функциональные предикторы временных рядов). – Тольятти: Изд-во РАН, 1994.

6. Korostensky C. et al. Near Optimal Multiple Sequence Alignments Using a Travelling Salesman Problem Approach. / String Processing and Information Retrieval Symposium & International Workshop on Groupware. – 1999. – P. 105-114

7. Мельников Б., Панин А. Параллельная реализация мультиэвристического подхода в задаче сравнения генетических последовательностей // Вектор науки Тольяттинского государственного университета. –2012. – № 4. – С. 83-86.

8. Makarkin S., Melnikov B., Panin A. On the metaheuristics approach to the problem of genetic sequence comparison and its parallel implementation // Applied Mathematics. – 2013. – Vol. 4, No. 10A, P. 35-39. doi: 10.4236/ am.2013.410A1006.

9. Melnikov B., Kashlakova E. Some grammatical structures of programming languages as simple bracketed languages // Informatica (Lithuania). – 2000. – V. 11, No. 4. – P. 441-453.

10. Алексеева А., Мельников Б. Итерации конечных и бесконечных языков и недетерминированные конечные автоматы // Вектор науки Тольяттинского государственного университета. – 2011. – № 3. – С. 30-33.

11. Мельников Б. Алгоритм проверки равенства бесконечных итераций конечных языков / Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика. – 1996. – № 4. – С. 49-

12. Korostensky C. et al. Using traveling salesman problem algorithms for evolutionary tree construction // Bioinformatics. – 2000. – Vol. 16. – P. 619-627.

13. Hromkoviи J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. – Springer, 2003.

14. Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию. – СПб.: БХВ- Петербург, 2010.

15. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982. (Garey M., Johnson D. Computers and Intractability: A Guide to the Theory of NP-Completeness. – W. H. Freeman and Company, 1979.)

16. Melnikov B., Radionov A., Gumayunov V. Some special heuristics for discrete optimization problems // Proc. of 8th International Conference on Enterprise Information Systems, ICEIS-2006. – Cyprus. – 2006. – P. 360- 364.

17. Мельников Б., Романов Н. Еще раз об эвристиках для задачи коммивояжера // Теоретические проблемы информатики и ее приложений. – 2001. – Т. 4. – С. 81-92.

18. Melnikov B. Multiheuristic approach to discrete optimization problems // Cybernetics and Systems Analysis. – 2006. – Vol. 42. – No. 3. – P. 335-341.

19. Мельников Б., Пивнева С., Рогова О. Репрезентативность случайно сгенерированных недетерминированных конечных автоматов с точки зрения соответствующих базисных автоматов // Стохастическая оптимизация в информатике. – 2010. – Т. 6. – № 1. – С. 74-82.

20. Балинова В. Статистика в вопросах и ответах: учеб. пособие. – М.: ТК Велби, изд-во Проспект, 2004.

21. Философский энциклопедический словарь; гл. редакция: Л. Ильичев, П. Федосеев, С. Ковалев, В. Панов. – М.: Сов. Энциклопедия, 1983.

22. Gurevich Y., Veanes M., Wallace C. Can abstract state machines be useful in language theory? // Theoretical Computer Science (Developments in Language Theory). – 2007. – V. 376, No. 1-2. – P. 17-29.

23. Люгер Дж. Искусственный интеллект. Стратегии и методы решения сложных проблем. – Вильямс, 2003.

24. Мельников Б., Радионов А. О выборе стратегии в недетерминированных антагонистических играх // Программирование. – 1998. – № 5. – С. 55-62.

25. Макаркин С. Еще об одном подходе к решению псевдогеометрической задачи коммивояжера // Вектор науки Тольяттинского государственного университета. – 2012. – № 4, C. 79-82.

26. Gutin G., Punnen A. (editors). The Traveling Salesman problem. – Kluwer Academic Publishers, 2002.

27. http://arxiv.org/ftp/arxiv/papers/1204/1204.2350.pdf – Liew Sing. Introducing convex layers to the Traveling Salesman Problem / Preprint: arXiv:1204.2348. – 2012. – Режим доступа – свободный. (Access mode – free.)

28. Somhom S., Modares A., Enkawa T. Competition-based neural network for the multiple travelling salesmen problem with minimax objective // Computers & Operations Research. – 1999. – Vol. 26, No. 4. – P. 395-407