Метод ветвей и границ для задачи коммивояжера
Аннотация
Целью дипломной работы является реализация метода ветвей и границ в задаче коммивояжера и оценка числа исследуемых вершин в дереве решений алгоритма.
Используемые методы: анализ, наблюдение, эксперимент, измерение, сравнение. Исходные данные – случайно сгенерированные матрицы расстояний между вершинами.
В ходе работы был реализован метод ветвей и границ в задаче коммивояжера. На основе случайных матриц расстояний в графе были рассчитаны экспериментальные данные. С помощью метода наименьших квадратов найдена оценка на количество вершин в дереве решений.
Область применения результатов: данный алгоритм находит оптимальное решение для задачи коммивояжера при бо́льших ограничениях, чем это может делать переборный алгоритм. Используется в организации логистики и перевозок, в задаче о дыропробивном прессе, на производстве при организации конвейера, чтобы сократить время простоя и сделать сборку деталей максимально эффективной
Используемые методы: анализ, наблюдение, эксперимент, измерение, сравнение. Исходные данные – случайно сгенерированные матрицы расстояний между вершинами.
В ходе работы был реализован метод ветвей и границ в задаче коммивояжера. На основе случайных матриц расстояний в графе были рассчитаны экспериментальные данные. С помощью метода наименьших квадратов найдена оценка на количество вершин в дереве решений.
Область применения результатов: данный алгоритм находит оптимальное решение для задачи коммивояжера при бо́льших ограничениях, чем это может делать переборный алгоритм. Используется в организации логистики и перевозок, в задаче о дыропробивном прессе, на производстве при организации конвейера, чтобы сократить время простоя и сделать сборку деталей максимально эффективной