§ 54. Метод прогрессивных разделений и оценок (метод ветвления и ограничения)

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

Рис. 254.

Пусть с помощью свойства множество можно разбить на подмножество А и его дополнение А. Предположим, что мы умеем найти нижнюю границу значений на а также нижние границы значений на соответственно. Рассмотрим свойства также позволяющие разбить на две части. Тогда свойствам соответствуют подмножества соответственно. Таким образом, можно образовать прадерево (рис. 254), которое, вообще говоря, нам не нужно строить полностью. Действуем следующим образом. Допустим, что мы уже построили часть прадерева, использовав к свойств и нашли нижние границы для вершин этой части. Берем тогда одну из висячих вершин с наименьшей границей и с помощью этих свойств и, быть может, нового получаем новые две

вершины, для которых стараемся уточнить нижние границы, и т. д. Заметим, что объединение висячих вершин, получающихся на каждом этапе, дает Например, для прадерева на рис. 255 имеем

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

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

Рис. 255

Этот метод можно назвать «методом оптимизации с помощью решета». Рассматриваются его различные модификации (например, метод динамического программирования). При реализации этого метода существуют выбор свойств и уточнение оценок на каждом этапе. Заметим также, что вместо разбиений на две части можно рассматривать разбиения на частей. Об этом, в частности, см. работу Лоулера и Вуда.

Отыскание оптимальных гамильтоновых контуров графа. Алгоритм Литтла. Эта задача, известная под названием «задача о коммивояжере», долгое время оставатась нерешенной. В 1963 г. Литтл (вместе с другими авторами) дал для этой задачи строгий метод оптимизации; мы рассмотрим его на примере. Название этой задачи происходит из того, что гамильтонов контур можно рассматривать как путь коммивояжера, желающего посетить все города в точности по одному разу и возвратиться обратно.

Опишем алгоритм Литтла для нахождения минимального гамильтонова контура для графа с вершинами. Для иллюстрации рассуждений будем пользоваться полным симметрическим графом на рис. 256, каждой дуге которого приписано значение Эти значения представлены в виде матрицы стоимостей (рис. 257). Символ означает, что между нет дуги. Этот алгоритм сводится к следующим правилам.

А) Находим в каждой строке матрицы минимальный элемент и вычитаем его из всех элементов этой строки Если в получающейся матрице окажутся столбцы, не содержащие

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

Б) Суммируем все элементы, которые мы вычитали в А). Очевидно, что эта сумма является нижней границей множества Е решений, которое берется в качестве корня прадерева (см. стр. 299).

Рис. 256 Здесь пара дуг заменена двойной стрелкой

Рис. 257

В) Выбираем дугу для которой

где сумма наименьшего элемента строки (исключая и наименьшего элемента столбца (исключая , которая вычисляется для

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

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

Г) Вычисляем по формуле (54.1) и прибавляем его к границе, соответствующей вершине прадерева, исходя из которой производится разбиение Эта сумма будет границей для новой вершины, определяемой свойством которую соединяем дугой, идущей в нее из указанной выше вершины.

Д) Аналогично Г) присоединяем к прадереву вершину, определяемую свойством «контур использует дугу ». Удалим из матрицы строку и столбец и заменим на

значения тех дуг, используя которые, получают контуры длины, меньшей

Е) Действуем, как в А), с матрицей, получающейся в результате Д).

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

3) Если в результате Д) получают матрицу порядка 1, то процесс заканчивается. В противном случае переходим к И).

И) Среди висячих вершин уже построенного прадерева выбираем вершину с наименьшей границей (если таковых несколько, выбираем произвольно).

Рис. 258.

К) Если выбранная по И) вершина соответствует свойству то переходим к В). В противном случае переходим к Л),

Л) Значение в клетке матрицы, соответствующей висячей вершине, выбранной в К), заменяем на строке, а также в столбце находим наименьший элемент и вычитаем его из всех элементов этой строки (столбца). Затем переходим к В).

