Задача коммивояжера. Метод ветвей и границ

↑

⇐ ПредыдущаяСтр 2 из 28Следующая ⇒

Постановка задачи. Бродячий торговец должен посетить п горо­дов и вернуться в исходный. Маршрут должен проходить через ка­ждый город, причем один и только один раз. Расстояния (транспорт­ные издержки, время на переезд и т.д.) между городами известны — . Требуется отыскать самый короткий маршрут.

Математическая модель:

 (1)

        (2)

          (3)

 — некоторый маршрут, L(x) — суммарные из­держки; (2) означает, что из каждого города торговец выезжает только раз; (3) означает, что в каждый город он въезжает один раз.

Суть метода

Для каждого подмножества маршрутов может быть подсчитана эффективная нижняя граница по следующему способу.

Например, пусть задана матрица транспортных издержек

Для нахождения оценки начального участка {1,2} — {1,2} строим под­матрицу матрицы С вычеркивая в ней первую строку и второй столбец. У полученной подматрицы  находим минимальные элементы у строк. Отнимаем их от элементов соответствующих строк и получаем подматрицу . Находим у нее минимальные элементы у столбцов. В качестве оценки  берется сумма минимальных элементов строк подматрицы  и столбцов  и длины начального участка

{1,2}=(7+8+5+4+0+7+0+4)+8=43

Для нахождения оценки для участка {1,5,3} у матрицы С вычеркиваются строки 1 и 5 и столбцы 5 и 3.

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

Для вычисления рекорда итерации выбираются один либо несколько маршрутов. Вычисляются их длины. Рекордом r будет длина самого короткого из них. Соответствующий маршрут будет рекордным. На итерациях рекорд может быть улучшен.

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

Познавательные статьи:



Техника нижней прямой подачи мяча

Комплекс физических упражнений для развития мышц плечевого пояса

Стандарт Порядок надевания противочумного костюма

Общеразвивающие упражнения без предметов