1 of 21

Методы оптимизации: семинар 12

ФКН НИУ ВШЭ

2021-2022

Маминов А.Д.

2 of 21

Введение

  •  

3 of 21

Введение

  •  

4 of 21

Задача о ранце

  •  

5 of 21

Задача о ранце

  •  

6 of 21

Задача о ранце: вариации

  •  

7 of 21

Задача о ранце: вариации

  •  

8 of 21

Задача о ранце: вариации

  •  

9 of 21

Задача о ранце: вариации

  •  

10 of 21

Задача о ранце: вариации

  •  

11 of 21

Как решать задачу о ранце?

  • Допустим, мы захотим перебрать все решения в задаче о ранце. Сколько их?

12 of 21

Метод ветвей и границ

  •  

13 of 21

Метод ветвей и границ

  •  

14 of 21

Метод ветвей и границ

  •  

Можно�комби-�нировать!

15 of 21

Метод ветвей и границ. Алгоритм.

  •  

16 of 21

Метод динамического программирования

  •  

17 of 21

Примеры

  •  

18 of 21

Задаче об упаковке ящиков

 

19 of 21

Задаче об упаковке ящиков. �Приближённые алгоритмы

  •  

​

​

20 of 21

Онлайн алгоритмы

  •  

​

​

21 of 21

Офлайн алгоритмы

  •  

​

​