Решить самостоятельно:

Задание 1.

25 25 10 10

10 2 8 3 4

10 9 5 2 3

15 4 9 6 4

Задание 2.

20 25 35 35

10 4 6 7 3

35 2 8 8 2

30 7 9 6 4

Задание 3.

20 20 20 20

30 3 7 9 7

30 6 7 4 5

20 4 8 5 8

Задание 4.

10 15 40 25

35 7 8 5 8

40 2 4 3 7

20 4 5 3 5

Задание 5.

15 40 30 25

20 2 7 3 4

35 5 4 7 8

35 6 7 3 2

Задача о коммивояжере

Метод ветвей и границ ("поиск с возвратом", "backtracking") для решения задачи о коммивояжере – один из наиболее эффективных и быстрых методов решения задачи о коммивояжере, был разработан Литтлом, Мерти, Суини, Кэрелом [1] в 1963 г. Представляет собой итеративную схему неявного (улучшенного) перебора, который состоит в отбрасывании заведомо неоптимальных решений и является одной из самых эффективных процедур в группе методов ветвей и границ.

Идея метода. Пусть S(0) – множество всех допустимых замкнутых маршрутов (циклов) задачи о коммивояжере с n городами и матрицей затрат переходов C={c_ij}, i=1,..,n, j=1,...,n. Множество S(0) состоит из (n-1)! допустимых решений. Метод Литтла основан на разбиении множества S(0) на два непересекающихся подмножества и на вычислении оценок каждого из них. Далее подмножество с минимальной оценкой (стоимостью) разбивается на два подмножества и вычисляются их оценки. На каждом шаге выбирается подмножество с наименьшей из всех полученных на этом шаге оценок и производится его разбиение на два подмножества. В конце концов получаем подмножество, содержащее один цикл (замкнутый маршрут, удовлетворяющий наложенным ограничениям), стоимость которого минимальна.

Алгоритм метода.

Метод состоит из предварительного этапа и общего, который повторяется необходимое число раз.

Предварительный этап. Приведение матрицы затрат {c_ij}, вычисление нижней оценки стоимости маршрута r.

Вычисление наименьшего элемента по каждой строке (константы приведения):

α_j = min c_ij, i = 1,..,n

j

Переход к новой матрице с элементами:

c`_ij = c_ij - α_j

Вычисление наименьшего элемента по каждому столбцу (константы приведения):

β_j min c_ij, j = 1,..,n

j

Переход к новой матрице с элементами:

c⁰_ij = c`_ij - β_j

Вычисление нижней оценки стоимости маршрута (сумма констант приведения):

В результате выполнения предварительного этапа получаем матрицу {c⁰_ij} в каждой строке и в каждом столбце которой есть хотя бы один нулевой элемент.

Общий этап.

1. Вычисление штрафа “за неиспользование” p_hk для каждого нулевого элемента приведенной матрицы {c⁰_ij}.

Если ребро (h,k) не включается в маршрут, то в него входит некоторый элемент строки h и столбца k. Следовательно, стоимость «неиспользования» (h,k) во всяком случае, не меньше суммы минимальных элементов строки h и столбца k, исключая сам элемент {c⁰_ij}. Отсюда

p_hk = min{c⁰_hj} + min{c⁰_ik}

^{j≠k j≠h}

2 . Выбор нулевого элемента, которому соответствует максимальный штраф. Если таких элементов несколько, то выбирается любой из них. Разбиение множества всех допустимых маршрутов S(0) на два подмножества: подмножество содержащее ребро (h,k) – S(h,k); подмножество, не содержащее ребро (h,k) – S(h,k).

Примечание: максимальный штраф означает, что исключение из решения переезда, соответствующего нулевому элементу, приведет к максимальному увеличению стоимости оптимального маршрута.

3. Вычисление оценок затрат по всем маршрутам, входящим в каждое подмножество.

3 .1. Обозначим за θ(h,k) минимальную оценку стоимости маршрутов, вошедших в множество θ(h,k), т. е. не содержащих ребро (h,k). Для S(h,k) оценка затрат:

θ (h,k) = r + p_hk

3.2. При вычислении оценки затрат для S(h,k) учитывают, что, если ребро (h,k) входит в маршрут, то ребро (k,h) не может входить в маршрут, поэтому принимаем: c⁰_kh = ∞; если в маршрут включено ребро (h,k), то ни одно другое ребро, начинающееся в пункте h или заканчивающееся в пункте k не может входить в маршрут, поэтому строка h и столбец k вычеркиваются. Полученная матрица приводится, т.е. выполняется предварительный этап алгоритма. Пусть сумма приводящих констант матрицы: r_hk. Тогда оценка затрат:

θ(h,k) = r + r_hk

