![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Метод ветвей и границ. Решение задачи о рюкзаке.
Метод вариаций используется в задачах, где можно произвести полный анализ задач, т.е. полный перебор вариантов. Если такое невозможно, то используются методы неполного перебора, напр. Метод ветвей и границ: Нужно найти х0 Алгоритм: 1. Мн-во М разбиваем на не пересекаемые подмн-ва: 2. На каждом подмн-ве находим границу. Сn* – точная граница, если 3. Если есть точные границы у подмн-в, то находим самую наименьшую из них. Т.е. подмн-ва, у которых границы Ci > Cn исключаем из рассмотрения. 4. Если все подмн-ва исключены, то останавливаем алгоритм. 5. Если существует мн-во, у которого Сi*< Сn, то данное подмн-во снова разбиваем и переходим к п.2. Для реализации алгоритма используется схема: Задача о рюкзаке: Пусть имеется n предметов: Рассм. Задачу 1) типа. Пусть Разбивать на множества будем след. образом: в 1 группу попадает набор предметов при условии, что предмет
|