Тема: УСОВЕРШЕНСТВОВАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА ПО МЕТОДУ ВЕТВЕЙ И ГРАНИЦ

Как известно, задача коммивояжёра является NP-трудной задачей поэтому точные алгоритмы её решения не могут иметь временную сложность меньше экспоненциальной. Решением ЗК является гамильтонов цикл полного взвешенного графа, сумма длин рёбер в котором минимальна. Такой граф обычно задается матрицей неотрицательных расстояний (длин рёбер графа для каждой пары вершин) размером п X п, в которой диагональные элементы полагаются равными очень большой величине, теоретически бесконечности. В самом общем случае матрица асимметрична, а для её элементов не выполнятся неравенство треугольника.
Одним из известных ранних алгоритмов точного решения задачи коммивояжера для общего случая является алгоритм Литтла [1, 2],
основанный на методе ветвей и границ, который строит дерево решений для перебора вариантов маршрута (циклов обхода) с отсечением. Отсекаются такие частично построенные маршруты, у которых оценка снизу длины маршрута больше или равна длине ранее построенного полного наилучшего маршрута. При построении оценки снизу на каждом этапе работы алгоритма матрица расстояний подвергается такому преобразованию с трудоемкостью О(п2), чтобы в каждой её строке и каждом столбце появился хотя бы один нуль.
Целью данной работы является изучение и реализация алгоритма Литтла, который гарантирует оптимальность, и является общим, т. е. не узкоспециализированным для конкретной численной задачи. Так как при построении дерева решений нам на каждом шаге будет требоваться выбирать очередное ребро для включения, мы рассмотрим несколько вариантов как выбрать ребро для ветвления, при помощи вычислительного эксперимента будет выяснено как способ выбора более предпочтительный. Также будет рассмотрена модификация алгоритма, для получения новой оценки нижней границы, что позволит отсекать бесперспективные ветки дерева решений гораздо раньше. В упомянутом вычислительном эксперименте, помимо времени работы алгоритма будет рассчитано количество построенных узлов, что также поможет оценить работу алгоритма.
Купить

Как показал вычислительный эксперимент, выбор ребра для ветвления на очередном шаге лучше осуществлять при помощи коэффициента 6(1,р). При выборе ребра с использованием исходной матрицы, мы не тратим время на вычисление этого коэффициента, но при этом строим значительно больше узлов в дереве решений, что сильно отражается на времени работы алгоритма.
Так же было выявлено, что предложенная модификация алгоритма Литтла для случайной матрицы расстояний позволяет существенно сократить количество обрабатываемых узлов дерева решений при поиске оптимального маршрута в задаче коммивояжёра. При этом время обработки каждого узла имеет тот же порядок трудоёмкости, 0(п2), но с увеличенным в 1,5 — 2 раза множителем. В целом, трудоёмкость обоих алгоритмов имеет порядок 0(п2 * сп), но у модифицированного алгоритма константа с существенно меньше, что позволяет при примерно одинаковом времени решать задачу для п = 100 против п = 60.
Купить