Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:此题使用贪心算法正确性的证明In Reply To:此题使用贪心算法正确性的证明 Posted by:njuallen at 2015-05-31 13:12:11 > 关于这个算法的正确性的证明: > 首先,我们可以看到好多人的解决方法是给每个路径都加上一个计数器,最后这么多计数器的最大值就是结果,但计数器的最大值只是结果的下限,我们还必须说明存在一个解能达到这个下限,这个解必然就是最优解了。 > 为了证明这个贪心算法正确,我们可以证明:在计数器的最大值为N时,经过一轮贪心选互不相交区间操作之后,计数器的最大值为N-1。 > 1、所有在这一轮被选走的区间(即在这一轮移动玩的桌子)上的计数器的值必然减1。 > 2、其他区间上的计数器值不变,但其他区间上的计数器的值一定小于N。 > 假设第一轮移走的连续两个桌子占用走廊区间为[a1,a2],[b1,b2],我们要证明区间(a2,b1)上的所有计数器的值全部都小于N,不妨考察a2+1处的计数器值。 > 假设a2+1处的计数器值为N,则由于搬桌子时采取了贪心策略,且搬完桌子[a1,a2]之后,直接搬走了桌子[b1,b2],所有覆盖了a2+1的桌子并未被移动,因此覆盖a2+1处的N个桌子的区间的开始位置必然小于a2,即覆盖了a2+1的N张桌子必然同时覆盖a2。同时考虑到a2处已经被搬走了一张桌子,因此在这次搬桌子之前,a2处计数器的值为N+1,与假设矛盾!因此a2+1处的计数器的值必然小于N,同理,(a2,b1)区间上的所有计数器的值全都小于N。 > 证明完成! > 搬了一轮桌子后,计数器最大值就必然减1,因此最多搬N次桌子,所有计数器值为0,即搬完了。 > 同时,由于计数器最大值为N,意味着我们至少要搬N次,所以用此贪心算法达到的搬N次是最优结果。 > 亦即次贪心算法正确! > 证明完成! Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator