Дерево поиска частичных решений

Прохождение в глубину, которое используется для поиска с возвращением, показано стрелками.

В методе ветвей и границ стоимость должна быть четко определена для частичных решений; кроме того, для всех частичных решений (а₁, а₂, … , ) и для всех расширений (а₁, а₂, …, ).

Должно выполняться следующее соотношение для стоимостей

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

Функция стоимости неотрицательная и даже удовлетворяет более сильному требованию:

,

где , для всех a_k .

В более конкретизированном виде метод ветвей и границ выглядит следующим образом.

Пусть Х – множество вариантов решения некоторой задачи. Если эти варианты пронумеровать от 1 до п, то под множеством Х можно понимать множество номеров вариантов решения, т.е.

Пусть множество - множество параметров, характеризующих решение каждого варианта, Тогда оптимальным решением будет значение

,

являющееся минимальным значением из множества значений , т.е. являющееся точной нижней границей этого множества.

Под оценкой снизу для множества Х понимают значение , которое удовлетворяет соотношению

или .

Если выполняется , то оценку называют достижимой.

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

Пусть можно получить оценку снизу как для множества Х , так и для его подмножеств. Разобьем множество Х на два подмножества А и В с точными нижними границами критерия качества и , связанными с соотношением

.

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

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

Геометрически метод ветвей и границ показывается в виде дерева.

Е сли оказалось, что , то есть основания полагать, что оптимальный вариант входит в множество А и это множество надо исследовать детальней. Для этого его разбивают на два подмножества С и D так, чтобы оценки и различались возможно больше. Если оказалось, что , то разбиваем множество С на два и т.д. Процедуру продолжаем до тех пор, пока не придем к подмножеству, состоящему всего из одного элемента со значением параметра р = р₀ = .

Однако найденный элемент р = р₀ не всегда может быть оптимальным. Необходимо рассмотреть множества В , D и т.д. Может среди них найдется элемент p < p₀ . Эта проверка или даст элемент p < p₀ или подтвердит, что оптимальным является элемент р = р₀ .

Для каждой задачи, которая решается методом ветвей и границ , имеются свои особенности. Рассмотрим метод ветвей и границ применительно для решения задачи коммивояжера.

Пример. Коммивояжер должен посетить п городов и вернуться в исходный пункт с наименьшими затратами на переезды. При переезде из города I в город j он терпит убыток с_ij . Матрица размера описывает стоимости перемещения. Нельзя посещать один и тот же город дважды. Определить маршрут с минимальной стоимостью.

□ Проиллюстрируем решение задачи следующим примером. Матрица С размера определяет стоимости переездов

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

1. Из каждой строки матрицы стоимостей вычитаем минимальный элемент

2. Вычитаем минимальные элементы из тех столбцов,в которых нет 0:

3. Пусть Х – множество всех маршрутов. Суммируем все минимальные числа и принимаем это значение в качестве нижней

границы (Н.Г.) (оценка снизу) стоимости всех решений (маршрутов) Х

Н.Г. = ( 25 + 5 + 1 + 6 + 7) + 3 = 47.

Это число означает, что стоимость полного маршрута не может быть меньше 47 денежных единиц.

4. В последней матрице для каждой клетки ( I, j ), в которой , находим число, которое определяется путем сложения наименьших чисел i-ой строки и j-ого столбца. Сама клетка ( I, j ) в этих подсчетах не участвует. Найденные значения устанавливаем в виде верхних индексов у нулей:

Выбираем наибольшее значение индекса. Другими словами, выбираем ноль, который соответствует переезду , т.к. он имеет наибольший индекс, равный 15. Тем самым разбиваем множество всех маршрутов на два подмножества: где разрешается переезд и где не разрешается этот переезд : 2 1. Таким образом, увеличиваем Н.Г. подмножества с 2 1 в правом поддереве на 15:

Н.Г.= 47 + 15 = 62.

