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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «== Постановка задачи == Задачей коммивояжера (Traveling Salesman Problem, TSP) явл…»)
 
Строка 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) пути. Цель: минимизация значения весовой функции.