资源简介:
【算法蓝图】怎样设计一个算法?——更多资源,课程更新在
资源,名师讲座课程简介:
【算法蓝图】怎样设计一个算法?
算法蓝图——怎样设计一个算法
初学算法的人很容易掉进一个误区,认为懂的算法越多,就越厉害,这是不对的。
算法是解决问题的工具,我们学习算法的目标是解决问题,让计算机更快更好地工作,这光靠算法懂得多可做不到。
打个比方,学英语肯定要背单词,很多学生能背 1 万个单词,可写作能力还是中学水平,而厉害的作家只用 3000 个常用单词就可以写出文学名著。我们现在想
提高写作水平,不是比谁单词背得多,而是得提高写作能力。
怎么提高写作能力呢?算法工程师有一套用算法解决问题的标准流程,称之为
算法蓝图”,这一讲就说说什么是算法蓝图。
把这个复杂过程简化成三个步骤:第一,明确问题;第二,建立模型;第三,算法选择。接下来,具体讲讲。
1 明确问题
首先是明确问题。不少武断”的算法工程师,做预测就要用回归分析,给产品分
类就要上 K 临近算法,给用户推荐就要用神经网络,但是他们真的搞清楚问题是什么了吗?
拿网约车举个例子。如果你是一名产品经理,你会怎么描述需要解决的问题呢?
最直接的描述可能是这样:设计一套算法,可以匹配乘客和车辆。”
这显然还不够明确,乘客耐心有限,不愿意等很久,那就加上一条乘客等待时间最好 5 分钟以下”。这时候问题明确了吗?网约车公司看重的是盈利,而平台注册车辆是有限的,如果能够在早晚高峰鼓励司机多接单就能获得更大的收益。怎么实现呢?那就需要算法可以根据需求的多少,对价格做动态调整。
如果再考虑到竞争对手的数据,平衡市场占有率等更多条件,需要考虑的东西只会越来越多,那又该怎么设计算法呢?
你可能听说过,产品经理最主要的工作就跟开发战斗”,产品经理认为某个需求很重要,但开发程序员认为没法实现。产品经理指责程序员不懂业务,程序员指责产品经理不懂技术,总是鸡同鸭讲。
其实他们可能都没错,只是需要在设计算法之前,就先明确问题,对问题的方向”和边界”先达成共识,再开始谈算法怎么实现。
怎么算明确问题呢?我们可以从三个要素入手,明确目的、明确限制条件、明确评价标准。
首先是,明确目的。对目的的描述可以有很多种,比如匹配到所有的打车乘客”
和尽可能快地匹配到更多乘客”,或者让车辆利用率达到最大”,这都是不一样的,究竟要选哪种目的需要在一开始就确立下来。
其次,要明确限制条件。比如,每个乘客等待时间不能超过 10 分钟”,市区乘客不能超过 1 分钟”,等等,要把量化的指标确立下来。
有时候,我们想实现的目标和限制条件是不相容的。比如,我们要设计一套算法,
让 10 辆网约车在 10 分钟内服务 1000 名乘客”,这显然是不可能的。
当然,这个例子太简单,我们都知道不合理,实际情况要复杂得多。能不能准确、
快速判断限制条件的合理性,是非常考验一位算法工程师水平的。接下来,要明确评价标准,也就是问题得以解决的标准是什么。前两个都很好理
解,目的、限制条件,好像已经可以帮我们清楚描述一个问题了,但评价标准一定是必不可少的。
标准的维度可以有不同的设定,比如时间、成本、收益等,但不可以没有。没有标准就无法判断问题是不是最终被解决了。
2 建立模型
明确问题之后,该设计算法了,不过这时还要再等等,设计算法前先要建立模型。
跳过数学模型,直接提出问题的解法,不是一个用算法解决问题的好习惯。为什么呢?咱们再看一个例子。
NBA 球队都热衷于追求速度快。进攻速度快,投篮次数多,得分概率就大,赢面也就越大。这么说好像没问题,但换个视角看,投篮多的同时也会让对手篮板的机会增加,也会增加对手的投篮机会。
如果对手命中率更高,那快速推进比赛会不会更容易输掉比赛呢?
好像有可能。要解决这个问题,就不能直接上算法,而需要建立数学模型。
现实问题是没办法直接交给计算机的,我们需要一个数学模型来与计算机建立桥梁”,可以说,建立模型的过程,也是把现实问题转化成算法问题的过程,用
另一套语言来重新描述问题。
有时候描述一个问题,还可能需要多种数学模型的组合,而这些模型有层次,甚至会互相依赖,合在一起才完成桥梁”的搭建,真正用数学语言描述了现实问题。
回到篮球比赛这个问题,怎么建模呢?可以用随机游走”模型来描述篮球比赛。随机游走,是描述事物随机性变动的一种模型,比如觅食的动物走来走去的路径,
股票价格上下的波动,分子在气体中的移动轨迹,都可以用随机游走模型来描述。
而类似的思路也可以用来描述篮球比分。
大概思路是这样的:假设每次进球得分都简化成 2 分,两个球队的比分之间的
差,就是一个不断变化的随机数 X。如果 A 队得分,随机数就加 2 分,如果 B 队得分,随机数就减 2 分。
那么在这个模型里,只要我们知道两个球队每次进攻的进球概率,就可以计算出
N 个回合之后,随机数 X 是个什么样子,也就是两个球队分差的概率分布,这是跟回合 N 是有关的。
拿到概率分布,很容易就可以确立战术,在我们队进球率低于对方的时候,打的节奏越快,比赛回合数 N 越大,比分落后的可能性也就越大。相反也是一个道理,如果我们的进球率高于对方,节奏越快,赢的机会也就越大。
这是随机游走模型告诉我们的答案,至于这个答案是不是真的靠谱呢?还要拿到赛场上去试试才知道。
总之,提出一个问题,直接设计算法、编写程序需要大量的成本,如果没有模型也就对结果没有办法进行预估,有了数学模型,才能实现推理、预估或者预测。
所以,在设计算法之前,一定要建立数学模型。
但请注意,数学模型并不是对现实问题的完美描述,建模的过程,也是大量细节
被抽象掉的过程,在算法迭代中,模型迭代是非常重要的一环。
3 算法选择好,问题明确了,模型也建好了,总算要设计算法了。但还有一个问题,是不是
同一个数学模型,总是对应同一个算法呢?
举一个最简单的例子,等差数列你肯定学过,等差数列求和怎么算呢?比如说,
你要把 1 加 2 加 3 一直加到 100,你可以老老实实,一个个数算,就能得到答案。
但这个算法就有点太笨了。
数学家高斯在 14 岁的时候,发明了等差数列法,用乘法来替代加法。他发现一
个规律,数列的首尾相加是一样的,1 加 100 等于 101,2 加 99 也是 101,所以用 101 乘以 50 就可以非常快地完成计算。
这你就可以看到,同样的数学问题,不同的算法效率很不一样。
像压缩音频的问题,用傅里叶变换和快速傅里叶变换,两种不同的算法用的时间可以分别是几天
和几秒,差出几万倍甚至更多。不同算法就是有这么大的差距。
说回等差数列求和的问题。高斯的算法非常好,只靠数学推导,就可以用时间复
杂度极低的算法来解决问题,可以说是完美的算法,那么这类问题可能就不考虑其他算法了。
可遗憾的是,大多时候并不存在最优的算法,没有所谓的only解”。有时候可能
因为算法复杂度还不够低,有时候可能是还没设计出最好的算法。于是,算法工程师不可避免地要在不同算法之间做出选择。
算法各有优劣,算法工程师在选择的时候会考虑时间复杂度,也要考虑达成目标
水平的高低,等等。如何选出最适合的算法,是算法工程师面对的又一个重要挑战。
最后,还有最重要的一环,迭代。很多时候,算法并不能直接解决问题,模型也只是对现实问题的近似和抽象,这就需要算法工程师不断迭代,在完成算法设计并且实现之后,不断回到原始问题,去评价算法。
这也是为什么在明确问题的时候,评价是特别重要的一环,只有清晰的评价标准,才能有更精准的迭代方向。
而且迭代,除了是算法的要求,也是硬件的要求。
硬件技术不断发展,从 4G 换 5G,每 18 个月芯片性能就会按照摩尔定律翻一番,
从依赖 CPU 做计算,到依赖图形处理器,这都不断需要与之相匹配的算法。有时
候迭代会改变整个算法设计的思路,会比算法设计本身还要重要。
算法解决问题的基本蓝图:
第一,明确问题,不明确问题会导致在算法设计中走很多不必要的弯路。
第二,建立模型,数学模型是对现实问题的近似和抽象,能够建立起计算机算法
和问题之间的桥梁,为算法的效果进行预先估计。
第三,选择算法,达成目标的好坏和时间复杂度决定了算法的选择。
91.0 MB
833次浏览
金融财经
899 MB
866次浏览
健康养生
983 KB
158次浏览
人性心理
993 KB
721次浏览
人性心理
2.75 GB
301次浏览
百科讲堂
434 MB
300次浏览
金融财经
加载中...