<HTML><HEAD>
<TITLE>Structures, Algorithm Analysis: CHAPTER 10: ALGORITHM DESIGN TECHNIQUE</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap11.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="chap9.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="01d1_0001">CHAPTER 10: ALGORITHM DESIGN TECHNIQUES<a name="01d1_0001"></h1><P>
So far, we have been concerned with the efficient implementation of algorithms. We have seen that when an algorithm is given, the actual data structures need not be specified. It is up to the programmer to choose the approriate data structure in order to make the running time as small as possible.<P>
In this chapter, we switch our attention from the <I>implementation</I> of algorithms to the <I>design</I> of algorithms. Most of the algorithms that we have seen so far are straightforward and simple. <A ="algo01b4.htm#01B4_02AD">Chapter 9</A> contains some algorithms that are much more subtle, and some require an argument (in some cases lengthy) to show that they are indeed correct. In this chapter, we will focus on five of the common types of algorithms used to solve problems. For many problems, it is quite likely that at least one of these methods will work. Specifically, for each type of algorithm we will<P>
<img src="../images/dot12.gif"> See the general approach.<P>
<img src="../images/dot12.gif"> Look at several examples (the exercises at the end of the chapter provide many more examples).<P>
<img src="../images/dot12.gif"> Discuss, in general terms, the time and space complexity, where appropriate.<P>
<P>
<h1><a name="01d3_0391">10.1. Greedy Algorithms<a name="01d3_0391"></h1><P>
<a name="01d3_038d"><a name="01d3_038e">The first type of algorithm we will examine is the <I>greedy algorithm</I>. We have already seen three greedy algorithms in Chapter 9: Dijkstra's, Prim's, and Kruskal's algorithms. Greedy algorithms work in phases. In each phase, a decision is made that appears to be good, without regard for future consequences. Generally, this means that some <I>local</I> <I>optimum</I> is chosen. This "take what you can get now" strategy is the source of the name for this class of algorithms. When the algorithm terminates, we hope that the local optimum is equal to the <I>global optimum</I>. If this is the case, then the algorithm is correct; otherwise, the algorithm has produced a suboptimal solution. If the absolute best answer is not required, then simple greedy algorithms are sometimes used to generate approximate answers, rather than using the more complicated algorithms generally required to generate an exact answer. <P>
<a name="01d3_038f"><a name="01d3_0390">There are several real-life examples of greedy algorithms. The most obvious is the coin-changing problem. To make change in U.S. currency, we repeatedly dispense the largest denomination. Thus, to give out seventeen dollars and sixty-one cents in change, we give out a ten-dollar bill, a five-dollar bill, two one-dollar bills, two quarters, one dime, and one penny. By doing this, we are guaranteed to minimize the number of bills and coins. This algorithm does not work in all monetary systems, but fortunately, we can prove that it does work in the American monetary system. Indeed, it works even if two-dollar bills and fifty-cent pieces are allowed.<P>
Traffic problems provide an example where making locally optimal choices does not always work. For example, during certain rush hour times in Miami, it is best to stay off the prime streets even if they look empty, because traffic will come to a standstill a mile down the road, and you will be stuck. Even more shocking, it is better in some cases to make a temporary detour in the direction opposite your destination in order to avoid all traffic bottlenecks.<P>
In the remainder of this section, we will look at several applications that use greedy algorithms. The first application is a simple scheduling problem. Virtually all scheduling problems are either <I>NP</I>-complete (or of similar difficult complexity) or are solvable by a greedy algorithm. The second application deals with file compression and is one of the earliest results in computer science. Finally, we will look at an example of a greedy approximation algorithm.<P>
<P>
<h2><a name="01d4_0394">10.1.1. A Simple Scheduling Problem<a name="01d4_0394"></h2><P>
<a name="01d4_0391"><a name="01d4_0392"><a name="01d4_0393">We are given jobs <I>j</I><SUB>1</SUB>, <I>j</I><SUB>2</SUB>, . . . , <I>j<SUB>n</I></SUB>, all with known running times <I>t</I><SUB>1</SUB>, <I>t</I><SUB>2</SUB>, . . . , <I>t<SUB>n</I></SUB>, respectively. We have a single processor. What is the best way to schedule these jobs in order to minimize the average completion time? In this entire section, we will assume <I>nonpreemptive scheduling</I>: Once a job is started, it must run to completion.<P>
As an example, suppose we have the four jobs and associated running times shown in <A ="algo01d4.htm#01D4_0397">Figure 10.1</A>. One possible schedule is shown in <A ="algo01d4.htm#01D4_0398">Figure 10.2</A>. Because <I>j</I><SUB>1</SUB> finishes in 15 (time units), <I>j</I><SUB>2</SUB> in 23, <I>j</I><SUB>3</SUB> in 26, and <I>j</I><SUB>4</SUB> in 36, the average completion time is 25. A better schedule, which yields a mean completion time of 17.75, is shown in <A ="algo01d4.htm#01D4_0399">Figure 10.3</A>.<P>
The schedule given in <A ="algo01d4.htm#01D4_0399">Figure 10.3</A> is arranged by shortest job first. We can show that this will always yield an optimal schedule. Let the jobs in the schedule be <I>j<SUB>i</I>1</SUB>, <I>j<SUB>i</I>2</SUB>, . . . , <I>j<SUB>in</I></SUB>. The first job finishes in time <I>t<SUB>i</I>1</SUB>. The second job finishes after <I>t<SUB>i</I>1</SUB> + <I>t<SUB>i</I>2</SUB>, and the third job finishes after <I>t<SUB>i</I>1</SUB> + <I>t<SUB>i</I>2</SUB> + <I>t<SUB>i</I>3</SUB>. From this, we see that the total cost, C, of the schedule is<P>
<img src="346_a.gif"><P>
<h4><a name="01d4_0395">(10.1)<a name="01d4_0395"></h4><P>
<img src="346_b.gif"><P>
<h4><a name="01d4_0396">(10.2)<a name="01d4_0396"></h4><P>
<pre>Job Time</sub></pre><P>
<pre>---------</sub></pre><P>
<pre><I> j</I><SUB>1 15</SUB> </sub></pre><P>
<pre><I> j</I><SUB>2 8</SUB> </sub></pre><P>
<pre><I> j</I><SUB>3 3</SUB> </sub></pre><P>
<pre><I> j</I><SUB>4 10</SUB> </sub></pre><P>
</sub>
</sub></pre>
</font>
<h4><a name="01d4_0397">Figure 10.1 Jobs and times<a name="01d4_0397"></h4><P>
<img src="347_a.gif"><P>
<h4><a name="01d4_0398">Figure 10.2 Schedule #1<a name="01d4_0398"></h4><P>
<img src="347_b.gif"><P>
<h4><a name="01d4_0399">Figure 10.3 Schedule #2 (optimal)<a name="01d4_0399"></h4><P>
Notice that in <A ="algo01d4.htm#01D4_0396">Equation (10.2)</A>, the first sum is independent of the job ordering, so only the second sum affects the total cost. Suppose that in an ordering there exists some <I>x</I> > <I>y</I> such that <I>t<SUB>ix</I></SUB> < <I>t<SUB>iy</I></SUB>. Then a calculation shows that by swapping <I>j<SUB>ix</I></SUB> and <I>j<SUB>iy</I></SUB>, the second sum increases, decreasing the total cost. Thus, any schedule of jobs in which the times are not monotonically nonincreasing must be suboptimal. The only schedules left are those in which the jobs are arranged by smallest running time first, breaking ties arbitrarily.<P>
This result indicates the reason the operating system scheduler generally gives precedence to shorter jobs.<P>
<P>
<h3>The Multiprocessor Case</h3><P>
We can extend this problem to the case of several processors. Again we have jobs <I>j</I><SUB>1</SUB>, <I>j</I><SUB>2</SUB>, . . . , <I>j<SUB>n</I></SUB>, with associated running times <I>t</I><SUB>1</SUB>, <I>t</I><SUB>2</SUB>, . . . , <I>
Data.Structures.And.Algorithm.Analysis.In.C.1992.
需积分: 12 93 浏览量
2007-05-06
11:17:36
上传
评论 1
收藏 2.41MB RAR 举报
Data.Structures.And.Algorithm.Analysis.In.C.1992. （599个子文件） 
298_a.gif 26KB 387_c.gif 24KB 79_a.gif 23KB 56_a.gif 21KB 375_a.gif 21KB 372_a.gif 20KB 160_b.gif 18KB 157_a.gif 17KB 186_a.gif 17KB 164_a.gif 17KB 170_a.gif 14KB 250box2.gif 13KB 106_a.gif 13KB 250box3.gif 13KB 250box1.gif 13KB 285_a.gif 13KB 397_c.gif 12KB 169_a.gif 12KB 410_b.gif 12KB 249box2.gif 12KB 249box1.gif 12KB 249box3.gif 12KB 417_a.gif 12KB 249box4.gif 12KB 411_a.gif 11KB 245_a.gif 11KB 363_a.gif 11KB 109_a.gif 11KB 316_a.gif 11KB 248box1.gif 10KB 313_a.gif 10KB 284_a.gif 10KB 212_a.gif 10KB 136_b.gif 10KB 439_a.gif 9KB 168_a.gif 9KB 188_b.gif 9KB 188_a.gif 9KB 187_a.gif 9KB 133_a.gif 9KB 388_a.gif 9KB 188_c.gif 9KB 78_b.gif 8KB 233_a.gif 8KB 20_b.gif 8KB 106_b.gif 8KB 330_a.gif 8KB 268_a.gif 8KB 334_a.gif 8KB 359_a.gif 8KB 310_a.gif 8KB 336_a.gif 8KB 273_a.gif 8KB 309_c.gif 7KB 122_a.gif 7KB 312_a.gif 7KB 307_a.gif 7KB 203_a.gif 7KB 305_d.gif 7KB 53_a.gif 7KB 358_a.gif 7KB 308_a.gif 7KB 150_a.gif 7KB 396_c.gif 7KB 166_b.gif 7KB 227_d.gif 7KB 92_a.gif 7KB 328_a.gif 7KB 160_a.gif 7KB 359_g.gif 7KB 309_b.gif 7KB 182_a.gif 7KB 153_a.gif 7KB 305_b.gif 7KB 182_b.gif 7KB 309_a.gif 7KB 20_a.gif 7KB 305_c.gif 7KB 308_b.gif 7KB 305_a.gif 7KB 444_a.gif 7KB 303_a.gif 7KB 357_a.gif 7KB 25_d.gif 7KB 208_b.gif 7KB 184_a.gif 6KB 396_d.gif 6KB 338_a.gif 6KB 184_b.gif 6KB 340_a.gif 6KB 181_c.gif 6KB 184_c.gif 6KB 410_a.gif 6KB 360_a.gif 6KB 208_a.gif 6KB 380_e.gif 6KB 214_a.gif 6KB 403_a.gif 6KB 198_a.gif 6KB 396_b.gif 6KB共 599 条
- 1
- 2
- 3
- 4
- 5
- 6
资源评论
