Travelling salesman problem by branch and bound online on Intellect

Used 534 times

Решение задачи коммивояжера методом ветвей и границ

Введите матрицу расстояний между городами. Пустая ячейка означает, что переезд невозможен, диагональ считается равной 0. Нажмите "Решить" для полного расчета или "Пошагово", чтобы увидеть раскрытие ветвей, оценки границ и отсечения.

Стартовый город:

Маршрут и дерево поиска

Введите матрицу и нажмите "Решить".

Нижняя граница считается как стоимость уже построенного пути плюс минимальные необходимые выходы из текущего и еще не посещенных городов. Если граница не меньше лучшего найденного тура, ветвь отсекается.

Was this answer useful?

Choose a quick rating so we can improve the next answer for you.

How satisfied are you?

Your answer option for this service or noticed an error:

This online tool solves the travelling salesman problem by the branch and bound method. From a distance matrix it searches for the shortest closed route that visits every city exactly once and returns to the start city.
Branch and bound builds a tree of partial tours. Each branch receives a lower bound estimate; if the bound is already not better than the best complete tour found so far, the branch is pruned. This reduces the search space compared with checking every permutation.
The calculator is useful for discrete mathematics, operations research, graph theory, and route optimisation tasks. Step-by-step mode shows which branch is expanded, which candidates are added to the queue, and which branches are cut off by the bound.

Algorithms Programming