Названия:
РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЁРА
Автор:
Аннабаева Назик Рахманбердиевна
Расположение страниц:
43-48
Язык:
Русский
Аннотация:
Настоящая работа посвящена задаче коммивояжёра (Travelling Salesperson Problem, TSP) — одной из ключевых проблем теории графов и комбинаторной оптимизации. Мы детально рассматриваем её вычислительную сложность, относящую TSP к классу NP-полных задач, что исключает возможность гарантированного нахождения точного решения для больших графов за разумное (полиномиальное) время. В статье представлен обзор двух основных групп алгоритмов: точных методов (например, динамическое программирование, метод ветвей и границ), применяемых для небольших систем, и приближенных эвристических подходов (таких как генетические и муравьиные алгоритмы), которые незаменимы для решения крупномасштабных логистических задач. Акцент сделан на балансе между качеством полученного маршрута и вычислительной эффективностью.