5. Функции ветвления

Как при поиске по глубине, так и при поиске по ширине выбор очередной вершины для ветвления не был полностью определен.

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

Функция ветвления — это функция, которая позволяет «вычислить», какая из допустимых вершин должна использоваться при следующем ветвлении. Для вершины, соответствующей подзадаче эта функция является некоторой мерой вероятности того, что оптимальное решение всей задачи является решением для Совершенно очевидно, что вершина, соответствующая подзадаче с большими шансами на оптимальное решение, должна пользоваться правом преимущественного выбора при очередном ветвлении. Можно указать несколько эвристических мер этой вероятности, причем одна из полезных мер связана просто с вычислением для вершин нижних или верхних границ. Для такой меры вершина с более низкой нижней границей (для случая минимизации) считается имеющей большую вероятность.

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