Трудные задачи требуют экспоненциального времени на поиск решения.
*Метод поиска с возвратом* и *метод ветвей и границ* являются усовершенствованием исчерпывающего перебора,
рассмотренного в методах грубой силы, и позволяют получить точное решение.
В отличие от исчерпывающего перебора указанные методы строят
кандидатов в решения по одному компоненту и оценивают частично построенные
решения: если потенциальных значений оставшихся компонентов, которые
могли бы привести к корректному решению, не имеется, то оставшиеся компоненты
решения не генерируются.
--
Метод ветвей и границ применим только к оптимизационным задачам, поскольку основан на вычислении границ возможных
значений целевой функции. Поиск с возвратом можно применять для любых задач.
Оба метода основаны на построении *дерева пространства состояний*, узлы которого отражают конкретные выборы,
сделанные для компонентов решения.
Его корень представляет начальное состояние перед началом поиска.
Узлы на первом уровне дерева представляют варианты выбора,
сделанные для первого компонента решения, узлы на втором уровне — варианты
выбора второго компонента и т.д.
--
Узел дерева пространства состояний называется
*перспективным*, если он соответствует частично построенному решению,
которое может привести к полному решению; в противном случае он называется
*бесперспективным*. Листья дерева представляют собой либо
бесперспективные тупики, либо полные решения, найденные алгоритмом.
При поиске с возвратом выполняется простой обход дерева в глубину.
В методе ветвей и границ сначала рассматриваются наиболее перспективные варианты.
--
Если текущий узел бесперспективен, алгоритм возвращается к родительскому узлу и рассматривает очередной
возможный вариант для его последнего компонента; если такого варианта нет,
алгоритм поднимается вверх по дереву на один уровень и продолжает работу.
При получении полного решения задачи, поиск с возвратом обычно завершает работу (если требуется только одно
решение), а метод ветвей и границ продолжает поиск более оптимальных решений.