算法合集之《用改进算法的思想解决规模维数增大的问题.ppt

用改进算法的思想解决规模维数增大的问题一、概述二、引子：从一道IQ题说起二、引子：从一道IQ题说起二、引子：从一道IQ题说起二、引子：从一道IQ题说起二、引子：从一道IQ题说起模型A.不减小每根香的计时，两根香加在一起计时是45分钟；模型A.不减小每根香的计时，两根香加在一起计时是45分钟；模型A.不减小每根香的计时，两根香加在一起计时是45分钟；模型A.不减小每根香的计时，两根香加在一起计时是45分钟；如果我们两头一起烧，用一根香就能够计时30分钟。二、引子：从一道IQ题说起二、引子：从一道IQ题说起二、引子：从一道IQ题说起二、引子：从一道IQ题说起二、引子：从一道IQ题说起二、引子：从一道IQ题说起二、引子：从一道IQ题说起二、引子：从一道IQ题说起二、引子：从一道IQ题说起三、改进算法的途径【例题】TeamSelection(BalkanOI2004Day1)如数据：〖原始算法〗枚举每一个选手X，判断X是否excellent。这可以通过另一重循环，枚举另一选手Y，判断Y是否比Xbetter。判断是容易的，我们只需要简单地判断X和Y的三次排名。〖改进一〗如果让X依照第一次竞赛的名次循环，枚举Y时只需要枚举在第一次竞赛中排在X前面选手即可。〖改进二〗如果Y不是excellent（因为有Z比Ybetter），当我们检查X是否excellent时，我们只需要检查了Z是否比Xbetter，可以不检查Y。〖原始思路小结〗这里的原始算法是直接根据原始模型模拟出来的，改进一和改进二都单纯地根据原始算法的设计缺陷来“改进”（这个改进没有利用问题的本质内容，不是本文所要阐述的“改进”），所以最后的时间复杂度没有质的进展。【降维思路】【降维思路】【降维思路】【降维思路】【降维思路】【降维思路】【降维思路】【降维思路】……Ai只要比A1A2…Ai-1任何一个大就不是Excellent【降维思路】【扩展思路】2.B[Aj]<B[Ai]〖改进五〗通过改进四，我们观察到，我们要在一个数列中找B小于某个数的元素，又要找出所有这些元素的C的最小值。【改进五的实现：优化数据结构】〖最终算法〗这样我们就能很清晰地得出优化的解法：以第一次竞赛的名次从高到低枚举X，以第二次竞赛名次为key，第三次竞赛名次为value。对于每个X，只要查询区间[1,key]的最小值min-value，若min-value<value，则有选手比Xbetter，即X不是excellent。反之，若min-value>value，说明X是excellent，并把(key,value)加入检索树。【小结】TeamSelection一题不仅很好地反映了改进算法对解决规模维数增大的问题所起的重要作用，而且还突出了数据结构的应用对解决问题的帮助。正是印证了“算法+数据结构=程序”四、总结谢谢！