65. По сравнению с методом поиска с возвратом метод ветвей и границ требует:

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

значение наилучшего решения, полученного к этому моменту.

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

В общем случае мы завершаем путь поиска в текущем узле дерева пространства состояний алгоритма ветвей и границ по одной из трех следующих причин:1)Значение границы узла не лучше значения наилучшего решения, найденного к этому моменту.2)Узел не представляет допустимых решений из-за нарушения ограничений, налагаемых задачей.

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

Применение: задача о назначениях, задача о коммивояжере, укладка рюкзака.

66. Динамическим программированием называют процесс пошагового решения задач, когда на каждом шаге выбирается одно решение из множества допустимых на этом шаге решений, оптимизирующее заданную (целевую) функцию F. Метод д.п. применим только тогда, когда функция F удовлетворяет принципу оптимальности Беллмана. Этот принцип требует, чтобы всякий отрезок a_i, a_i+1,...,a_m оптимальной последовательности а₁,...,а_n (1< = i < = т< = n) был бы сам оптимальным среди всех отрезков, совпадающих с ним по числу элементов и в крайних элементах. Это свойство позволяет найти оптимальную последовательность, постепенно удлиняя уже найденные от начала (конца) последовательности отрезки.

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

Два признака, характерных для задач, решаемых методом д.п: 1) Оптимальность для подзадач - необходимо сначала описать структуру оптимального решения. Задача обладает свойством оптимальности для подзадач, если оптимальное решение задачи содержит оптимальные решения её подзадач.

2) Перекрывающиеся подзадачи – небольшое число различных подзадач.

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

Примеры применения: перемножение нескольких матриц(Задача об умножении последовательности матриц может быть сформулирована следующим образом: дана последовательность из n матриц A₁A₂ ×…×A_n заданных размеров (матрица A_i имеет размер p_i-1´p_i ); требуется найти такую расстановку скобок в произведении A₁A₂ …A_n, чтобы вычисление произведения требовало наименьшего числа умножений); задача об оптимальной триангуляции многоугольника (Дан выпуклый многоугольник Р = áv0, v1, …, vn-1ñ и весовая функция w, определённая на множестве треугольников с вершинами в вершинах Р. Требуется найти триангуляцию, для которой сумма весов треугольников будет наименьшей). Разбиение абзаца на строки; Алгоритм Витерби (Динамическое программирование может быть применено к задаче распознавания речи. В качестве модели рассмотрим ориентированный граф G = (V, Е) и отображение о, сопоставляющее с каждым ребром (u, v) звук s(и, v) из множества возможных звуков å. В графе выделена некоторая вершина v0. Каждому пути, начинающемуся в v0 , соответствует последовательность звуков (элементов å) ).

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

• Методы решета полезны прежде всего в теоретико-числовых вычислениях. Например, одним из наиболее известных методов отыскания простых чисел является «решето Эратосфена». Это решето перечисляет составные (не простые) числа между N и N2 для некоторого N

• Легко понять, почему методы решета могут быть полезны. Если в множестве возможных решений элементы можно удобно занумеровать натуральными числами, то хранить нужно только характеристический вектор; в этом векторе i-й разряд равен нулю, если i-й элемент не является решением, и равен единице в противном случае. Таким образом, на множествах, состоящих буквально из миллионов элементов, возможен поиск без явного порождения и исследования каждого элемента множества. Кроме того, в большинстве вычислительных устройств булевы операции можно производить параллельно над многими разрядами, обеспечивая тем самым значительную экономию времени.