Реферат: Лекции по вычислительной математике

Специальность ПО

5-й семестр

Конспект лекций

Лекция 1

Общее описание метода ветвей и границ организации пол-ного перебора возможностей . Решение задачи о коммивояжере методом ветвей и границ: основная схема.

Пусть - конечное множество и - ве-щественно-значная функция на нем; требуется найти минимум

этой функции и элемент множества, на котором этот минимум

достигается.

Когда имеется та или иная дополнительная информация о множестве, решение этой задачи иногда удается осуществить без полного перебора элементов всего множества M . Но чаще

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

обязательно возникает задача, как лучше перебор организовать.

Метод ветвей и границ - это один из методов организации полного перебора. Он применим не всегда, а только тогда, когда

выполняются специфические дополнительные условия на множе-

ство M и минимизируемую на нем функцию. А именно, -

предположим , что имеется вещественно-значная функция j на множестве подмножеств множества M со следующими двумя свойствами:

1) для (здесь - множество, состоящее

из единственного элемента );

2) если и , то .

В этих условиях можно организовать перебор элементов множества M с целью минимизации функции на этом множестве так:

разобьем множество M на части (любым способом) и выбе-

рем ту из его частей W₁ , на которой функция j минимальна; за-тем разобьем на несколько частей множество W₁ и выберем ту из его частей W₂ , на которой минимальна функция j ; затем разо-бьем W₂ на несколько частей и выберем ту из них, где минималь-на j, и так далее, пока не придем к какому-либо одноэлементно-му множеству .

Это одноэлементное множество называется рекордом .

Функция j , которой мы при этом выборе пользуемся, называется

оценочной. Очевидно, что рекорд не обязан доставлять минимум

функции f ; однако, вот какая возможность возникает сократить

перебор при благоприятных обстоятельствах .

Описанный выше процесс построения рекорда состоял из последовательных этапов, на каждом из которых фиксировалось

несколько множеств и выбиралось затем одно из них. Пусть

- подмножества множества M , возникшие на предпослед-нем этапе построения рекорда, и пусть множество оказалось

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

--> ЧИТАТЬ ПОЛНОСТЬЮ <--