Войти
Переход и граница (BB, BB, или BnB ) - алгоритм парадигма проектирования для дискретных и задач комбинаторной оптимизации, а также математической оптимизации. Алгоритм ветвей и границ состоит из систематического перечисления возможных решений с помощью поиска в пространстве состояний : набор возможных решений рассматривается как формирование корневого дерева с полным установить в корень. Алгоритм исследует ветви этого дерева, которые представляют собой подмножества множества решений. Перед перечислением возможных решений ветви, ветвь проверяется на соответствие верхней и нижней оценкам оптимального решения и отбрасывается, если она не может дать лучшее решение, чем лучшее, найденное алгоритмом на данный момент.
Алгоритм зависит от эффективной оценки нижней и верхней границ областей / ветвей пространства поиска. Если границы недоступны, алгоритм переходит к исчерпывающему поиску.
Метод был впервые предложен Айлсой Лэнд и Элисон Дойг во время проведения исследования в Лондонской школе экономики при спонсорской поддержке British Petroleum в 1960 году для дискретного программирования, и стал наиболее часто используемым инструментом для решения NP-сложных задач оптимизации. Название «ветвь и граница» впервые появилось в работе Little et al. по задаче коммивояжера .
Цель алгоритма ветвей и границ - найти значение x, которое максимизирует или минимизирует значение реального -значная функция f (x), называемая целевой функцией, среди некоторого множества S допустимых, или возможных решений. Набор S называется пространством поиска или допустимой областью. В остальной части этого раздела предполагается, что желательна минимизация f (x); это предположение приходит без потери общности, поскольку можно найти максимальное значение f (x), найдя минимум g (x) = −f (x). Алгоритм BB работает в соответствии с двумя принципами:
Превращение этих принципов в конкретный алгоритм для конкретной задачи оптимизации требует некоторого вида структуры данных, которая представляет наборы возможных решений. Такое представление называется экземпляром проблемы. Обозначим множество возможных решений экземпляра I через S I. Экземплярное представление должно включать три операции:
Используя эти операции, алгоритм BB выполняет нисходящий рекурсивный поиск по дереву экземпляров, сформированных операцией ветвления. При посещении экземпляра I он проверяет, больше ли граница (I) найденной на данный момент верхней границы; в таком случае меня можно безопасно исключить из поиска, и рекурсия прекратится. Этот шаг сокращения обычно реализуется путем поддержания глобальной переменной, которая записывает минимальную верхнюю границу, наблюдаемую среди всех исследованных экземпляров.
Ниже приведен каркас универсального алгоритма ветвления и границы для минимизации произвольной целевой функции f. Чтобы получить из этого фактический алгоритм, требуется граница функции, которая вычисляет нижние границы f на узлах дерева поиска, а также правило ветвления для конкретной задачи. Таким образом, общий алгоритм, представленный здесь, является функцией более высокого порядка.
Можно использовать несколько различных структур данных queue. Эта реализация на основе очереди FIFO дает поиск в ширину. Стек (очередь LIFO) даст алгоритм в глубину. Алгоритм перехода и границы best-first может быть получен с помощью очереди приоритетов, которая сортирует узлы по их нижней границе. Примерами алгоритмов поиска «лучший первый» с этой предпосылкой являются алгоритм Дейкстры и его потомок A * search. Вариант в глубину рекомендуется, когда нет хорошей эвристики для получения начального решения, потому что он быстро дает полные решения и, следовательно, верхние границы.
A C ++ -подобная реализация псевдокода для приведенное выше:
1 // C ++ - подобная реализация ветвления и границы, 2 // предполагая, что целевая функция f должна быть минимизирована 3 CombinatorialSolution branch_and_bound_solve (4 CombinatorialProblem проблема, 5 ObjectiveFunction objective_function / * f * /, 6 BoundingFunction lower_bound_function / * bound * /) 7 {8 // Шаг 1 выше 9 double problem_upper_bound = std :: numeric_limits :: infinity; // = B 10 CombinatorialSolution heuristic_solution = heuristic_solve (проблема); // x_h 11 problem_upper_bound = objective_function (heuristic_solution); // B = f (x_h) 12 Комбинаторное решение current_optimum = heuristic_solution; 13 // Шаг 2 выше 14 queue кандидата_queue; 15 // инициализация очереди, специфичной для проблемы 16 кандидата_queue = populate_candidates (проблема); 17 while (! Кандидата_queue.empty ()) {// Шаг 3 выше 18 // Шаг 3.1 19 CandidateSolutionTree node = кандидата_queue.pop (); 20 // "узел" представляет N выше 21 if (node.presents_single_candidate ()) {// Шаг 3.2 22 if (objective_function (node.candidate ()) < problem_upper_bound) { 23 current_optimum = node.candidate(); 24 problem_upper_bound = objective_function(current_optimum); 25 } 26 // else, node is a single candidate which is not optimum 27 } 28 else { // Step 3.3: node represents a branch of candidate solutions 29 // "child_branch" represents N_i above 30 for (autochild_branch : node.candidate_nodes) { 31 if (lower_bound_function(child_branch) <= problem_upper_bound) { 32 candidate_queue.enqueue(child_branch); // Step 3.3.2 33 } 34 // otherwise, bound(N_i)>B, поэтому мы сокращаем ветвь; шаг 3.3.1 35} 36} 37} 38 return current_optimum; 39} В приведенном выше псевдокоде функции heuristic_solveи populate_candidates, вызываемые как подпрограммы, должны быть предоставлены в зависимости от проблемы. (target_function) и граница (lower_bound_function) обрабатываются как объекты функции, как написано, и могут соответствовать лямбда-выражениям, указатели на функции или функторы в языке программирования C ++, среди других типов вызываемых объектов.
Когда 
Этот подход используется для ряда NP-сложных задач
Разделение и граница также может быть основой различных эвристик. Например, кто-то может пожелать прекратить ветвление, когда разрыв между верхней и нижней границами становится меньше определенного порога. Это используется, когда решение «достаточно хорошо для практических целей» и может значительно сократить требуемые вычисления. Этот тип решения особенно применим, когда используемая функция стоимости зашумлена или является результатом статистических оценок и поэтому точно не известна, а скорее всего лишь известна как лежащая в диапазоне значений. с определенной вероятностью .
Nau et al. представляют собой обобщение ветвей и границ, которое также включает алгоритмы поиска A*, B* и альфа-бета из искусственного интеллекта.
