An Entity of Type: programming language, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.

Property Value
dbo:abstract
  • Jako metoda větví a mezí nebo též metoda větví a hranic či B&B, anglicky branch and bound se označuje typ algoritmů v a , které při prohledávání stavového prostoru postupují, jako by se jednalo o strom; pro jednotlivé větve reprezentující části prostoru možných řešení odhadují horní a spodní meze cílové funkce, a vylučují větve, ve kterých se na základě těchto odhadů nemůže vyskytovat optimální řešení. Metoda se používá i pro nekonvexní spojitou optimalizace bez omezení. Metoda je implementována například v programu BARON ([1]). Metoda hledá vždy globální řešení optimalizačního problému. Metodu poprvé navrhly a v roce 1960 pro lineární programování. Typickou úlohou, kde se využívá, je problém batohu. (cs)
  • Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm. The algorithm depends on efficient estimation of the lower and upper bounds of regions/branches of the search space. If no bounds are available, the algorithm degenerates to an exhaustive search. The method was first proposed by Ailsa Land and Alison Doig whilst carrying out research at the London School of Economics sponsored by British Petroleum in 1960 for discrete programming, and has become the most commonly used tool for solving NP-hard optimization problems. The name "branch and bound" first occurred in the work of Little et al. on the traveling salesman problem. Branch and bound methods do not go deep like Depth-first search; the first direction is lateral movement in the tree similar to Breadth-first search (BFS). (en)
  • Branch-and-Bound (engl. für Verzweigung und Schranke oder Verzweigen und begrenzen) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch-and-Bound führt auf einen Entscheidungsbaum, ist selbst aber kein spezielles Verfahren, sondern eine Behandlungsmethode, ein Meta-Verfahren. Für konkrete kombinatorische Optimierungsprobleme ergeben sich dementsprechend angepasste Branch-and-Bound-Algorithmen. (de)
  • El método de diseño de algoritmos ramificación y poda (también llamado ramificación y acotación) es una variante del backtracking mejorado sustancialmente. El término (del inglés, Branch and Bound) se aplica mayoritariamente para resolver cuestiones o problemas de optimización. La técnica de ramificación y poda se suele interpretar como un árbol de soluciones, donde cada rama conduce a una posible solución posterior a la actual. La característica de esta técnica con respecto a otras anteriores (y a la que debe su nombre) es que el algoritmo se encarga de detectar en qué ramificación las soluciones dadas ya no están siendo óptimas, para «podar» esa rama del árbol y no continuar malgastando recursos y procesos en casos que se alejan de la solución óptima. (es)
  • Un algorithme par séparation et évaluation, ou branch and bound en anglais, est une méthode générique de résolution de problèmes d'optimisation combinatoire. Cet algorithme a été introduit par Ailsa Land et Alison Harcourt (Doig) en 1960. L'optimisation combinatoire consiste à trouver un point minimisant une fonction, appelée coût, dans un ensemble dénombrable. Une méthode naïve pour résoudre ce problème est d'énumérer toutes les solutions du problème, de calculer le coût pour chacune, puis de donner le minimum. Parfois, il est possible d'éviter d'énumérer des solutions dont on sait, par l'analyse des propriétés du problème, que ce sont de mauvaises solutions, c'est-à-dire des solutions qui ne peuvent pas être le minimum. La méthode séparation et évaluation est une méthode générale pour cela. Cette méthode est très utilisée pour résoudre des problèmes NP-complets, c'est-à-dire des problèmes considérés comme difficiles à résoudre efficacement. Le branch and bound est parfois comparé à une autre technique de recherche de solution, l'algorithme A*, très souvent utilisé en intelligence artificielle, alors que le branch and bound est plutôt destiné aux problèmes de recherche opérationnelle. (fr)
  • 분기 한정법(分岐限定法, Branch and bound)은 다양한 최적화 문제를 풀기 위한 범용 알고리즘이다. 주로 나 조합 최적화 문제를 풀 때 쓴다. 분기 한정법은 모든 후보해를 체계적으로 늘어놓으면서 최적화할 수치의 상한과 하한을 추정, 가망 없다는 판정이 나는 해를 제거해 나간다. 제거하는 해에서 파생되는 해는 살펴보지 않기 때문에 불필요한 시간 소모를 줄이게 된다. 이 방법은 A. H. 랜드와 A. G. 도이그가 1960년에 선형 계획법을 풀기 위해서 제안하였다. (ko)
  • Il branch and bound è una tecnica generale per la risoluzione di problemi di (cioè problemi con spazio di soluzioni finito) e si basa sulla scomposizione del problema originale in sottoproblemi più semplici da risolvere. Questo metodo è stato inizialmente proposto da A. H. Land e A. G. Doig nel 1960 per risolvere problemi di programmazione lineare intera. Gli algoritmi Branch and Bound sono detti di enumerazione implicita perché si comportano esattamente come un algoritmo di enumerazione -cioè "provano" tutte le soluzioni possibili fino a trovare quella ottima (o quella corretta)- ma ne scartano alcune dimostrando a priori la loro non ottimalità. (it)
  • 分枝限定法(ぶんしげんていほう、英: branch and bound, BB)は、各種最適化問題(特にと組合せ最適化)の最適解を求める汎用アルゴリズムである。分枝操作(英: branching operation)と限定操作(英: bounding operation)から構成される。全ての解候補を体系的に列挙するもので、最適化された量の上限と下限の概算を使って、最適でない候補は「ひとまとめに」捨てられる。 1960年、A. H. Land と A. G. Doig が線型計画法の手法として最初に提案した。 (ja)
  • O método de Ramificar e limitar (em inglês, Branch and bound) é um algoritmo para encontrar soluções ótimas para vários problemas de otimização, especialmente em otimização combinatória. Consiste em uma enumeração sistemática de todos os candidatos a solução, através da qual grandes subconjuntos de candidatos infrutíferos são descartados em massa utilizando os limites superior e inferior da quantia otimizada. O método foi proposto por A. H. Land e A. G. Doig em 1960 para . É utilizado para vários problemas NP-completos como o problema do caixeiro viajante e o problema da mochila. (pt)
  • Метод ветвей и границ (англ. branch and bound) — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. Метод является развитием метода полного перебора, в отличие от последнего — с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений. Метод ветвей и границ впервые предложен в 1960 году Алисой Лэнд и Элисон Дойг для решения задач целочисленного программирования. Общая идея метода может быть описана на примере поиска минимума функции на множестве допустимых значений переменной . Функция и переменная могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ). Процедура ветвления состоит в разбиении множества допустимых значений переменной на подобласти (подмножества) меньших размеров. Процедуру можно рекурсивно применять к подобластям. Полученные подобласти образуют дерево, называемое деревом поиска или деревом ветвей и границ. Узлами этого дерева являются построенные подобласти (подмножества множества значений переменной ). Процедура нахождения оценок заключается в поиске верхних и нижних границ для решения задачи на подобласти допустимых значений переменной . В основе метода ветвей и границ лежит следующая идея: если нижняя граница значений функции на подобласти дерева поиска больше, чем верхняя граница на какой-либо ранее просмотренной подобласти , то может быть исключена из дальнейшего рассмотрения (правило отсева). Обычно минимальную из полученных верхних оценок записывают в глобальную переменную ; любой узел дерева поиска, нижняя граница которого больше значения , может быть исключён из дальнейшего рассмотрения. Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти. Метод используется для решения некоторых NP-полных задач, в том числе задачи коммивояжёра и задачи о ранце. (ru)
  • Метод гілок і меж (англ. Branch-and-Bound) — один з поширених методів дискретної оптимізації. Метод працює на дереві рішень та визначає принципи роботи конкретних алгоритмів пошуку розв'язків, тобто, є мета-алгоритмом. Для різних задач комбінаторної оптимізації створюють спеціалізовані алгоритми гілок та меж. Ідею методу було вперше сформульовано A.H. Land та A.G. Doig (1960) в галузі дослідження операцій. R.J. Dakin (1965) розробив простий для впровадження алгоритм. (uk)
  • 分支定界(英語:Branch and bound,BB)是用于离散优化、组合优化以及数学优化问题的算法设计范式。分支定界算法可以视为一种对可行解进行穷举的算法,但是和穷举法所不同的是,分支定界算法在对某一分支进行检索之前会先算出该分支的上界或下界,如果界限不比目前最佳解更好,那么该分支就会被舍弃,从而节约了大量的时间。分支定界算法非常依赖合适的上界或下界,如果无法找到合适的界限,该算法将会退化为穷举法。 该方法最初是由阿尔萨·兰德和艾莉森·哈考特在1960年由英国石油公司赞助的伦敦经济学院进行离散规划研究时提出的,目前已成为解决NP困难优化问题最常用的工具。“分支定界”一词最早出现在解决旅行推销员问题的时候。 (zh)
