商城网站哪个公司做的好,seo和sem推广,网站开发详情,远程教育网站开发文章目录 从一个案例开始动态规划 Hi, 你好。我是茶桁。
咱们之前的课程就给大家讲了什么是人工智能#xff0c;也说了每个人的定义都不太一样。关于人工智能的不同观点和方法#xff0c;其实是一个很复杂的领域#xff0c;我们无法用一个或者两个概念确定什么是人工智能也说了每个人的定义都不太一样。关于人工智能的不同观点和方法其实是一个很复杂的领域我们无法用一个或者两个概念确定什么是人工智能无法具体化。
我也是要给大家讲两个重要的概念要成为一个良好的AI工作者需要了解两个概念一个是什么是优化问题第二个呢就是什么是继续学习。
这一节开始我们要开始进入机器学习的入门这一部分只是机器学习的初级部分我将其分成了三个部分分别是
如何衡量向量的相似性metric for tensor)k-means算法进行聚类线性回归与梯度下降
但是整体课程的排程并不是严格按照这三个部分来排的所以大家能看到我本篇课程的标题也并不是「如何衡量向量的相似性metric for tensor)」。以上三个部分仅仅是我们当前这一部分会讲到的内容但是也是拆散了放入课程中的。
从一个案例开始
那这节课最初让我们从一个实际案例来引入开始我们的深度学习初级之旅。
那要给大家讲的第一个问题我们叫做optimization, 也叫做优化问题。那这里我们拿一个实际的项目来。
我们所在的城市可能很多人会经常看到运钞车。这个运钞车其实也是银行花钱雇的运钞车其实也不是银行的。 每次要使用运钞车的时候是需需要花钱还比较贵。这样就会带来一个结果专门有人来策划运钞车的运行路径。为什么要策划计划运钞车的运行路径呢因为如果我们有一台ATM机ATM机满了那么面对的一个问题就是别人存不进去钱了
另外很重要一点是如果一个ATM机满了而且没有把钱取出来那这个钱就相当于是浪费了。加入一个ATM机能存一百万那晚拿出来一天、两天对银行来说损失就比较大。
还有一种情况就是这个ATM机空了那客户去取钱的时候也取不到钱也就起不到ATM机的作用。而银行对ATM机所在地的房租也就相当于白费了。
试想一下如果同时有两张卡一张农行卡一张工行的卡在农行准备想取钱的时候取不出来就到工行去取了。而每次农行都取不出来那之后就用工行用的多了。
在这样的情况下, 一个城市有很多个点, 就需要有很多个运钞车。
比方说在城市中有很多个ATM机的站点现在我们有k个运钞车。 我们要策划一条线路这个线路要使得所有的车每个车每个点只走一遍还要回到他出发的地方而且这k个车运行的时间加起来是最小的。
那怎么样计划出这样一条路径呢就这是一个非常典型的优化问题。对于此类的问题其实还有很多很相似的。
比如对于一家公司而言手里的钱是有限的。如何把这些金额分配到不同的项目组中 另外一个比方就是对于一个公司来说如何选取合理的仓库的存货点还有哪些仓库放哪些商品能够让运输的车辆花的时间最少能快速的去把这货物运输到不同的地方这种物流问题是我最喜欢的问题之一。 或者我们制造一部手机我们能花的钱就这么多那怎么样能够在我们可以花的这个金额的范围内如何选取最合理的元器件成本让我们的手机达到最大的利润 有很多约束条件很多约束我们做决策的东西总量不能大于多少。比方电的成本水的成本等等都要满足一定的关系才可以。这种东西我们就把它叫做约束条件。
要解决在约束条件下达成目标的这个问题我们就把它叫做优化问题。 优化问题就是我们可能会有不少的函数这些函数去限定了之间的一种关系也就是函数之间可能会有一些约束条件。比如图中的g_i(x)。
假设我们要造很多仓库仓库加起来所花费的成本是什么样的, 花费的人力是什么样的。
最后要优化出来一个最小值就是我们的最小花费或者所需要最少的时间。这种问题其实广泛存在于我们各个地方。
你点外卖每天在地图上做一个地图的规划公司里做一笔投资其实都是使用了类似这样的东西。
动态规划
我们要解决优化问题其实有比较多的方法今天来介绍最著名的一种也是可以说是最重要的一种动态规划的思想。
动态规划是一个什么样的情况以这个问题引入一下。 想象一下有这么一个工厂这个工厂是卖木头的长度是一米的木头卖一块钱长度2米的卖5块钱。
那么所以除非拿了一个一米的木头否则不会有一个人像傻子一样说把这个两米的木头截成两段。
图中我们可以看到3米的就卖8块等等到后面10米的卖3011米的卖33。
那么现在你拿到了一个长度为8的一个木头那你想想这个8米的木头是该直接卖还是它切分掉去卖。切分掉去卖的话如果用1和7加起来就是18块钱 2和6加起来就22块钱了比8是不是就多了 给你任意的一个长度n然后我们要得出来这个n到底该怎么切分能够使得价格最大。怎么样能够让卖出去的价格最大。
思考一下咱们怎么解决这个问题。计算机有一个很很简单的方法就是计算机有一个非常好的优点就是它可以做穷举。你可以让他去找什么让他把所有东西全部都运行一遍就可以了。这是计算机的一个好处。
我们来思考一下咱们怎么样能够解决这个问题呢
我们现在输入了一个长度是n的一个木头。它可以变成n和0就是不切分。可以变成1和n-1, 变成2和n-2。一直截断到多少呢可以变成n-n/2。
(0,n),(1, n-1),(2, n-2)…(n-n/2, n-n/2)
在这个情况下, 它分成1和n-1, n-1也面临了类似的问题。n-1是你直接返回n-1呢, 还是变成(1, n-2)变成(2, n-3)。对于2其实也有也会面临这样一个问题是返回2呢还是(2-1, 2-1)。如果我们要遍历的话遍历的就应该是一个树。把这个树里面所有情况都找一遍然后返回那个最大值就可以了。 我们可以把所有的情况循环一遍那我们现在来实现一下你会发现其实一点也不难。
让我们来先定义一下所有的价格
prices [1, 5, 8, 9, 10, 17, 17, 20, 24, 30 , 33]我们要知道它的每一个商品直接的价钱就是complete我们来定义一个complete_price,
complete_price { i1: p for i, p in enumerate(prices)}
print(complete_price[9])---
24那如果这个时候是30就会出问题。
print(complete_price[30])---
KeyError: 30遇到这种问题的时候不要非要去判断这个在不在里边,可以直接用detaultdict, 它是是一个带有默认值的Dictionary如果这个值不存在的话给它赋予一个默认值。
from collections import defaultdictcomplete_price defaultdict(int)for i, p in enumerate(prices): complete_price[i1] pprint(complete_price[9])
print(complete_price[30])这个时候如果是30, 它就有一个结果了。现在有了这样的一个基础数据我们假如要写一个revenue,revenue就是营收输入长度是n。
现在做一个很简单的方法
def r(n):candidates [complete_price[n]]candidates等于价钱完全不切割是多少钱。然后我们写一个for循环
for i in range(1, n):pass接下来我们做个拆分拆分左边就等于i, right就等于n-i:
left i
right n-i这个时候整体的价格就等于complete_price[left], 再加完整的右边, complete_price[right]。
total_r complete_price[left] complete_price[right]这里其实是有问题的, 如果我们在这里假设n现在是100, 假设运行到i是50, 那么complete_price[50] 其实是一个没有值的, 值是0。
就是数据里没有50的长度的价格所以这个左边和右边其实是需要变成一个递归问题。
total_r r(left) r(right)
candidates.append(total_r)现在写法写的稍微巧妙一些这个就是我们刚才所说的遍历一遍把所有的情况给拿出来,找到最大的返回出来。目前为止这个方法完整的代码如下
def r(n):candidates [complete_price[n]]for i in range(1, n):left iright n-itotal_r r(left) r(right)candidates.append(total_r)return max(candidates)
这个时候我们来调用一下
print(r(8))---
22这个22是怎么来的呢? 我们来看一下上面这段代码, 首先8进方法之后 第2行告诉我们8完全不切割的话是多少并赋值给candidates。
紧接着把它变成了1和72和63和54和4这样的问题。
假如到6的时候又会去求一下这个6。右边是要变成6那么6最大应该是多少。
这个代码其实可以写成更加Python化的方式我先写一遍上面的是希望能让大家知道这个代码是怎么来的现在让我们来用Python的方式来解决
# 优化为Python向
def r(n):return max([complete_price[n]] [r(i) r(n-i) for i in range(1, n)])print(r(8))---
22也就是以上方法里定义的内容完全可以压缩成一句话解决。你们可以仔细的研究一下这两段的相同点和差别。
现在的问题就是我们缺了一个记录他中间分割步骤的内容这个也简单我们稍微改变一下代码将return改为赋值然后给他加一个分割方法
candidates [(complete_price[n], (n, 0))] [(r(i) r(n-i), (i, n-i)) for i in range(1, n)]其中我们添加了(n, 0), 还有(i,n-i)。
然后我们还要给他加上最优值
optimal_price, split max(candidates)如果这其中你要是看不出逻辑过程那你需要一些更多的练习。好好的再去回去看看我之前写的AI秘籍中的Python基础教程篇。
对于熟练的Python的工程师来说应该熟悉这种方式才对。第一次咱们实现的方法其实是C和Java的一种方法。如果是Python的话你需要熟悉Python直接会写成这个样子。
我们定义了一个candidates, 后面将风格方式定义进去并赋值给它。
然后我们使用optimal_price来接收它的最优价格。
接着我们添加一个solution变量solution是n的时候就找到了它的分割过程。
# 在方法外定义一个solution
solution {}# 在方法内赋值solution[n]def r(n):...solution[n] split最后我们还是将最优价格给返回出去。
return optimal_price来看一下solution[8]
print(solution[8])---
(6, 2)我们如果在这里debug一下这个solution运行完之后solution如下 是8的情况下变成6和2现在就要看一下6的时候怎么切分6的时候变成6和0。
好现在我们来看一个更复杂的问题我们将它变成33, 33你会发现他运行的时间很久。刚刚我们运行8或者我们重新运行9的时候速度都还可以很快就能得到结果。但是运行33的时候就会非常的缓慢。知道这是为什么吗
在这段代码中现在有一个nn接下来会拆分成了n-1个问题其实是要进行n-1个循环。那每个n-1的循环里面又有两个调用了这个运算。所以在整个计算的次数的复杂性对于一个n来说它整个的运行时间应该是2 * (n-1) * 2 * (n-2) * … 2^n * n!就等于2的n次方再乘上n的阶乘。
这样的话结果就是它的运行时间会非常非常的久。那我们就需要对代码进行优化了。
如果现在仔细分析一下的话会发现之所以运行的慢问题在于很多重复的值其实被重复运算了。同样是n-3这个事不仅在n-1向下分支中会计算一次在其他的分支也会再计算很多次。有很多的值是被重复运算了。
为了解决重复运算的问题我们可以做一个非常简单的方法。既然很多计算是重复的那我定义一个变量去记录这些曾经计算过的再遇到的时候就不要去计算不就完了
cache {}def r(n):if n in cache: return cache[n]...cache[n] optimal_pricereturn optimal_priceprint(r(33))---
99如果n在cache里面, 直接return cache[n], 如果它不在里边的话就往下继续运行每次求完解的之后我们让cache[n]等于optimal_price。这样就简单多了。
我们最后求了一下33瞬间就得到了99的答案。
这个cache其实是很简单的一个东西但是它其实是很重要的一种思想。在一九二几年、三几年的时候当时有一个数学家叫Richard Bellman。Bellman发现在整个数学计算中有相当的一类问题都牵扯到了一个相似的问题over-lapping sub-problem就是子问题的重复。 Bellman就提出来了一种方法他就说我们解决这种问题其实有一个很简单的方法用一张表格不断地记录不断地查表就是不断地写表查表。
就把值和结果都一一对应的写入表中我们发现问题的时候在这个表里面重新查一遍看一下有没有这个值存不存在。
当时Bellman把这种方法叫做Dynamic不断地、持续地、变化的、动态的。programming在我们现在意思是编程在一九二几、一九三几年的时候是指把东西写到表格里以及从表格里面拿出来。
那为什么后来演化成编程的意思因为早些时候冯诺伊曼当年制作的那个机器写的是纸带就是给你一个一个的纸带这个纸带每一行会打八个洞就是当时冯诺伊曼最早的计算机。这8个洞里边有一些是透光的有一些是不透光的其实就是一条一条计算机命令。
这其实也是一个写表读表的过程后来programming就有了编程的意思。但是Bellman当年提出来的这个意思Dandep programming就是不断地写表和查表。它针对的是所有一切有这个over-lapping sub-problem的问题都可以用这种简单的方法可以大幅度的减少计算性。
在很多地方学动态规划的时候很多书上教动态规划的时候往往是直接给一个解法。不知道您有没有看过那些算法的书在动态规划里往往会有一个表这个表格很重要。
如果不用动态规划的话这个问题也是能解决的。世界上几乎所有的这种优化问题不用动态规划都是可以解决的。但是理论上是要给你一个运算能力无限强存储空间无限大的计算设备。
显然不太可能所以我们就需要这样写到一个表格里边记一个记录表格。这个就是我们动态规划的核心思想。
关于「动态规划的详解」之后有机会我去专门写个算法的相关课程在这里就把动态规划的核心思想给大家介绍了。
我们现在来继续看代码刚才我们算了一下33这个值得到了99。但现在我们知道了能卖多少钱但是我们还不知道到底怎么个拆分法。
要拆分的话我们就要把这个solution给它parse一下再继续定义一个方法
def parse_solution(n, cut_solution):left, right cut_solution[n]if left 0 or right 0: return [leftright, ]else:return parse_solution(left, cut_solution) parse_solution(right, cut_solution)print(r(18))
print(parse_solution(18, solution))---
52
[10, 6, 2]我们看一下left和right将分割分别传进来那如果left和right是0的话比如10 写成(10, 0) 其实意思就是10就不用切分了直接返回left和right就可以了。
那如果说它里边不是0假如说是37切分17和20我们就要知道17该怎么分20该怎么分。所以就返回:
return parse_solution(left, cut_solution) parse_solution(right, cut_solution)最后我们看到了18的切分结果就被切分成[10, 6, 2]。
具体的切割过程也可以获得。
在Python里边呢这个是一个非常非常经典的动态规划问题。经过一个比较简单的方法把重复问题给解决了。
再跟大家普及一个知识在Python里面有一个好处就是它把很多常见的功能其实都已经想到做了切分了。
比方说Python自带的库里面就有一个functools, 它有一个lru_cache就是least recent used, 最近最少使用。
我们如果在直接写一个cache它会存在一个问题。当n特别大的时候那么cache的size也会变得特别的大。这个时候我们就需要一种机制来让cache保留最需要保留的东西保留那些最重要的东西不要把所有的信息全部弄进去。
这个lru_cache帮我们实现了这个功能,它会把最近最少使用过的这些值删去, cache的这个size会保持在一个比较固定的范围内。
这个函数是一个装饰器小伙伴们是否还记得我在Python课程中介绍过装饰器以及其使用
我们来使用一下这个装饰器:
lru_cache(maxsize2**10)这里定义了一下maxsize等于2的10次方就是最多可以存2的10次方个值。
那这里和我们方法里的这一段内容其实是一摸一样
if n in cache: return cache[n]
...
cache[n] optimal_price当我们调用这个函数的时候, 如果函数的参数曾经被计算过那么就直接返回这个值。如果没有被计算过就计算一遍再把这个值写下来。
那我们使用了这个装饰器之后我们对cache的使用的这两句代码就可以删掉了。
lru_cache的作用都懂了吧以后遇到一个程序很慢的时候就可以用它来做优化。
那其实今天这节课程把这个函数看懂几乎所有的动态规划的问题的主体思路就都懂了。因为所有的动态规划的问题都包含了以下几个问题
识别子问题 sub-problems dividing识别子问题中的重叠特点 over-lapping sub-problem存储子问题的答案 cache sub-solutions合并问题答案 combine solutions解析答案 parse solutions
这是所有的动态规划的特点当你发现一个问题可以被分解成子问题而且子问题有重复的时候就可以用这种方法去优化它。
以后大家面试大概率会遇到这种问题。只要按照这个方法来思考的话问题基本上就不大了。
但是动态规划其实也是有一个极限曾经有一段时间人们以为动态规划可以解决很多问题几乎可以解决所有常见的问题。但是后来人们发现当限制条件特别多或者问题已经复杂到非常难的去识别此问题了。可能它是包含了子问题的关系但是因为这个问题太复杂了所以我们没办法去把它分割出来我们没有办法去识别它。
动态规划是一种思维方法一种思维类型。比方计算机里面的图论问题并不是只能把它变成图论问题不用图论完全可以解决但是不太好弄。
所以动态规划其实也有它的局限性人们为了解决更多问题就提出了更多的方法其中一种方法就叫做机器学习。
好我们下节课就好好的来讲讲机器学习。本节课的最后我将之前咱们写的那段代码完整版贴在这里
from collections import defaultdict
from functools import lru_cacheprices [1, 5, 8, 9, 10, 17, 17, 20, 24, 30 , 33]
complete_price defaultdict(int)for i, p in enumerate(prices): complete_price[i1] psolution {}
cache {}lru_cache(maxsize2**10)
def r(n):candidates [(complete_price[n], (n, 0))] [(r(i) r(n-i), (i, n-i)) for i in range(1, n)]optimal_price, split max(candidates)solution[n] splitreturn optimal_pricedef parse_solution(n, cut_solution):left, right cut_solution[n]if left 0 or right 0: return [leftright, ]else:return parse_solution(left, cut_solution) parse_solution(right, cut_solution)print(r(18))
print(parse_solution(18, solution))
