page440.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 91 行
HTML
91 行
<HTML><HEAD><TITLE>Example-Balancing Scales</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="tex2html6243" HREF="page441.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6241" HREF="page439.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6235" HREF="page439.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6245" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0014210000000000000000">Example-Balancing Scales</A></H2><A NAME="secalgsscales"> </A><P>Consider the set of <em>scales</em><A NAME=32185> </A> shown in Figure <A HREF="page440.html#figscales1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Suppose we are given a collection of <I>n</I> weights, <IMG WIDTH=114 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67693" SRC="img1714.gif" >,and we are required to place <em>all</em> of the weightsonto the scales so that they are balanced.<P><P><A NAME="32215"> </A><A NAME="figscales1"> </A> <IMG WIDTH=575 HEIGHT=155 ALIGN=BOTTOM ALT="figure32188" SRC="img1719.gif" ><BR><STRONG>Figure:</STRONG> A set of scales.<BR><P><P>The problem can be expressed mathematically as follows:Let <IMG WIDTH=14 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline67687" SRC="img1713.gif" > represent the pan in which weight <IMG WIDTH=15 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline67677" SRC="img1712.gif" > is placedsuch that<P> <IMG WIDTH=386 HEIGHT=48 ALIGN=BOTTOM ALT="displaymath67713" SRC="img1720.gif" ><P>The scales are balanced whenthe sum of the weights in the left pan equalsthe sum of the weights in the right pan,<P> <IMG WIDTH=338 HEIGHT=44 ALIGN=BOTTOM ALT="displaymath67714" SRC="img1721.gif" ><P><P>Given an arbitrary set of <I>n</I> weights,there is no guarantee that a solution to the problem exists.A solution always exists if, instead of balancing the scales,the goal is to minimize the difference between between the total weightsin the left and right pans.Thus, given <IMG WIDTH=114 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67693" SRC="img1714.gif" >,our <em>objective</em> is to <em>minimize</em> <IMG WIDTH=7 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline67735" SRC="img1722.gif" > where<P> <IMG WIDTH=355 HEIGHT=49 ALIGN=BOTTOM ALT="displaymath67715" SRC="img1723.gif" ><P>subject to the constraint that <em>all</em>the weights are placed on the scales.<P>Given a set of scales and collection of weights,we might solve the problem by trial-and-error:Place all the weights onto the pans one-by-one.If the scales balance, a solution has been found.If not, remove some number of the weightsand place them back on the scales in some other combination.In effect, we search for a solution to the problem byfirst trying one solution and then backing-up to try another.<P>Figure <A HREF="page440.html#figscales2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows the <em>solution space</em><A NAME=32234> </A>for the scales balancing problem.In this case the solution space takes the form of a tree:Each node of the tree represents a <em>partial solution</em> to the problem.At the root (node A)no weights have been placed yet and the scales are balanced.Let <IMG WIDTH=7 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline67735" SRC="img1722.gif" > be the difference between thethe sum of the weights currently placed in the left and right pans.Therefore, <IMG WIDTH=37 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline67739" SRC="img1724.gif" > at node A.<P><P><A NAME="32430"> </A><A NAME="figscales2"> </A> <IMG WIDTH=575 HEIGHT=239 ALIGN=BOTTOM ALT="figure32236" SRC="img1725.gif" ><BR><STRONG>Figure:</STRONG> Solution space for the scales balancing problem.<BR><P><P>Node B represents the situation in which weight <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline67799" SRC="img1726.gif" > has been placedin the left pan.The difference between the pans is <IMG WIDTH=58 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67801" SRC="img1727.gif" >.Conversely, node C represents the situation in which the weight <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline67799" SRC="img1726.gif" >has been placed in the right pan.In this case <IMG WIDTH=58 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67805" SRC="img1728.gif" >.The complete solution tree has depth <I>n</I> and <IMG WIDTH=15 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline60291" SRC="img558.gif" > leaves.Clearly, the solution is the leaf node having the smallest <IMG WIDTH=15 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67811" SRC="img1729.gif" > value.<P>In this case (as in many others) the solution space is a tree.In order to find the best solutiona backtracking algorithm visits all the nodes in the solution space.That is, it does a tree <em>traversal</em><A NAME=32434> </A>.Section <A HREF="page258.html#sectreestraversals"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> presents the two mostimportant tree traversals--<em>depth-first</em><A NAME=32437> </A>and <em>breadth-first</em><A NAME=32439> </A>.Both kinds can be used to implement a backtracking algorithm.<P><HR><A NAME="tex2html6243" HREF="page441.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6241" HREF="page439.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6235" HREF="page439.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6245" 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 + -
显示快捷键?