4. Применение границ

Если задача подлежит решению как задача оптимизации, то безотносительно к типу поиска этот поиск завершается только тогда, когда будут разрешены все подзадачи, представляемые висячими вершинами. Для ускорения процесса разрешения для каждой из висячих вершин вычисляются нижние или верхние границы (для случаев минимизации или максимизации соответственно). Эти границы дают наименьшее (или наибольшее) возможное значение оптимального решения той подзадачи, которая

соответствует рассматриваемой висячей вершине. Таким образом (для задачи минимизации), если окажется, что нижняя граница для вершины, соответствующей задаче больше, чем величина наилучшего ответа, полученного ранее при поиске, то в нет необходимости производить дальнейшее ветвление, так как в нет решения, лучшего, чем текущий наилучший ответ. В соответствии с толкованием (II) термина «разрешение задачи» из разд. 1 подзадача окажется автоматически разрешенной.