Библиографическое описание:РЕШЕНИЕ ЗАДАЧИ КОММИВОЯЖЕРА ДВУМЯ РАЗЛИЧНЫМИ СПОСОБАМИ: "ВЕНГЕРСКИЙ МЕТОД" И "МЕТОД ВЕТВЕЙ И ГРАНИЦ" : научное издание / Р. А. Каримов. - Текст : непосредственный // Международный студенческий научный вестник. - 2019. - № 1. - С. 41-41. - ISSN 2409-529X. Перевод заглавия: SOLUTION OF THE TRAVELING SALESMAN PROBLEM IN TWO DIFFERENT WAYS: "THE HUNGARIAN METHOD" AND "THE METHOD OF BRANCHES AND BORDERS"
Аннотация:Задача коммивояжера, проблема оптимизации в теории графов, в которой узлы (города) графа соединены направленными ребрами (маршрутами), где вес края указывает расстояние между двумя городами. Проблема состоит в том, чтобы найти путь, который посещает каждый город один раз, возвращается в начальный город и минимизирует пройденное расстояние. Единственный известный алгоритм общего решения, гарантирующий кратчайший путь, требует времени решения, которое растет экспоненциально с размером задачи (т. Е. Количеством городов). Это пример NP-полной проблемы (из неполиномиальной), для которой не существует известного эффективного алгоритма (то есть полиномиального времени). Изучение этой проблемы привлекло многих исследователей из разных областей, например, математики, исследования операций, физики, биологии или искусственного интеллекта. Это связано с тем, что TSP демонстрирует все аспекты комбинаторной оптимизации и служит и продолжает служить в качестве ориентира для новых алгоритмических идей, таких как моделируемый отжиг, поиск с запретами, нейронные сети и эволюционные методы. Теоретические исследования, связанные с вопросами сложности задач дискретной оптимизации, а также с построением и анализом эффективных приближенных алгоритмов решения этих задач, находятся в русле современных, интенсивно развивающихся областей математики. Терминология, возникающая в ходе этих исследований, широко распространена в современной научной литературе и требует определенного с ней знакомства.
The traveling salesman problem, the optimization problem in graph theory, in which the nodes (cities) of a graph are connected by directed edges (routes), where the edge weight indicates the distance between two cities. The problem is to find a way that each city visits once, returns to the starting city and minimizes the distance traveled. The only known general solution algorithm that guarantees the shortest path requires solution time, which grows exponentially with the size of the problem (i.e., the number of cities). This is an example of an NP-complete problem (from non-polynomial) for which there is no well-known efficient algorithm (that is, polynomial time). The study of this problem attracted many researchers from various fields, such as mathematics, operations research, physics, biology, or artificial intelligence. This is due to the fact that TSP demonstrates all aspects of combinatorial optimization and serves and continues to serve as a guideline for new algorithmic ideas, such as simulated annealing, banshooting, neural networks and evolutionary methods. Theoretical studies related to the complexity of discrete optimization problems, as well as the construction and analysis of effective approximate algorithms for solving these problems, are in line with modern, rapidly developing areas of mathematics. The terminology arising in the course of these studies is widespread in modern scientific literature and requires some familiarity with it.