Пример. Опишем построение прадерева на рис. 259, дающего минимальный гамильтонов контур графа на рис. 256, согласно алгоритму, изложенному выше.

A) Из элементов строк матрицы на рис. 257 вычитаем соответственно их наименьшие элементы:

3, 2, 1, 2, 2, 2, 1, а также вычитаем 2 из всех элементов столбца Получаем на рис. 260 матрицу.

Б) Вычисляем сумму: Получаем для на рис. 259 границу, равную 15.

B) Рассмотрим все нулевые элементы матрицы на рис. 260 (воспроизведенной также на рис. 261 — выкладки для вершины 2 прадерева).

Возьмем 0 в клетке Если исключить его, то 2 — наименьший элемент строки а также столбца Имеем Это значение записываем в клетке курсивом, чтобы отличить от Берем затем 0 в клетке Если исключить элемент в этой клетке, то -наименьший элемент в строке в столбце Имеем

(кликните для просмотра скана)

Аналогично Выбираем дугу так как максимально. Это значение записываем полужирным шрифтом в соответствующей клетке.

Г) Изображаем вершину прадерева (рис. 259) и приписываем ей значение

Рис. 262.

Д) Изображаем вершину Исключая строку и столбец в матрице на рис. 261, получаем матрицу на рис. 262. Рассматривая уже выбранные дуги (в нашем случае дугу видим, что надо заменить на со, так как иначе получился бы контур

Рис. 263.

Рис. 264

Е) Рассматривая матрицу на рис. 262, видим, что нужно только вычесть 2 из строки что приводит к матрице на рис. 263 (выкладки для вершины 2 прадерева).

Ж) Сумма элементов, вычтенных из строк и столбцов по Е), здесь равна 2. Следовательно, для вершины имеем границу:

3) Имеем матрицу порядка 6, поэтому переходим к И).

И) Висячая вершина с наименьшим значением, равным 17, есть

К) получалась с помощью Переходим к В).

В) Рассматривая матрицу на рис 264 и вычисляя для нулевых элементов этой матрицы, получаем, что (на рисунке выкладки для вершины 3 прадерева).

Г) Строим вершину которой отвечает граница

Рис. 265.

Д) Строим вершину Вычеркивая строку и столбец матрицы на рис. 264, приходим к матрице на рис. 265, в клетку которой ставим чтобы не получить контура (

Е) Рассматривая матрицу на рис. 265, видим, что из всех элементов столбца нужно только вычесть 1, что приводит к матрице на рис. 266 (выкладки для вершины 3 прадерева).

Рис. 266

Рис. 267.

Ж) Сумма элементов, вычтенных из строк и столбцов по Е), здесь равна 1. Следовательно, для вершины имеем границу

3) Имеем матрицу порядка 5, поэтому переходим к И).

И) Висячая вершина с наименьшим значением, равным 18, есть .

К) получалась с помощью 15. Переходим к В).

В) Рассматривая матрицу на рис. 267 и вычисляя для нулевых элеменюв этой матрицы, получаем, что

Г) Строим вершину которой отвечает граница

Д) Строим вершину Вычеркивая строку и столбец матрицы на рис. 267 (выкладки для вершины 4 прадерева), приходим к матрице на рис. 268, в клетку которой ставим чтобы не получить контура

Рис. 268.

Рис. 269.

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

Рис. 270.

Рис. 271

Ж) Сумма элементов, вычтенных из строк и столбцов по Е), здесь равна 2. Следовательно, для вершины имеем границу

3) Имеем матрицу порядка 4, поэтому переходим к И).

И) Висячая вершина с наименьшим значением, равным 19, есть

К) получалась с помощью 27. Переходим к Л).

Л) В клетку матрицы на рис. 261 ставим что приводит к матрице на рис 270. Затем вычитаем 3 из всех элементов

