Алгоритмы и модели вычислений

Если при решении задачи минимизации методом ветвей и границ нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то

(Отметьте один правильный вариант ответа.)

Варианты ответа

метод ветвей и границ не может быть реализован

подобласть A может быть исключена из дальнейшего рассмотрения(Верный ответ)

подобласть B не рассматривается для потенциального решения

Похожие вопросы

При решении задачи многопроцессорного расписания для m процессоров с помощью метода ветвей и границ количество вершин первого уровня дерева поиска может достигать

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

Подобласти, образовавшиеся в результате процедуры ветвления в методе ветвей и границ, образуют дерево, называемое

Разбиение области допустимых решений на подобласти меньших размеров в методе ветвей и границ представляет собой

Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является

Если d - максимальная высота дерева леса, n - количество вершин, то общие затраты многопроцессорного алгоритма определения корня для вершины двоичного леса составляют

Если классы P и NP равны, то любую задачу из класса NP можно будет решить

Если задача П₁ сводится по Тьюрингу к задаче П₂ из класса NP, то задача П₁ является

Если NP не равно co-NP, то любая задача, которая лежит и в классе NP и в классе co-NP

Если существует NP-полная задача П₁, которая сводится по Тьюрингу к задаче П₂, то задача П₂ является