4551
правка
Метрическая задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
м
Метрическая задача коммивояжера (посмотреть исходный код)
Версия от 01:19, 24 августа 2016
, 24 августа 2016нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 2: | Строка 2: | ||
[[задача коммивояжера|Задачей коммивояжера]] (Traveling Salesman Problem, TSP) является следующая [[задача оптимизации]]: | [[задача коммивояжера|Задачей коммивояжера]] (Traveling Salesman Problem, TSP) является следующая [[задача оптимизации]]: | ||
Дано: полный неориентированный граф без циклов G = (V, E) и весовая функция w: E | Дано: полный неориентированный граф без циклов G = (V, E) и весовая функция <math>w: E \to \mathbb{Q}_{ \ge 0}</math>, присваивающая каждому ребру неотрицательный вес. | ||
Допустимые решения: все гамильтоновы обходы, т.е. подграфы H графа G, которые являются связными и каждая вершина которых имеет степень 2. | Допустимые решения: все гамильтоновы обходы, т.е. подграфы H графа G, которые являются связными и каждая вершина которых имеет степень 2. | ||