dbo:thumbnail
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 456580 (xsd:integer)
dbo:wikiPageLength
  • 20091 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1106168616 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:isPartOf
dcterms:subject
gold:hypernym
rdf:type
rdfs:comment
  • Branch-and-Bound (engl. für Verzweigung und Schranke oder Verzweigen und begrenzen) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch-and-Bound führt auf einen Entscheidungsbaum, ist selbst aber kein spezielles Verfahren, sondern eine Behandlungsmethode, ein Meta-Verfahren. Für konkrete kombinatorische Optimierungsprobleme ergeben sich dementsprechend angepasste Branch-and-Bound-Algorithmen. (de)
  • 분기 한정법(分岐限定法, Branch and bound)은 다양한 최적화 문제를 풀기 위한 범용 알고리즘이다. 주로 나 조합 최적화 문제를 풀 때 쓴다. 분기 한정법은 모든 후보해를 체계적으로 늘어놓으면서 최적화할 수치의 상한과 하한을 추정, 가망 없다는 판정이 나는 해를 제거해 나간다. 제거하는 해에서 파생되는 해는 살펴보지 않기 때문에 불필요한 시간 소모를 줄이게 된다. 이 방법은 A. H. 랜드와 A. G. 도이그가 1960년에 선형 계획법을 풀기 위해서 제안하였다. (ko)
  • 分枝限定法(ぶんしげんていほう、英: branch and bound, BB)は、各種最適化問題(特にと組合せ最適化)の最適解を求める汎用アルゴリズムである。分枝操作(英: branching operation)と限定操作(英: bounding operation)から構成される。全ての解候補を体系的に列挙するもので、最適化された量の上限と下限の概算を使って、最適でない候補は「ひとまとめに」捨てられる。 1960年、A. H. Land と A. G. Doig が線型計画法の手法として最初に提案した。 (ja)
  • O método de Ramificar e limitar (em inglês, Branch and bound) é um algoritmo para encontrar soluções ótimas para vários problemas de otimização, especialmente em otimização combinatória. Consiste em uma enumeração sistemática de todos os candidatos a solução, através da qual grandes subconjuntos de candidatos infrutíferos são descartados em massa utilizando os limites superior e inferior da quantia otimizada. O método foi proposto por A. H. Land e A. G. Doig em 1960 para . É utilizado para vários problemas NP-completos como o problema do caixeiro viajante e o problema da mochila. (pt)
  • Метод гілок і меж (англ. Branch-and-Bound) — один з поширених методів дискретної оптимізації. Метод працює на дереві рішень та визначає принципи роботи конкретних алгоритмів пошуку розв'язків, тобто, є мета-алгоритмом. Для різних задач комбінаторної оптимізації створюють спеціалізовані алгоритми гілок та меж. Ідею методу було вперше сформульовано A.H. Land та A.G. Doig (1960) в галузі дослідження операцій. R.J. Dakin (1965) розробив простий для впровадження алгоритм. (uk)
  • 分支定界(英語:Branch and bound,BB)是用于离散优化、组合优化以及数学优化问题的算法设计范式。分支定界算法可以视为一种对可行解进行穷举的算法,但是和穷举法所不同的是,分支定界算法在对某一分支进行检索之前会先算出该分支的上界或下界,如果界限不比目前最佳解更好,那么该分支就会被舍弃,从而节约了大量的时间。分支定界算法非常依赖合适的上界或下界,如果无法找到合适的界限,该算法将会退化为穷举法。 该方法最初是由阿尔萨·兰德和艾莉森·哈考特在1960年由英国石油公司赞助的伦敦经济学院进行离散规划研究时提出的,目前已成为解决NP困难优化问题最常用的工具。“分支定界”一词最早出现在解决旅行推销员问题的时候。 (zh)
  • Jako metoda větví a mezí nebo též metoda větví a hranic či B&B, anglicky branch and bound se označuje typ algoritmů v a , které při prohledávání stavového prostoru postupují, jako by se jednalo o strom; pro jednotlivé větve reprezentující části prostoru možných řešení odhadují horní a spodní meze cílové funkce, a vylučují větve, ve kterých se na základě těchto odhadů nemůže vyskytovat optimální řešení. Metoda se používá i pro nekonvexní spojitou optimalizace bez omezení. Metoda je implementována například v programu BARON ([1]). Metoda hledá vždy globální řešení optimalizačního problému. (cs)
  • Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm. (en)
  • El método de diseño de algoritmos ramificación y poda (también llamado ramificación y acotación) es una variante del backtracking mejorado sustancialmente. El término (del inglés, Branch and Bound) se aplica mayoritariamente para resolver cuestiones o problemas de optimización. (es)
  • Un algorithme par séparation et évaluation, ou branch and bound en anglais, est une méthode générique de résolution de problèmes d'optimisation combinatoire. Cet algorithme a été introduit par Ailsa Land et Alison Harcourt (Doig) en 1960. Cette méthode est très utilisée pour résoudre des problèmes NP-complets, c'est-à-dire des problèmes considérés comme difficiles à résoudre efficacement. (fr)
  • Il branch and bound è una tecnica generale per la risoluzione di problemi di (cioè problemi con spazio di soluzioni finito) e si basa sulla scomposizione del problema originale in sottoproblemi più semplici da risolvere. Questo metodo è stato inizialmente proposto da A. H. Land e A. G. Doig nel 1960 per risolvere problemi di programmazione lineare intera. (it)
  • Метод ветвей и границ (англ. branch and bound) — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. Метод является развитием метода полного перебора, в отличие от последнего — с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений. Метод ветвей и границ впервые предложен в 1960 году Алисой Лэнд и Элисон Дойг для решения задач целочисленного программирования. Метод используется для решения некоторых NP-полных задач, в том числе задачи коммивояжёра и задачи о ранце. (ru)
rdfs:label
  • Metoda větví a mezí (cs)
  • Branch-and-Bound (de)
  • Ramificación y poda (es)
  • Branch and bound (en)
  • Séparation et évaluation (fr)
  • Branch and bound (it)
  • 分枝限定法 (ja)
  • 분기 한정법 (ko)
  • Ramificar e limitar (pt)
  • Метод ветвей и границ (ru)
  • Метод гілок і меж (uk)
  • 分支定界 (zh)
owl:sameAs
skos:closeMatch
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:knownFor of
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License