毕业半年，借复旦学报/复旦招生网的人气，也收到了差不多两位数本科低年级学弟学妹的咨询邮件，甚至高三小朋友的邮件。很多小朋友都在请教，怎么做研究，怎么发论文。其实这个问题我也在摸索，估计还只有一只脚入了门，另外一只脚还不知道该往哪儿踏。所以我建议小朋友问我不如去问老师……任何一个老师经验都比我丰富。不过，昨天上了一节网络算法课，对我的启发非常大。

我自以为自己算法水平非常强的。虽然从没得过什么国际金牌，但是大部分日常问题一眼就能看出问题的复杂度和基本算法思路。不过，昨天那节算法课让我觉得，我的算法即使不说是白学了，远远没有学到算法思考的方法。

昨天是第一课，讲算法设计的原则。老师先举了个问题，让大家来想该怎么做。一个路由器，希望能够对那些可能是“坏”的数据包进行标记，方便终端进行进一步的检查。一些安全专家统计了数据包中每个字符的频率，然后对每个字符给出了个阈值。如果一个数据包中该字符占的比例超过了这个阈值，那么就给这个数据进行标记。该算法用硬件实现。一个最简单的方法是每个字符一个一个计数器，每收到一个新的字符后计数器加1。数据包接收完整后再检查，是否有字符超过阈值。如果是的话进行标记。老师说，这个方法有个问题，收完了数据包后在从新扫描所有字符的计数器，复杂度就平白多了255。问大家有没有什么好的办法？（背景补充：硬件解决这个问题中，在收完整个数据包之前不知道数据包的长度。并且数据包长度的范围差距非常大）

这个问题当然不难。作为有良好算法基础的计算机学生，很快能想到，每次计数器加1时，计算该计数器和阈值的比值的最大值，然后和一个全局最大值进行比较。最后只要这个全局最大值超过包长度就可以对该数据包进行标记了。不过我选的这门课不是CS的，是EE的。老师说，做除法代价太大了，我们不能做除法。于是我就半傻眼了（也许再思考下有其他算法，不过上课进度还是相当快的）。

老师的做法让我大跌眼镜：老师说：这个问题定义的有问题。解决这个问题的方法是改变这个问题的定义。最重要的是解决正确的问题，其次才是正确地解决问题。这个问题的本质是对可疑的数据包进行标记，并且阈值也是人给的。与其使用和和包总长度的比例，不如使用和当前长度的比例，（需要特殊处理长度较小时的情况，取个max即可）。虽然解决的问题和原来不一样，但是最后效果其实没差。或者改进一下我刚刚的算法，与其可以除以一个任意的阈值，不如限制阈值的取值范围，使其可以用移位来实现，反正阈值都是人给的。通过改变问题，这个问题一下就简单而又容易地解决了。

在国内，如果老师布置这么一道作业题，你去把人家题目给改了，自然是零分。不过做研究，第一步则需要能够分析出问题的本质，从而提炼出“正确”的问题去解决。

有了第一步的找出问题，第二步就是找到所有可以利用的条件。拿TCP的拥塞控制举例。最早的TCP，利用的信息是丢包。即当数据包发生丢失时，肯定发生了拥塞，所以我们需要降低传输速率，降低的幅度为1/2。然而这个粒度实在是太粗了。进一步分析这个问题，知道丢包的原因是中间某路由器的缓冲区满了，所以才丢包。那么我们可以利用路由器的缓冲区的信息。现代很多路由器支持当队列长度在A到B之间时（A和B由路由器的控制者定义），对数据包进行标记。于是后来TCP利用的条件就是有数据包在路由器被标记，因为缓冲区增大超过了A，说明即将开始拥塞了，需要降低速率。SIGCOMM 10的一篇文章提出来的DCTCP。思想仍然是利用被路由器标记的数据包。不过，他利用了更多的条件，即统计了在一个窗口中被标记的数据包的数量（而不仅仅是有和没有)，所以可以更细粒度地进行拥塞控制。

以前做作业，问题和条件都是老师给出来的，顶多仔细读题，不存在去寻找可以利用的条件这个问题。我觉得很多时候，由知识储备不充分，或者对最新动向不了解，比如不知道现在各种路由器的功能，所以找不到更多的可以利用的条件。所以我觉得，要做好这一步，需要大量平时的积累，而不是仅仅靠脑子想就出结果了。

第三步就是把问题解决了。有了问题有了条件去解决问题，这一点在国内从小学就开始学了。所以我就不多说了。


转载本文请联系原作者获取授权，同时请注明本文来自杨双科学网博客。
链接地址：https://wap.sciencenet.cn/blog-441887-427850.html

上一篇：研究做出来要给别人看/用的
下一篇：选导师很纠结