page469.html

wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq

	    <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_inline69187" SRC="img1984.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1984.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_inline69187" SRC="img1984.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1984.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_inline69187" SRC="img1984.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1984.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_inline69187" SRC="img1984.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1984.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=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69119" SRC="img1975.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1975.gif"  >,
we can use Equation&nbsp;<A HREF="page468.html#eqnalgscost" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page468.html#eqnalgscost"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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_inline68911" SRC="img1926.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1926.gif"  >,
associated forming a paragraph from the words in that subsequence.
These are tabulated in Table&nbsp;<A HREF="page469.html#tblalgssolution" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page469.html#tblalgssolution"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
<P>
The  <IMG WIDTH=27 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69201" SRC="img1985.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1985.gif"  > entry in Table&nbsp;<A HREF="page469.html#tblalgssolution" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page469.html#tblalgssolution"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> gives the minimum total
cost of typesetting the entire paragraph.
The value 22 was obtained as follows:
<P> <IMG WIDTH=500 HEIGHT=63 ALIGN=BOTTOM ALT="eqnarray33538" SRC="img1986.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1986.gif"  ><P>
This indicates that the optimal solution is to set words 
 <IMG WIDTH=17 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline68589" SRC="img1832.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1832.gif"  >,  <IMG WIDTH=18 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline69207" SRC="img1987.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1987.gif"  >,  <IMG WIDTH=17 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline69209" SRC="img1988.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1988.gif"  > and  <IMG WIDTH=18 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline69211" SRC="img1989.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1989.gif"  > on the first line of the paragraph
and leave  <IMG WIDTH=17 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline69213" SRC="img1990.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1990.gif"  > by itself on  the last line of the paragraph.
Figure&nbsp;<A HREF="page469.html#figparagraph" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page469.html#figparagraph"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> illustrates this result.
<P>
<P><A NAME="33896">&#160;</A><A NAME="figparagraph">&#160;</A> <IMG WIDTH=575 HEIGHT=301 ALIGN=BOTTOM ALT="figure33553" SRC="img1991.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1991.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=26 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69251" SRC="img1992.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1992.gif"  > is the smallest.
From Table&nbsp;<A HREF="page469.html#tblalgssolution" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page469.html#tblalgssolution"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
we see that  <IMG WIDTH=63 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69253" SRC="img1993.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1993.gif"  > has the smallest penalty.
Therefore, the greedy approach puts three words on the first line
as shown in Figure&nbsp;<A HREF="page469.html#figparagraph" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page469.html#figparagraph"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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 greedy
algorithm is  <IMG WIDTH=157 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69255" SRC="img1994.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1994.gif"  >.
Clearly, the solution is not optimal
(nor is it very pleasing esthetically).
<P>
<HR><A NAME="tex2html7715" HREF="page470.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page470.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html7713" HREF="page468.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page468.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html7707" HREF="page468.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page468.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html7717" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html7718" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright &#169; 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.

</ADDRESS>
</BODY>
</HTML>