📄 page443.html
字号:
<HTML><HEAD><TITLE>Depth-First Solver</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="tex2html6278" HREF="page444.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6276" HREF="page442.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6270" HREF="page442.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6280" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0014231000000000000000">Depth-First Solver</A></H3><P>This section presents a backtracking solverthat finds the best solution to a given problem byperforming depth-first traversal of the solution space.Program <A HREF="page443.html#progdepthFirstSolvera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the <tt>DepthFirstSolver</tt> class.The <tt>DepthFirstSolver</tt> class extendsthe abstract <tt>Solver</tt> classdefined in Program <A HREF="page442.html#progsolvera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.It provides an implementation for the <tt>search</tt> method.<P><P><A NAME="33422"> </A><A NAME="progdepthFirstSolvera"> </A> <IMG WIDTH=575 HEIGHT=219 ALIGN=BOTTOM ALT="program32535" SRC="img1732.gif" ><BR><STRONG>Program:</STRONG> <tt>DepthFirstSolver</tt> class <tt>__init__</tt> and <tt>search</tt> methods.<BR><P><P>The <tt>search</tt> method does a complete,depth-first traversal of the solution space.<A NAME="tex2html800" HREF="footnode.html#33426"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A>Note that the implementation does not depend uponthe characteristics of the problem being solved.In this sense the solver is a generic, <em>abstract solver</em>and can be used to solve any problem that has a tree-structured solution space!<P>Since the <tt>search</tt> method in Program <A HREF="page443.html#progdepthFirstSolvera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>visits all the nodes in the solution space,it is essentially a <em>brute-force</em> algorithm.And because the recursive method backs upand then tries different alternatives,it is called a <em>backtracking</em> algorithm.<P><HR><A NAME="tex2html6278" HREF="page444.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6276" HREF="page442.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6270" HREF="page442.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6280" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -