Page 50 - 4386
P. 50
ребру v співставлена певна довжина с(v). Задача комівояжера
зводиться до знаходження в одержаному графі із заданими
довжинами ребер циклу Гамільтона C мінімальної довжини.
Існує ряд алгоритмів, що дозволяють знаходити
найкоротший шлях від вершини v до вершини w, таких як
алгоритми Дейкстри, Флойда-Уоршола та інші. Але ефективних
алгоритмів, для пошуку циклу Гамільтона мінімальної довжини
немає. Через їхню відсутність, щораз дану практичну задачу
доводиться вирішувати методом прямого перебору.
49
