📄 page444.html
字号:
<HTML><HEAD><TITLE>Breadth-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="tex2html6287" HREF="page445.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6285" HREF="page442.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6281" HREF="page443.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6289" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0014232000000000000000">Breadth-First Solver</A></H3><P>If we can find the optimal solutionby doing a depth-first traversal of the solution space,then we can find the solution with a breadth-first traversal too.As defined in Section <A HREF="page258.html#sectreestraversals"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,a breadth-first traversal of a tree visits the nodesin the order of their depth in the tree.That is, first the root is visited,then the children of the root are visited,then the grandchildren are visited, and so on.<P>The <tt>BreadthFirstSolver</tt> class is definedin Program <A HREF="page444.html#progbreadthFirstSolvera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The <tt>BreadthFirstSolver</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 simply provides an implementation for the <tt>search</tt> method.<P><P><A NAME="33427"> </A><A NAME="progbreadthFirstSolvera"> </A> <IMG WIDTH=575 HEIGHT=298 ALIGN=BOTTOM ALT="program32565" SRC="img1733.gif" ><BR><STRONG>Program:</STRONG> <tt>BreadthFirstSolver</tt> class <tt>__init__</tt> and <tt>search</tt> methods.<BR><P><P>The <tt>search</tt> method implements a non-recursive,breadth-first traversal algorithmthat uses a queue to keep track of nodes to be visited.The initial solution is enqueued first.Then the following steps are repeated until the queue is empty:<OL><LI> Dequeue the first solution in the queue.<LI> If the solution is complete, call the <tt>updateBest</tt> method to keep track of the solution which minimizes the objective function.<LI> Otherwise the solution is not complete. Enqueue all its successors.</OL>Clearly, this algorithm does a complete traversalof the solution space.<A NAME="tex2html802" HREF="footnode.html#33431"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A><P><HR><A NAME="tex2html6287" HREF="page445.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6285" HREF="page442.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6281" HREF="page443.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6289" 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 + -