9. Как зависит трудоемкость перебора от числа переменных и от числа возможных значений переменных?

T=O(mn), где m - число вершин самого нижнего уровня, n – номер уровня (экспоненциальная оценка).

Размер дерева перебора может быть очень большим. Пусть для простоты все mi = m, тогда число всех планов (не обязательно допустимых) равно mn. Приняв довольно скромное значение m = 10, легко видеть, что при n  3 дерево можно обойти даже вручную, при значениях n от 4 до 7-8 с задачей без труда справится компьютер, но уже для значений n примерно от 11-12 и выше трудно рассчитывать на выполнение перебора с использованием любой существующей техники. Действительно, ведь в данном примере увеличение размерности задачи всего лишь на 1 приводит к увеличению времени решения в 10 раз.

10. Что называется рекордом при решении задач оптимизации?

Рекорд – это наилучшее из значений целевой функции на данный момент работы.

11. В каких случаях можно сократить перебор с возвратами?

• Иногда уже после выбора нескольких первых значений x_i выясняется, что на данной ветви дерева перебора не может быть допустимых планов. Например, коммивояжер раньше времени вернулся в исходный город, рюкзак переполнен первым же товаром, при раскраске графа две смежные вершины оказались одного цвета. Во всех этих случаях нет смысла достраивать план до полного, лучше уже не будет.

• Похожая ситуация иногда возникает в задачах оптимизации. Каждый построенный план задачи должен сравниваться с текущим рекордом. Иногда удается, не дожидаясь построения полного плана, сравнить с рекордом и на основании этого сравнения отвергнуть частичный план. Например, для задачи о коммивояжере текущий рекорд составляет 500 единиц длины, а очередной строящийся план начинается с путей длиной 200 и 350 единиц. Нет смысла достраивать такой план, потому что короче он уже не станет.

• В задаче поиска иногда возникает ситуация, когда удачный выбор нескольких первых переменных гарантирует, что план будет допустим при любых значениях оставшихся переменных. Например, в задаче о тождественной истинности ДНФ может оказаться, что первое же значение x₁ = 0 обращает в нуль все элементарные конъюнкции.

• В задаче оптимизации иногда удается построить допустимый план, относительно которого можно с уверенностью сказать, что он оптимален, потому что лучшего просто не бывает. Например, если в задаче о коммивояжере удалось построить такой замкнутый маршрут, в котором путь из каждого города ведет в ближайший к нему город, то этот маршрут, очевидно, является кратчайшим и дальнейший перебор не имеет смысла.

12. Что такое последовательный перебор (перебор с перечислением планов)?

Организация цикла со счётчиком планов.

Это такой перебор, при котором следует продолжать перебор до получения всех допустимых планов.

13. В чем недостаток последовательного перебора по сравнению с перебором с возвратами?

В переборе с возвратами возможно отсечение целых ветвей дерева – меньше занимаемых ресурсов.

14. В чем идея метода ветвей и границ?

Метод ветвей и границ— общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации.

Идея заключается в отсеве подмножеств допустимых решений, заведомо не содержащих оптимальных решений.

15. Для чего служат оценки снизу при решении задач методом ветвей и границ?

Оценка снизу равна ₁ =  + ₂₁ , где  показывает, на сколько длина приведенного маршрута меньше длины исходного (кратчайший маршрут имеет длину не менее ), а _ij – оценки потерь в случае неиспользования данного пути в маршруте коммивояжера(равна сумме оценок по строке и по столбцу)

Сравнение нижней оценки некоторого множества с уже имеющимся рекордным планом позволяет отбросить заведомо «плохие» множества (если целевая ф-ция больше множества)