Метрическая задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) (Новая страница: «== Постановка задачи == Задачей коммивояжера (Traveling Salesman Problem, TSP) явл…») |
Irina (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
[[задача коммивояжера|Задачей коммивояжера]] (Traveling Salesman Problem, TSP) является следующая задача оптимизации: | [[задача коммивояжера|Задачей коммивояжера]] (Traveling Salesman Problem, TSP) является следующая [[задача оптимизации]]: | ||
Дано: полный неориентированный граф без циклов G = (V, E) и весовая функция w: E ! Q >o, присваивающая каждому ребру неотрицательный вес. | Дано: полный неориентированный граф без циклов G = (V, E) и весовая функция w: E ! Q >o, присваивающая каждому ребру неотрицательный вес. | ||
Допустимые решения: все гамильтоновы пути, т.е. подграфы H графа G, которые являются связными и каждая вершина которых имеет степень 2. | Допустимые решения: все гамильтоновы пути, т.е. подграфы H графа G, которые являются связными и каждая вершина которых имеет степень 2. | ||
Целевая функция: весовая функция w(H) = Pe2H w(e) пути. Цель: минимизация значения весовой функции. | Целевая функция: весовая функция w(H) = Pe2H w(e) пути. Цель: минимизация значения весовой функции. | ||
Версия от 18:40, 20 августа 2016
Постановка задачи
Задачей коммивояжера (Traveling Salesman Problem, TSP) является следующая задача оптимизации:
Дано: полный неориентированный граф без циклов G = (V, E) и весовая функция w: E ! Q >o, присваивающая каждому ребру неотрицательный вес.
Допустимые решения: все гамильтоновы пути, т.е. подграфы H графа G, которые являются связными и каждая вершина которых имеет степень 2.
Целевая функция: весовая функция w(H) = Pe2H w(e) пути. Цель: минимизация значения весовой функции.