Содержание
- 2. Задача оптимизации: где конечное множество допустимых решений множество всех подмножеств множества
- 3. Ветвление – это функция которая каждому подмножеству множества ставит в соответствие некоторое его разбиение таким образом:
- 4. Оценка – это функция Величина оценивает сверху значения функции на множестве и совпадает с ней на
- 5. Пусть L – это список подмножеств множества Рекорд – это число, которое:
- 6. Общая схема метода ветвей и границ Шаг 0: ищется начальное решение для k =1,2,… Шаг k:
- 7. На каждом шаге необходимо обновлять рекорд при обнаружении решений лучших, чем текущее рекордное решение. Для реализации
- 8. Пример: задача о рюкзаке. Даны рюкзак грузоподъемностью V и n предметов, каждый из которых имеет вес
- 9. Математическая модель задачи о рюкзаке:
- 10. Метод ветвей и границ схема ветвления: пусть определены значения Оценки:
- 11. Нет ветвления, если или
- 13. Скачать презентацию