算法课件资料第4章贪心算法课堂练习.doc

《算法课件资料第4章贪心算法课堂练习.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章贪心算法课堂练习【照亮的山景】问题描述：在一片山的上空，高度为T处有N个处于同一水平位置的灯泡，如图所示，如果山的边界上某一点与某灯i的连线不经过山上的其他点，我们称灯i可以照亮该点。已知山体所有转折点X[1]…X[M]，及灯的高度T，设计一个算法，在高度T的水平线上，如何放置尽量少的灯(灯的个数为N)，使得某个山景都被照亮。解：本题的几何味较浓，山被表示为有M个转折点的折线，因此很容易想到把照亮整个山景的问题转化为照亮这M个折点（因为照亮M个折点就一定能照到整个山景）。顺着这个思路，接下来我们考察每个灯的照射范围。发现一个另人头痛的问题：灯的照射范围是多区间的！如灯B1

2、可以照射折点[X1,X2]+[X4]+[X8]。换一个角度出发，考虑每个顶点能被哪些灯照到。发现：如果两盏灯可以照射到同一个顶点i，则两盏灯之间的所有灯也能照到顶点i，即，能照射到一个点的所有灯形成一个连续的区间[l[i],r[i]]，其中l[i]和r[i]分别代表能照到顶点i的最左边的灯和最右边的灯。现在我们的问题变成：给M个区间，选出尽量少的点使得每个区间至少有一个点被选出。为了研究方便，首先把包含某其它区间的大区间去掉（因为只要满足了小区间，则包含它的大区间一定满足，大区间除去），然后将所有区间按照起始位置从小到大排序，这样，所有区间的终止位置严格递增（因为之前已经除去了

3、大区间，区间之间不会相互包含）。例如，上图X1～X9这9个折点的区间都可计算出来，比如：照耀X1点的[－∞,A0]，照耀X3点的[A1,A2]，照耀X5点的[A3,A4]，照耀X6点的[A5,A6]、照耀X7点的[A7,A8]和照耀X9点的[A9,＋∞]。去掉包含其它区间的区间，剩下四个区间：照耀X1点的[－∞,A0]，照耀X3点的[A1,A2]，照耀X7点的[A7,A8]和照耀X9点的[A9,＋∞]。按区间起始位置排序（或终止位置排序，这是同理的），排序后为：[－∞,A0]、[A1,A2]、[A7,A8]、[A9,＋∞]。下面要分析的就是从左往右扫描排序后的每个区间，检查是否

4、需要选取一个点作为灯安置的位置。那么对于第一个区间应该选取哪个点呢？直觉告诉我们，应该选取第一个区间的最后一个点，因为这样能够“让较多其它的区间得到条件的满足”。这个结论是正确的。因为对于任何一个”选取点最少“的最优解，如果第一个区间不是选最后一个点，把哪个点换成最后一个点之后，本区间得到满足，而且还可能时之后的其它区间得到满足。因此选取最后一个点是最优的。因此：从前往后扫描排序后的每个区间，如果它上面还没有点被取出，则选它的最后一个点作为灯的安置位置。对于此题只有放置两个灯即可，这两个灯放置在A0和A8处。