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

Пусть U - множество всех допустимых планов задачи оптимизации и F(X) - целевая функция, подлежащая минимизации. Разделим каким-то образом множество U на два непересекающихся подмножества U0 и U1. При этом постараемся провести разделение так, чтобы множество U0 было «поменьше и получше», т.е. с наибольшей вероятностью содержало искомый оптимальный план и при этом было невелико по мощности. Практически разделение можно выполнить, например, так: выбрать какое-то «наиболее перспективное» значение одной из переменных и отнести к U0 все планы с этим значением переменной. Далее аналогичным образом разделим U0 на два множества U00 и U01, затем разделим U00 на U000 и U001 и т.д. На некотором шаге придем к множеству, содержащему только один план. Чтобы не плодить индексы, предположим, что это произошло на четвертом шаге: U0000 = {X0}. Результат разделения множеств показан на рис.1.2. Получен некоторый допустимый план X0. Не является ли он оптимальным?

Пусть имеется какая-то достаточно просто вычисляемая функция (W), дающая оценку снизу для любого подмножества W U, т.е. (W) F(X) для любого X W. Оценка не обязательно должна быть точной, т.е. на самом деле, возможно, минимум F(X) при X W больше, чем оценка (W). Однако чем она точнее, тем лучше будет работать алгоритм.

Вычислим значение целевой функции F(X0) и сравним его с оценкой (U0001). Если F(X0) (U0001), то план X₀ является лучшим среди всего подмножества U000. Мы выяснили это, не выполняя перебора планов из U0001. В этом случае следует подняться по дереву и вычислить оценку U001. Если, на наше счастье, F(X0) (U001), то план X₀ является лучшим на подмножестве U00 и т.д.

Что, если на каком-то шаге подъема по дереву оценка (W) не позволит отсечь очередное подмножество без рассмотрения? Пусть, например, F(X0) > (U01). Тогда следует разделить U01 на U010 и U011, U010 на U0100 и U0111 и т.д., то есть выполнить спуск еще по одной ветви дерева. При этом будет получен другой план, назовем его X₁. После этого следует запомнить лучший из двух планов в качестве рекорда и в дальнейшем использовать его для сравнения с нижними оценками множеств.

Работа алгоритма будет завершена тогда, когда каждое из построенных подмножеств будет либо состоять из одного элемента, для которого можно вычислить целевую функцию, либо будет исключено из рассмотрения на основании сравнения нижней оценки целевой функции на множестве с текущим рекордом

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

c20 итд

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

?Вычитая одно и то же число из всех элементов строки (т.е. из всех расстояний от данного города до других городов), мы уменьшаем на это число длину всех возможных маршрутов коммивояжера, поскольку каждый допустимый маршрут ровно один раз проходит через каждый город. Величина j показывает, на сколько длина приведенного маршрута меньше длины исходного. Ясно, что после приведения кратчайший маршрут останется кратчайшим. Зато теперь можно легко получить оценку снизу для всего множества маршрутов исходной задачи. Поскольку для приведенной матрицы кратчайший маршрут не может иметь длину меньше 0, то для исходной матрицы кратчайший маршрут имеет длину не менее j.

17. Для каких задач может использоваться метод --отсечений?

с 32 итд

18. Что такое -отсечение? -отсечение?

Альфа-бета отсечение — это алгоритм поиска, стремящийся сократить количество узлов, оцениваемых в дереве поиска алгоритмом минимакс.

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

Альфа-бета отсечение является оптимизацией

19. Как поступают, если в методе --отсечений перебор остается слишком большим?

При этом вычисление точных значений вершин приходится заменять вычислением приближенных оценочных функций. На каждом ходу строят дерево перебора, искусственно ограниченное по высоте несколькими ходами, и для тех позиций игры, которые оказались в роли листьев усеченного дерева, вычисляют приближенную оценку позиции. Для шахмат, например, самая тупая оценочная функция учитывает только суммарную стоимость оставшихся фигур. Более изощренные функции учитывают различные позиционные факторы: контроль над центром, наличие проходных пешек и т.п. На основании таких оценок выполняется перебор с --отсечениями и выбирается наилучший ход. После получения ответного хода соперника вся процедура повторяется для новой корневой позиции.