строки и 1 из всех элементов столбца что приводит к матрице на рис. 271.

В) Рассматривая матрицу на рис. 271 и вычисляя для нулевых элементов этой матрицы, получаем, что (клетки также дают это значение).

Г) Строим вершину которой отвечает граница

Рис. 272.

Д) Строим вершину Вычеркивая строку и столбец матрицы на рис. 271, приходим к матрице на рис. 272, в клетку которой ставим

Е) Рассматривая матрицу на рис. 272, видим, что в каждой ее строке и каждом столбце есть по крайней мере один нулевой элемент.

Рис. 273.

Рис. 274

Ж) Сумма элементов, вычтенных из строк и столбцов по Е), здесь равна 0. Следовательно, для вершины имеем границу

3) Имеем матрицу порядка 6, поэтому переходим к И).

И) Висячая вершина с наименьшим значением, равным 19, есть .

К) получалась с помощью 46. Переходим к В).

В) Рассматривая матрицу на рис. 273 и вычисляя для нулевых элементов этой матрицы, получаем, что дает то же значение).

Г) Строим вершину которой отвечает граница

Д) Строим вершину Вычеркивая строку и столбец 5 в матрице на рис. 273, приходим к матрице на рис. 274, в клетку которой ставим

Е) Рассматривая матрицу на рис. 274, видим, что нужно только вычесть 1 из строки что приводит к матрице на рис. 275.

Рис. 275.

Рис. 276.

Ж) Сумма элементов, вычтенных из строк и столбцов по Е), здесь равна 1 Следовательно, для вершины имеем границу

3) Имеем матрицу порядка 5, поэтому переходим к И).

И) Висячие вершины с наименьшим значением, равным 20, — это Произвольно выбираем последнюю.

К) получилась с помощью Переходим к В).

В) Рассматривая матрицу на рис. 269 (воспроизведенную на рис 276 — выкладки для вершины 7 прадерева) и вычисляя для нулевых элементов этой матрицы, получаем, что

Г) Строим вершину которой отвечает граница

Д) Строим вершину Вычеркивая строку и столбец 3 матрицы на рис. 276, приходим к матрице на рис. 277, в клетку которой ставим чтобы не получить контура

Е) Рассматривая матрицу на рис. 278, видим, что ее элементы либо 0, либо

Ж) Сумма элементов, вычтенных из строк и столбцов по Е), здесь равна 0. Следовательно, для вершины имеем границу

3) Имеем матрицу порядка 3, поэтому переходим к И).

И) Висячие вершины с наименьшим значением, равным это Выбираем последнюю.

К) получалась с помощью 73. Переходим к В).

Рис. 277

Рис. 278

В) Очевидно, что для матрицы на рис. 278 все равны 0. Произвольно выбираем клетку

Г) Строим вершину которой отвечает граница

Д) Строим вершину

Вычеркивая строку и столбец в матрице на рис. 278, приходим к матрице на рис 279, в клетку которой ставим

Рис. 279

Рис. 280

Е) Рассматривая матрицу на рис. 279, видим, что ее элементы либо 0, либо

Ж) Сумма элементов, вычтенных из строк и столбцов по Е), здесь равна 0. Следовательно, для вершины имеем границу

3) Имеем матрицу порядка 2, поэтому переходим к И).

И) Выбираем вершину с наименьшим значением, равным 20.

К) Вершина, выбранная в И), строилась с помощью Переходим

В) Очевидно, что для матрицы на рис. 280 все значения равны (что означает, что мы больше не можем использовать свойств исходя из рассматриваемой вершины).

Рис. 281

Рис. 282

Выбираем клетку .

Г) Строим вершину которой отвечает граница

Рис. 283.

Рис. 284.

Д) Строим вершину Вычеркивая строку и столбец переходим к матрице на рис. 281. Очевидно, что символ ставить не нужно.

