Аппроксимационные алгоритмы для задачи TSP | Решение задачи коммивояжёра

В этом видео рассматривается задача коммивояжера и объясняются два приближенных алгоритма для нахождения решения за полиномиальное время. Первый метод — это 2-приближение, использующее минимальное остовное дерево (MST) и поиск в глубину (DFS). Второй метод — это алгоритм Кристофидеса, который сочетает в себе идеальное паросочетание с минимальным остовным деревом. Задача коммивояжера — это классическая NP-трудная задача. Рекомендую сначала посмотреть следующие видео о MST и DFS, на которые я ссылаюсь в этом видео: ► Алгоритм Крускала:    • Kruskals Algorithm for Minimum Spanning Trees   ► Алгоритм Прима:    • Prims Algorithm for Minimum Spanning Trees   ► Поиск в глубину:    • Depth-First Search Algorithm DFS   Некоторые другие мои видео по теме графов: ► Введение в алгоритм Дейкстры:    • Dijkstras Algorithm for Single-Source Shor...   ► Алгоритм Дейкстры на ориентированном графе:    • Dijkstras Algorithm Directed Graph Example   ► Алгоритм Беллмана-Форда:    • Bellman-Ford Single-Source Shortest-Path a...   ► Пример алгоритма Беллмана-Форда:    • Bellman Ford Algorithm Example   ► Алгоритм Флойда-Уоршалла    • Floyd Warshall Graph Traversal Algorithm: ...   ► Флойд-Уоршалл на неориентированном графе    • Floyd Warshall Algorithm on Undirected Gra...   ► Поиск в ширину    • Breadth First Search - BFS algorithm