page449.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 82 行
HTML
82 行
<HTML>
<HEAD>
<TITLE>Abstract Backtracking Solvers</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html7470" HREF="page450.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page450.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html7468" HREF="page446.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page446.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html7462" HREF="page448.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page448.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html7472" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html7473" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H2><A NAME="SECTION0015230000000000000000">Abstract Backtracking Solvers</A></H2>
<P>
The usual way to implement a backtracking algorithm
is to write a function or procedure which traverses the solution space.
This section presents an alternate, object-oriented approach
that is based on the notion of an
<em>abstract solver</em><A NAME=32658> </A><A NAME=32659> </A>.
<P>
Think of a solver as an abstract machine,
the sole purpose of which is to search a given solution space
for the best possible solution.
A machine is an object.
Therefore, it makes sense that
we represent it as an instance of some class.
<P>
Program <A HREF="page449.html#progsolution2h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page449.html#progsolution2h"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> declares the abstract class <tt>Solver</tt>.
The public interface of this class consists
of the single function <tt>Solve</tt>.
This function takes as its lone argument
a reference to a <tt>Solution</tt> instance that is the node
in the solution space from which to begin the search.
The <tt>Solve</tt> function returns a reference to the
to the best solution found.
<P>
<P><A NAME="33603"> </A><A NAME="progsolution2h"> </A> <IMG WIDTH=575 HEIGHT=200 ALIGN=BOTTOM ALT="program32665" SRC="img1837.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1837.gif" ><BR>
<STRONG>Program:</STRONG> <tt>Solver</tt> Class Definition<BR>
<P>
<P>
Program <A HREF="page449.html#progsolution2h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page449.html#progsolution2h"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> also declares two protected member variables,
<tt>bestSolution</tt> and <tt>bestObjective</tt>,
and two protected member functions,
<tt>UpdateBest</tt> and <tt>DoSolve</tt>.
Since <tt>DoSolve</tt> is a pure virtual function,
its implementation must be given in a derived class.
Program <A HREF="page449.html#progsolution1c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page449.html#progsolution1c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> gives the implementations
for <tt>Solve</tt> and <tt>UpdateBest</tt>.
<P>
<P><A NAME="33608"> </A><A NAME="progsolution1c"> </A> <IMG WIDTH=575 HEIGHT=391 ALIGN=BOTTOM ALT="program32687" SRC="img1838.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1838.gif" ><BR>
<STRONG>Program:</STRONG> <tt>Solver</tt> Class <tt>Solve</tt> and <tt>UpdateBest</tt> Member Function Definitions<BR>
<P>
<P>
The <tt>Solve</tt> function does not search the solution space itself.
It is the <tt>DoSolve</tt> routine,
which is provided by a derived class,
that does the actual searching.
The <tt>Solve</tt> routine merely sets things up for <tt>DoSolve</tt>.
When <tt>DoSolve</tt> returns it is expected that the
<tt>bestSolution</tt> variable will point to the best solution
and that <tt>bestObjective</tt> will be the value of the objective
function for the best solution.
In this case,
it is assumed that the goal is to <em>minimize</em> the objective function.
<P>
The <tt>UpdateBest</tt> function
is meant to be called by the <tt>DoSolve</tt> routine
as it explores the solution space.
As each complete solution is encountered,
the <tt>UpdateBest</tt> routine is called to keep track
of the solution which minimizes the objective function.
<P>
<BR> <HR>
<UL>
<LI> <A NAME="tex2html7474" HREF="page450.html#SECTION0015231000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page450.html#SECTION0015231000000000000000">Depth-First Solver</A>
<LI> <A NAME="tex2html7475" HREF="page451.html#SECTION0015232000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page451.html#SECTION0015232000000000000000">Breadth-First Solver</A>
</UL>
<HR><A NAME="tex2html7470" HREF="page450.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page450.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html7468" HREF="page446.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page446.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html7462" HREF="page448.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page448.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html7472" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html7473" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.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://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.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://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?