Е) Очевидно, что в матрице на рис. 281 ничего вычитать не требуется.

Ж) Очевидно, что для вершины в Д) нижняя граница

3) Имеем матрицу порядка 1. Процесс закончен. Для последних двух вершин прадерева имеем нижние границы соответственно и 20.

Добавляя дугу получаем искомый гамильтонов контур со значением 20, так как объединение висячих вершин построенного прадерева дает

Найденное решение представлено на рис. 282—284. Это решение не единственно, что получается из-за того, что при построении прадерева выбор вершин в некоторых случаях не однозначен.

Рис. 285.

Одно из других решений представлено на рис. 285—287.

Замечания. При применении алгоритма Литтла в случае произвольного графа следует приписать символ всем парам вершин для которых в графе нет дуги Если задача не имеет решения, то мы более или менее быстро придем к прадереву, все висячие вершины которого имеют нижнюю границу Поэтому предпочтительнее узнать заранее, существует ли решение (об этом см. стр. 335 и §§ 61,62).

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

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

Рис. 286

Рис. 287

Припишем символ всем парам вершин для которых в графе нет дуги Пусть

где матрица стоимостей графа с вершинами.

Тогда построим матрицу, элементы которой определяются гак:

и применим к ней алгоритм Литтла. Полученное минимальное решение дает нам максимальное для матрицы Заметим, что минимальное значение с и максимальное с в сумме дают

Пример. Найдем гамильтонов контур с максимальным значением графа с матрицей стоимостей на рис. 288.

Имеем

Матрица с элементами

изображена на рис. 289.

Рис. 288

Рис. 289.

Читателю предоставляется возможность провести выкладки, приводящие к построению прадерева на рис. 290 (см. рис. результате получаем гамильтонов контур с минимальным значением 19 для матрицы на рис. 289. Он является гамильтоновым контуром с максимальным значением для матрицы на рис. 288 и представлен на рис. 301—303.

Задача о назначениях. Пусть имеется работников должностей Каждому назначению сопоставим число

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

(кликните для просмотра скана)

(кликните для просмотра скана)

Для решения этой задачи можно применить алгоритм Литтла, не используя в пункте Д) символа который не позволял получать контуры длины меньшей и отождествляя

Для графа с матрицей стоимостей на рис. 304 процесс вычислений по этому алгоритму иллюстрируют рис. 305—330. На рис. 331 приведено другое решение.

Нахождение минимального гамильтонова пути. Для нахождения минимального гамильтонова пути с фиксированным началом следует видоизменить матрицу

1) поставить символ на главную диагональ;

2) в столбце все элементы, кроме заменить нулями и действовать по алгоритму Литтла.

Рис. 304.

Для нахождения минимального гамильтонова пути с нефиксированным началом следует ввести новую вершину соединяя ее с каждой вершиной дугами и с нулевыми значениями, и найти минимальный гамильтонов контур нового графа. Исключая затем из него получают искомый путь.

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

Пример. Вновь рассмотрим матрицу на рис. 257 и найдем минимальный гамильтонов путь с началом в Процесс вычислений иллюстрируют рис. 332—350. (Рис. 333 получается из матрицы на рис. 332, если положить .

Этим путем будет

Нахождение максимального гамильтонова пути. Оно сводится к задаче отыскания максимального гамильтонова контура.

Если начало пути не фиксируется, то достаточно ввести новую вершину 5 и соединить ее с вершинами которые могут быть взяты в качестве начала, дугой со значением 0 и с вершинами которые могут быть взяты в качестве конца, дугой со значением 0, а с остальными вершинами — дугами и со значением

(кликните для просмотра скана)

(кликните для просмотра скана)

(кликните для просмотра скана)

(кликните для просмотра скана)

(кликните для просмотра скана)

(кликните для просмотра скана)

(кликните для просмотра скана)

УПРАЖНЕНИЯ

(см. скан)

(см. скан)