4 . Из множеств S(h,k) и S(h,k) для дальнейшего ветвления выбирается множество, имеющее меньшую оценку. При выборе S(h,k) нужно вернуться к шагу 1, используя на этом шаге приведенную матрицу, полученную на шаге 3.2. При выборе S(h,k) нужно вернуться к матрице {c`_ij}, принять c⁰_hk = ∞ и привести полученную в результате матрицу, после чего перейти к шагу 2, используя на нем эту приведенную матрицу. Если несколько множеств имеют равную минимальную оценку, то дальнейшее ветвление производится для всех множеств с минимальной оценкой. Таким образом, метод ветвей и границ позволяет находить все оптимальные решения.

Алгоритм продолжается до тех пор, пока в подмножестве маршрутов с наименьшей оценкой не останется всего один маршрут. В расчетах это соответствует ситуации, когда исследуемая матрица имеет размерность 1˟1.

Пример:

Рассмотрим пример решения задачи о коммивояжере методом ветвей и границ. В табл. 1 приведена матрица затрат С размерностью 5 ˟ 5. Элементы матрицы С, стоящие на главной диагонали, равны: c_ii = ∞, так как переезд из i-го города в i-ый невозможен.

На предварительном этапе выполняют приведение матрицы затрат, для чего вычисляют константы приведения α_i по строкам (табл. 2).

Затем переходят к новой матрице затрат с элементами c`_ii, которые получены в результате вычитания из всех элементов исходной матрицы c_ij констант приведения α_i (табл. 3). Далее вычисляются константы приведения β_j по столбцам (табл. 3).

Выполняют переход к новой матрице затрат с элементами c⁰_ij, полученными путем вычитания из элементов матрицы c⁰_ij (табл. 3) констант приведения β_j. Результирующая матрица затрат C⁰ приведена (табл. 4), т.е. в каждой строке и в каждом столбце есть хотя бы один нулевой элемент. Нижняя оценка стоимости маршрута равная сумме констант приведения по строкам и столбцам составляет: r=45. Оценка множества всех допустимых маршрутов S(0) также равна: θ(0)=r=45. Следует обратить внимание на то, что из нулевых элементов матрицы затрат {c⁰_ij} невозможно составить полный замкнутый цикл, следовательно оптимальный маршрут будет иметь большую стоимость по сравнению с полученной оценкой: r=45.

Таблица 1 1 2 3 4 5 1 ∞ 14 9 16 7 2 20 ∞ 9 19 14 3 18 15 ∞ 12 12 4 23 10 13 ∞ 17 5 7 6 6 6 ∞	Таблица 2 1 2 3 4 5 αi 1 ∞ 14 9 16 7 7 2 20 ∞ 9 19 14 9 3 18 15 ∞ 12 12 12 4 23 10 13 ∞ 17 10 5 7 6 6 6 ∞ 6
Таблица 3 1 2 3 4 5 1 ∞ 7 2 9 0 2 11 ∞ 0 10 5 3 6 3 ∞ 0 0 4 13 0 3 ∞ 7 5 1 0 0 0 ∞ βj 1 0 0 0 0	Таблица 4 1 2 3 4 5 1 ∞ 7 2 9 02 2 10 ∞ 05 10 5 3 5 3 ∞ 00 00 4 12 03 3 ∞ 7 5 05 00 00 00 ∞

На первом шаге общего этапа вычисляют штраф “за неиспользование” p_hk для каждого нулевого элемента приведенной матрицы {c^”_ij} (табл. 4). Штраф “за неиспользование” p_hk равен сумме минимальных элементов по строке и столбцу, на пересечении которых находится нулевой элемент. Все штрафы указаны непосредственно в соответствующих клетках табл. 4.

Рис. 1. Дерево решения для задачи о коммивояжере

Н а втором шаге выбирают нулевой элемент, которому соответствует максимальный штраф – например, элемент (5,1) и разбивается множество всех допустимых маршрутов S(0) на два подмножества: S(5,1) – подмножество содержащее ребро (5,1); S(5,1) – подмножество, не содержащее ребро (5,1). Процесс решения наглядно иллюстрирует дерево решений (рис. 1). 

Н а третьем шаге вычисляют оценки затрат по всем маршрутам, входящим в каждое подмножество. Для S(5,1) оценка затрат:

Θ (5,1) =r +p₅₁ =45 + 5 = 50

Д ля вычисления оценки затрат для S(5,1) принимают: c`₁₅ = ∞ и вычеркивают строку 5 и столбец 1, т.е. полагают, что c_5j = ∞, при j=2,5; c_i1 = ∞, i=1,4 (табл. 5). Полученную таким образом матрицу (табл. 6) приводят и переходят к новой матрице (табл. 7). Затем вычисляют сумму констант приведения: r₅₁= 2 и оценку затрат подмножества S(5,1): Θ(5,1) =r +p₅₁ =45 + 2 = 47.

Таблица 5 2 3 4 5 αi 1 7 2 9 ∞ 2 2 ∞ 0 10 5 0 3 3 ∞ 0 0 0 4 0 3 ∞ 7 0

Таблица 6 1 2 3 4 5 1 ∞ 7 2 9 ∞ 2 10 ∞ 05 10 5 3 5 3 ∞ 00 00 4 12 03 3 ∞ 7 5 05 00 00 00 ∞

Н а четвертом шаге из множеств S(5,1) и S(5,1) для дальнейшего ветвления выбирается множество S(5,1), имеющее меньшую оценку. Далее итерационно выполняются шаги 1-4 общего этапа. В табл. 8 приведены штрафы “за неиспользование” нулевых элементов. Максимальный штраф соответствует элементу (3,4), поэтому множество S(5,1) разбивается на два подмножества: S(3,4) и S(3,4) (рис. 3.4). Для S(3,4) оценка затрат: θ(3,4) =47 +p₃₄ =47 + 7 = 54. Для вычисления оценки затрат для S(3,4) принимают: c”₄₃ = ∞, вычеркивают строку 3 и столбец 4.

Полученную матрицу (табл. 8) приводят и переходят к новой матрице (табл. 9). Затем вычисляют сумму констант приведения: r₃₄ = 5 и оценку затрат подмножества S(3,4): θ(3,4) =47 + 5 = 52.

И з множеств S(3,4), S(3,4), S(5,1) для дальнейшего разбиения выбирают множество S(5,1), так как его оценка минимальна на этом этапе решения задачи и составляет: θ(5,1)=50. Следовательно, необходимо согласно алгоритму вернуться к матрице табл. 4, принять c`₅₁ = ∞ и привести полученную в результате матрицу (табл. 9).

Таблица 7 2 3 4 5 1 5 0 7 ∞ 2 ∞ 0 10 5 3 3 ∞ 0 0 4 0 3 ∞ 7	Таблица 8 2 3 4 5 1 5 05 7 ∞ 2 ∞ 05 10 5 3 3 ∞ 07 05 4 06 ∞ ∞ 7
Таблица 9 2 3 5 1 5 0 ∞ 2 ∞ 0 5 4 0 ∞ 7 βj 0 0 5

После чего переходят к шагу 1 алгоритма и вычисляют штрафы “за неиспользование” нулевых элементов приведенной матрицы (табл. 11).

Д ля дальнейшего ветвления выбирается элемент (3,1). Оценка затрат множества S(3,1) составляет: θ(3,1) = 55. Для вычисления оценки затрат для S(3,1) принимают: c”₁₃=∞, вычеркивают строку 3 и столбец 1 (табл. 12). Полученная матрица уже приведена. Оценка затрат множества S(3,1) равна: θ(3,1) = 50. Для дальнейшего разбиения выбирается множество S(3,1).

Таблица 10 1 2 3 4 5 1 ∞ 7 2 9 0 2 10 ∞ 0 10 5 3 5 3 ∞ 0 0 4 12 0 3 ∞ 7 5 ∞ 0 0 0 ∞ βj 5 0 0 0 0	Таблица 11 1 2 3 4 5 1 ∞ 7 2 9 02 2 5 ∞ 05 10 5 3 05 3 ∞ 00 00 4 7 03 3 ∞ 7 5 ∞ 00 00 00 ∞
Таблица 12 1 2 3 4 5 1 ∞ 7 2 9 0 2 10 ∞ 0 10 5 3 5 3 ∞ 0 0 4 12 0 3 ∞ 7 5 ∞ 0 0 0 ∞	Таблица 13 2 3 4 5 1 7 2 9 012 2 ∞ 05 10 5 4 03 3 ∞ 7 5 00 ∞ 09 ∞

Н а следующей итерации ветвление выполняется относительно элемента (1,5) (табл. 13,). Оценка затрат множества S(1,5) составляет: θ(1,5) = 50 + p15 = 62. Для вычисления оценки затрат для S(1,5) принимают: c”₅₃ = ∞, чтобы избежать неполного замкнутого цикла 3→1→5→3, вычеркивают строку 1 и столбец 5. Полученная матрица уже приведена. Оценка затрат множества S(1,5) равна: θ(1,5) = 50.

Д алее выполняется разбиение множества S(1,5) на два подмножества: S(2,3) и S(2,3) (табл12).

Н а последней итерации множество S(2,3) разбивается на два подмножества: S(4,2) и S(4,2) (табл. 13).

Результат решения задачи в терминах модели задачи может быть представлен в виде матрицы переездов вида:

В терминах исходной задачи в виде маршрута: 1→5→4→2→3→1. Стоимость маршрута равна 50.