📄 branchnbound.html
字号:
<!DOCTYPE HTML PUBLIC "-//IETF//DTD W3 HTML 2.0//EN">
<HTML lang="en-US">
<HEAD>
<TITLE>branch and bound</TITLE>
<META name="description"
content="Definition of branch and bound,
possibly with links to more information and implementations.">
<META name="keywords" content="branch and bound">
</HEAD>
<BODY BGCOLOR="#FFFFFF">
<H1>branch and bound</H1>
<P>
(algorithm)
<P>
<strong>Definition:</strong>
An algorithm which finds the optimal solution by keeping the best solution found so far. If a partial solution cannot do better than the best, work on it is abandoned.
<P><strong>See also</strong>
<a href="depthfirst.html" tppabs="http://hissa.nist.gov/dads/HTML/depthfirst.html"><em>depth first search</em></a>.
<P><em>Note:
For instance, suppose we want to find the shortest route from Zarahemla to Manti. At some time shortest route found so far is 387 kilometers. If the shortest distance from Zarahemla to Cumeni is 350 km and Cumeni is 46 km from Manti in a straight line, there is no reason to explore possible roads from Cumeni: they will be at least 396 km (350 + 46), which is worse than a known route. So we need not explore paths from Cumeni. <P> This may be implemented as a <a href="backtrack.html" tppabs="http://hissa.nist.gov/dads/HTML/backtrack.html"><em>backtracking</em></a> algorithm, which is a modified <a href="depthfirst.html" tppabs="http://hissa.nist.gov/dads/HTML/depthfirst.html"><em>depth first search</em></a>, or using a <a href="priorityque.html" tppabs="http://hissa.nist.gov/dads/HTML/priorityque.html"><em>priority queue</em></a> ordering partial solutions by lower bounds (current + least possible completion), which is a <a href="bestfirst.html" tppabs="http://hissa.nist.gov/dads/HTML/bestfirst.html"><em>best first search</em></a>.</em>
<P>Author: <a href="terms.html#authorPEB" tppabs="http://hissa.nist.gov/dads/terms.html#authorPEB">PEB</a>
<H2>Implementation</H2>
A page of <A HREF="javascript:if(confirm('http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://solon.cma.univie.ac.at/%7Eneum/glopt/software_g.html%23bb_codes \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://solon.cma.univie.ac.at/%7Eneum/glopt/software_g.html%23bb_codes'" tppabs="http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://solon.cma.univie.ac.at/%7Eneum/glopt/software_g.html%23bb_codes">branch and bound implementations (C, C++, Matlab, Fortran, executables, etc.)</A>.
<H2>More information</H2>
A more formal and complete <A HREF="javascript:if(confirm('http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.cs.sandia.gov/opt/survey/branch-and-bound.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.cs.sandia.gov/opt/survey/branch-and-bound.html'" tppabs="http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.cs.sandia.gov/opt/survey/branch-and-bound.html">explanation</A> and a <A HREF="javascript:if(confirm('http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.ers.com/publications/html/sld0124.htm \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.ers.com/publications/html/sld0124.htm'" tppabs="http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.ers.com/publications/html/sld0124.htm">diagram of execution</A>.
<hr>
Go to the
<A HREF="terms.html" tppabs="http://hissa.nist.gov/dads/terms.html">Algorithms, Data Structures, and Problems</A>
home page.
<hr>
If you have suggestions, corrections, or comments, please get in touch
with
<a href="javascript:if(confirm('http://hissa.nist.gov/~black/black.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://hissa.nist.gov/~black/black.html'" tppabs="http://hissa.nist.gov/~black/black.html">Paul E. Black</a>
(<a href="mailto:paul.black@nist.gov">paul.black@nist.gov</a>).
<p>
Entry modified Tue Jan 26 09:07:25 1999.<BR>
HTML page formatted Wed Dec 22 09:34:52 1999.
<P>
This page's URL is
<A href="branchNbound.html" tppabs="http://hissa.nist.gov/dads/HTML/branchNbound.html">http://hissa.nist.gov/dads/HTML/branchNbound.html</A>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -