THE ADEQUATE OF MATHEMATICAL MODELS FOR TRAVELLING SALESMAN PROBLEM
Abstract
We consider one of the possible approaches to adequacy of mathematical models by the example of data samples used to design and analysis algorithms to solve reallife instances of travelling salesman problem (TSP). Authors consider so-called pseudo-Euclidian version of that problem to be more adequate description of the real-life examples of TSP, than more common Euclidian TSP. Latter is explained by the following: designing an algorithms (and estimating its effectiveness) for a given object domain one has to consider the representativeness of generated sample data for this domain. Commonly a set if random variables with a given distribution function is used as a sample data using some idealized data model (mostly with uniform distribution of attri-butes values). However in practice the input data has some special distribu-tion of attributes values, different from uniform or Gaussian. As a result the algorithm’s performance on a real-life data is inadequate (both on average and at worst). The most important conclusion made by the authors is the following. There are different object domains (as in theoretical information, so in mathematics), in which mainstream research conducted by different scientific groups has not much in common with the real-life instances of the studied problems. One of such examples is the «enthusiasm» of many mathematicians and pro grammers about the improvement of algorithms for Euclidian TSP (instead of pseudo-Euclidian)
About the Authors
S. Makarkin
Togliatti State University
Russian Federation
Russian Federation
B. Melnikov
Samara State University
Russian Federation
Russian Federation
References
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
Review
For citations:
Makarkin S., Melnikov B. THE ADEQUATE OF MATHEMATICAL MODELS FOR TRAVELLING SALESMAN PROBLEM. Philosophical Problems of IT & Cyberspace (PhilIT&C). 2013;(2):4-17. (In Russ.)
Views:
117
Email this article 