page462.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 130 行
HTML
130 行
<HTML><HEAD><TITLE>Example</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="tex2html6490" HREF="page463.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6488" HREF="page461.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6482" HREF="page461.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6492" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0014431000000000000000">Example</A></H3><P>Suppose we are given a sequence of <I>n</I>=5 words, <IMG WIDTH=174 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68355" SRC="img1871.gif" > having lengths <IMG WIDTH=123 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68357" SRC="img1872.gif" >, respectively,which are to be typeset in a paragraph of width <I>D</I>=60.Assume that the normal width of an inter-word space is <I>s</I>=10.<P>We begin by computing the lengths of all the subsequences of <I>W</I>using Equation <A HREF="page461.html#eqnalgslength"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The lengths of all <I>n</I>(<I>n</I>-1)/2 subsequences of <I>W</I>are tabulated in Table <A HREF="page462.html#tblalgsproblem"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="33310"> </A><P> <A NAME="tblalgsproblem"> </A> <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=7 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=5> <IMG WIDTH=25 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68303" SRC="img1861.gif" ></TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><P> <I>i</I></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=9 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68373" SRC="img1873.gif" ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><I>j</I>=1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 5 </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 20 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 30 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 42 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 92 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 20 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 32 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 82 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 22 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 72 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 12 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 12 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 62 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 50 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 50 </TD></TR></TBODY><CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Typesetting problem.</CAPTION></TABLE></P></DIV><P><P>Given <IMG WIDTH=25 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68303" SRC="img1861.gif" >, <I>D</I>, and <I>s</I>,it is a simple matter to apply <IMG WIDTH=107 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68383" SRC="img1874.gif" >to obtain the one-line penalties, <IMG WIDTH=23 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68329" SRC="img1866.gif" >,which measure the amount of stretching or compressing neededto set all the words in a given subsequence on a single line.These are tabulated in Table <A HREF="page462.html#tblalgssolution"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="33327"> </A><P> <A NAME="tblalgssolution"> </A> <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=11 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=5> <IMG WIDTH=23 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68329" SRC="img1866.gif" ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=5> <IMG WIDTH=24 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68121" SRC="img1817.gif" ></TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><P> <I>i</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><I>j</I>=1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><I>j</I>=1</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 5 </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 50 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 30 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 12 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=14 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline68397" SRC="img1875.gif" ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 50 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 30 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 12 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 22 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 50 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 30 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 8 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=14 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline68397" SRC="img1875.gif" ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 50 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 30 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 8 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 18 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 50 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 28 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=14 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline68397" SRC="img1875.gif" ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 50 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 28 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 38 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 48 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=14 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline68397" SRC="img1875.gif" ></TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 48 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 58 </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 10 </TD></TR></TBODY><CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Penalties.</CAPTION></TABLE></P></DIV><P><P>Given the one-line penalties <IMG WIDTH=23 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68329" SRC="img1866.gif" >,we can use Equation <A HREF="page461.html#eqnalgscost"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> to find for each subsequence of <I>W</I>the minimum total penalty, <IMG WIDTH=24 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68121" SRC="img1817.gif" >,associated with forming a paragraph from the words in that subsequence.These are tabulated in Table <A HREF="page462.html#tblalgssolution"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P>The <IMG WIDTH=26 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline68411" SRC="img1876.gif" > entry in Table <A HREF="page462.html#tblalgssolution"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the minimum totalcost of typesetting the entire paragraph.The value 22 was obtained as follows:<P> <IMG WIDTH=500 HEIGHT=62 ALIGN=BOTTOM ALT="eqnarray33349" SRC="img1877.gif" ><P>This indicates that the optimal solution is to set words <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline67799" SRC="img1726.gif" >, <IMG WIDTH=17 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68417" SRC="img1878.gif" >, <IMG WIDTH=18 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68419" SRC="img1879.gif" >, and <IMG WIDTH=17 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68421" SRC="img1880.gif" > on the first line of the paragraphand leave <IMG WIDTH=18 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68423" SRC="img1881.gif" > by itself on the last line of the paragraph.Figure <A HREF="page462.html#figparagraph"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates this result.<P><P><A NAME="33706"> </A><A NAME="figparagraph"> </A> <IMG WIDTH=575 HEIGHT=305 ALIGN=BOTTOM ALT="figure33364" SRC="img1882.gif" ><BR><STRONG>Figure:</STRONG> Typesetting a paragraph.<BR><P><P>This formulation of the typesetting problem seems like overkill.Why not just typeset the lines of text one-by-one,minimizing the penalty for each line as we go?In other words why don't we just use a greedy strategy?Unfortunately, the obvious greedy solution strategy <em>does not work</em>!<P>For example,the greedy strategy begins by setting the first line of text.To do so it must decide how many words to put on that line.The obvious thing to do is to select the value of <I>k</I>for which <IMG WIDTH=27 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68461" SRC="img1883.gif" > is the smallest.From Table <A HREF="page462.html#tblalgssolution"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>we see that <IMG WIDTH=65 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68463" SRC="img1884.gif" > has the smallest penalty.Therefore, the greedy approach puts three words on the first lineas shown in Figure <A HREF="page462.html#figparagraph"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P>Since the remaining two words do not both fit on a single line,they are set on separate lines.The total of the penalties for the paragraph typeset using the greedyalgorithm is <IMG WIDTH=159 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68465" SRC="img1885.gif" >.Clearly, the solution is not optimal(nor is it very pleasing esthetically).<P><HR><A NAME="tex2html6490" HREF="page463.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6488" HREF="page461.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6482" HREF="page461.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6492" 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 + -
显示快捷键?