Метрическая задача коммивояжера
Перейти к навигации
Перейти к поиску
Постановка задачи
Задачей коммивояжера (Traveling Salesman Problem, TSP) является следующая задача оптимизации:
Дано: полный неориентированный граф без циклов G = (V, E) и весовая функция w: E ! Q >o, присваивающая каждому ребру неотрицательный вес.
Допустимые решения: все гамильтоновы пути, т.е. подграфы H графа G, которые являются связными и каждая вершина которых имеет степень 2.
Целевая функция: весовая функция w(H) = Pe2H w(e) пути. Цель: минимизация значения весовой функции.