page441.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 80 行
HTML
80 行
<HTML><HEAD><TITLE>Representing the Solution Space</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html6254" HREF="page442.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6252" HREF="page439.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6246" HREF="page440.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6256" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0014220000000000000000">Representing the Solution Space</A></H2><P>This section presents an abstract classto represent the nodes of a solution space.By using an abstract class,we hide the details of the specific problem to be solvedfrom the backtracking algorithm.In so doing, it is possible to implement completelygeneric backtracking problem solvers.<P>Although a backtracking algorithm behavesas if it is traversing a solution tree,it is important to realize that it is not necessary to havethe entire solution tree constructed at once.Instead, the backtracking algorithm creates and destroysthe nodes dynamically as it explores the solution space.<P>Program <A HREF="page441.html#progsolutiona"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the <tt>Solution</tt> class.The abstract <tt>Solution</tt> classextends the abstract <tt>Object</tt> classintroduced in Program <A HREF="page116.html#progobjecta"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Each instance of a class derived from the<tt>Solution</tt> class represents a single nodein the solution space.<P><P><A NAME="33406"> </A><A NAME="progsolutiona"> </A> <IMG WIDTH=575 HEIGHT=757 ALIGN=BOTTOM ALT="program32447" SRC="img1730.gif" ><BR><STRONG>Program:</STRONG> Abstract <tt>Solution</tt> class.<BR><P><P>The abstract <tt>Solution</tt> class comprises the following properties:<DL ><DT><STRONG><tt>isFeasible</tt></STRONG><DD> This property returns <tt>True</tt> if the solution instance is a feasible solution to the given problem. A solution is feasible if it satisfies the problem constraints. <DT><STRONG><tt>isComplete</tt></STRONG><DD> This property returns <tt>True</tt> if the solution instance represents a complete solution. A solution is complete when all possible decisions have been made. <DT><STRONG><tt>objective</tt></STRONG><DD> This property returns the value of the objective function for the given solution instance. <DT><STRONG><tt>bound</tt></STRONG><DD> This property returns a value that is a lower bound (if it exists) on the objective function for the given solution instance as well as all the solutions that can possibly be derived from that instance. This is a hook provided to facilitate the implementation of <em>branch-and-bound</em> backtracking which is described in Section <A HREF="page445.html#secalgsbandb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>. <DT><STRONG><tt>successors</tt></STRONG><DD> This property returns an iterator that enumerates all of the successors (i.e., the children) of the given solution instance. It is assumed that the children of the given node are created <em>dynamically</em>.<P> </DL><HR><A NAME="tex2html6254" HREF="page442.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6252" HREF="page439.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6246" HREF="page440.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6256" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?