billycalc

Нижняя оценка задачи коммивояжёра

Нижняя оценка задачи коммивояжёра: онлайн-инструмент для точных расчётов.

Нижняя оценка задачи коммивояжёра

Вес минимального остовного дерева W(MST)
Длина найденного тура (эвристика), 0 — нет
Нижняя граница длины оптимального тура
100
OPT ≥ W(MST): без одного ребра тур превращается в остовный путь, а он не легче минимального остовного дерева (веса неотрицательны)При неравенстве треугольника обход дерева даёт тур ≤ 2·W(MST), алгоритм Кристофидеса — ≤ 1.5·OPT; более точная нижняя граница — 1-деревья Хелда — КарпаКоммивояжёр.
Верхняя граница (обход дерева, при неравенстве треугольника)
200
Найденный тур хуже оптимального не более чем на
30%

Подробнее: Нижняя оценка задачи коммивояжёра

Что считает калькулятор

Калькулятор «Нижняя оценка задачи коммивояжёра» рассчитывает Нижняя граница длины оптимального тура на основе 2 параметров: вес минимального остовного дерева w(mst), длина найденного тура (эвристика), 0 — нет.

Стандартные IT-расчёты для разработчиков и сисадминов.

Пример расчёта

При параметрах Вес минимального остовного дерева W(MST) = 100, Длина найденного тура (эвристика), 0 — нет = 130 результат составит 100 (OPT ≥ W(MST): без одного ребра тур превращается в остовный путь, а он не легче минимального остовного дерева (веса неотрицательны)).

Как пользоваться

  1. Введите вес минимального остовного дерева w(mst) и длина найденного тура (эвристика), 0 — нет — все поля выше можно менять слайдером.
  2. Нижняя граница длины оптимального тура рассчитывается автоматически по мере ввода.
  3. Смотрите пример ниже — формула применена к реальным числам.
  4. Скопируйте результат или сохраните страницу в закладки.

Связанные расчёты

Частые вопросы

Как рассчитывается «Нижняя оценка задачи коммивояжёра»?
Калькулятор «Нижняя оценка задачи коммивояжёра» вычисляет Нижняя граница длины оптимального тура по параметрам: вес минимального остовного дерева w(mst), длина найденного тура (эвристика), 0 — нет. Введите значения выше — точная формула применяется мгновенно, ниже показан пример с реальными числами.
Калькулятор «Нижняя оценка задачи коммивояжёра» бесплатный?
Да. Полностью бесплатно, без регистрации, всё считается прямо в браузере и никакие данные не отправляются на сервер.