Вычеркиваем 2-ую строку и 1-ый столбец в последней матрице стоимостей. Тем самым понижаем порядок матрицы на единицу. Поскольку мы переехали из города 2 в город 1, а возвращаться нельзя, то следует запретить обратный переход из 1 в 2: . В результате получим матрицу:

Замечаем, что в 1-ой строке и 2-ом столбце отсутствуют нули. Вычитаем из элементов 1-ой строки минимальный элемент 2, а из элементов 2-ого столбца – элемент 1.При этом Н.Г. маршрутов в левом поддереве (маршрутов, содержащих переход ) увеличится на 3:

Н.Г. = 47 + (2 + 1) = 50.

5. В преобразованной матрице стоимостей совершаем операции, аналогичные операциям п. 4. В результате получим

i\ j	2	3	4	5
1		13	1		2
3	13		2
4	43	18
5
	1

Выбираем ноль, который соответствует переходу , при этом обратный переход запрещаем: . Увеличиваем Н.Г. стоимостей маршрутов подмножества без перехода (4 5) в правом поддереве на 18:

Н.Г. = 50 + 18 = 68.

В строках 1 и 3 нет нулей. Вычитаем минимальные элементы из этих строк и увеличиваем Н.Г. подмножества, содержащего переход , в левой части поддерева на сумму этих элементов:

Н.Г. = 50 + (1 + 2) = 53.

Имеются два нуля с максимальными индексами: 12. Выбираем любой из них, например, соответствующий переходу . При этом повышаем Н.Г. стоимости подмножества, соответствующего 5 3 на 12:

Н.Г. = 53 + 12 = 65.

Поскольку в процессе решения были выбраны переходы и , то во избежание образования цикла следует запретить обратный переход , т.е. . Матрица примет вид:

В столбце 2 нет нулей. Вычитаем минимальный элемент, равный 11 и увеличиваем Н.Г. стоимости подмножества, содержащего переход на 11:

Н.Г. = 53 + 11 = 64.

Совершая операции, аналогичные операциям п. 4., получим матрицу

Выбираем переходы и . В результате получим маршрут со стоимостью, равной 64:

.

Дерево, соответствующее этому решению, имеет вид:

Но имеется группа маршрутов, где переход запрещен, но стоимость меньше 64.

7. Возвращаемся к маршруту, где стоимость равна 62, поскольку в других узлах стоимость выше. Запрещаем переход . Тогда матрица примет вид:

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

i \ j	1	2	3	4	5
1			15	3	2
2				10	8	12
3	15	14		2
4		44	18		0
5	12	1	0
	3

Для подмножества с 2 1 Н.Г. = 47 + (12 + 3) = 62.

По индексам у нулей выбираем переход и 4 1. Для подмножества с 4 1 Н.Г. = 62 + 12 = 74. Вычеркиваем 4-ую строку и 1-ый столбец , запрещаем переход 1 . Тогда получим матрицу

Так как матрица приведенная ( в каждом столбце и каждой строке имеются нули ), то оценка для подмножества с переходом 4 не изменится: Н.Г. = 62.

По индексам у нулей выбираем и 2 3. Для подмножества с 2 3 оценка увеличится : Н.Г. = 62 + 8 = 70. Удаляем строку 2 и столбец 3, запрещаем переход . Тогда получим

Матрица приведенная, значит для подмножества с переходом оценка Н.Г. = 62.

Выбираем и 3 5. Для подмножества 3 5 Н.Г. = 62 + 4= = 66. Удаляя строку 3 и столбец 5, получим

Матрица приведенная, поэтому для подмножества с переходом оценка Н.Г. = 62.

Выбираем и , 1 2 и 5 4. Для подмножества с

1 2 и 5 4 Н.Г. = 62 + 1 + 1 = 64. Для подмножества с переходами

и Н.Г. = 62.

В результате получим оптимальный маршрут со стоимостью, равной 62 :

.

Дерево с оптимальным маршрутом имеет вид:

■