Метрическая задача коммивояжера

Постановка задачи

Задачей коммивояжера (Traveling Salesman Problem, TSP) является следующая задача оптимизации:

Дано: полный неориентированный граф без циклов G = (V, E) и весовая функция w: E ! Q >o, присваивающая каждому ребру неотрицательный вес.

Допустимые решения: все гамильтоновы пути, т.е. подграфы H графа G, которые являются связными и каждая вершина которых имеет степень 2.

Целевая функция: весовая функция w(H) = Pe2H w(e) пути. Цель: минимизация значения весовой функции.