Решение задачи коммивояжера методом ветвей и границ
Введите матрицу расстояний между городами. Пустая ячейка означает, что переезд невозможен,
диагональ считается равной 0. Нажмите "Решить" для полного расчета или "Пошагово",
чтобы увидеть раскрытие ветвей, оценки границ и отсечения.
Маршрут и дерево поиска
Введите матрицу и нажмите "Решить".
Нижняя граница считается как стоимость уже построенного пути плюс минимальные необходимые выходы
из текущего и еще не посещенных городов. Если граница не меньше лучшего найденного тура, ветвь отсекается.
Онлайн сервис решает задачу коммивояжера методом ветвей и границ: по матрице расстояний он ищет минимальный замкнутый маршрут, который проходит через каждый город ровно один раз и возвращается в стартовый город.
Метод ветвей и границ строит дерево частичных маршрутов. Для каждой ветви вычисляется нижняя оценка стоимости: если эта оценка уже не лучше найденного маршрута, ветвь отсекается и не рассматривается дальше. Такой подход позволяет существенно сократить перебор по сравнению с проверкой всех перестановок.
Калькулятор подходит для учебных задач по дискретной математике, исследованию операций, теории графов и оптимизации маршрутов. Пошаговый режим показывает, какая ветвь раскрывается, какие варианты добавляются в очередь, а какие отсекаются по границе.
Комментарии