Метод ветвей и границ. Решение задачи о рюкзаке.

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

Нужно найти х_{0 .} Число С_n – граница множества М, если .

Алгоритм:

1. Мн-во М разбиваем на не пересекаемые подмн-ва:

2. На каждом подмн-ве находим границу. С_n^* – точная граница, если

3. Если есть точные границы у подмн-в, то находим самую наименьшую из них. Т.е. подмн-ва, у которых границы C_i > C_n исключаем из рассмотрения.

4. Если все подмн-ва исключены, то останавливаем алгоритм.

5. Если существует мн-во, у которого С_i^*< С_n, то данное подмн-во снова разбиваем и переходим к п.2.

Для реализации алгоритма используется схема:

Задача о рюкзаке:

Пусть имеется n предметов: – вес i-того предмета, - ценность i-того предмета. Бывают 2 задачи: 1) Выбрать такой набор предметов, чтобы их вес был минимален, а ценность была не меньше С. 2) Подобрать такой набор предметов, чтобы их ценность была максимальна, а вес не превышал P.

Рассм. Задачу 1) типа.

Пусть i=

Разбивать на множества будем след. образом: в 1 группу попадает набор предметов при условии, что предмет этому множеству. Во вторую группу - . Если i-тый предмет попадает в рюкзак, если i-тый предмет не попадает в рюкзак.