L3-023 计算图 (30 分)–PAT 团体程序设计天梯赛 GPLT

“计算图”(computational graph)是现代深度学习系统的基础执行引擎,提供了一种表示任意数学表达式的方法,例如用有向无环图表示的神经网络。 图中的节点表示基本操作或输入变量,边表示节点之间的中间值的依赖性。 例如,下图就是一个函数 f(x1​,x2​)=lnx1​+x1​x2​−sinx2​ 的计算图。

现在给定一个计算图,请你根据所有输入变量计算函数值及其偏导数(即梯度)。 例如,给定输入x1​=2,x2​=5,上述计算图获得函数值 f(2,5)=ln(2)+2×5−sin(5)=11.652;并且根据微分链式法则,上图得到的梯度 ∇f=[∂f/∂x1​,∂f/∂x2​]=[1/x1​+x2​,x1​−cosx2​]=[5.500,1.716]。

知道你已经把微积分忘了,所以这里只要求你处理几个简单的算子:加法、减法、乘法、指数(ex,即编程语言中的 exp(x) 函数)、对数(lnx,即编程语言中的 log(x) 函数)和正弦函数(sinx,即编程语言中的 sin(x) 函数)。

友情提醒:

  • 常数的导数是 0;x 的导数是 1;ex 的导数还是 ex;lnx 的导数是 1/x;sinx 的导数是 cosx
  • 回顾一下什么是偏导数:在数学中,一个多变量的函数的偏导数,就是它关于其中一个变量的导数而保持其他变量恒定。在上面的例子中,当我们对 x1​ 求偏导数 ∂f/∂x1​ 时,就将 x2​ 当成常数,所以得到 lnx1​ 的导数是 1/x1​,x1​x2​ 的导数是 x2​,sinx2​ 的导数是 0。
  • 回顾一下链式法则:复合函数的导数是构成复合这有限个函数在相应点的导数的乘积,即若有 u=f(y),y=g(x),则 du/dx=du/dydy/dx。例如对 sin(lnx) 求导,就得到 cos(lnx)⋅(1/x)。

如果你注意观察,可以发现在计算图中,计算函数值是一个从左向右进行的计算,而计算偏导数则正好相反。

输入格式:

输入在第一行给出正整数 N(≤5×104),为计算图中的顶点数。

以下 N 行,第 i 行给出第 i 个顶点的信息,其中 i=0,1,⋯,N−1。第一个值是顶点的类型编号,分别为:

  • 0 代表输入变量
  • 1 代表加法,对应 x1​+x2​
  • 2 代表减法,对应 x1​−x2​
  • 3 代表乘法,对应 x1​×x2​
  • 4 代表指数,对应 ex
  • 5 代表对数,对应 lnx
  • 6 代表正弦函数,对应 sinx

对于输入变量,后面会跟它的双精度浮点数值;对于单目算子,后面会跟它对应的单个变量的顶点编号(编号从 0 开始);对于双目算子,后面会跟它对应两个变量的顶点编号。

题目保证只有一个输出顶点(即没有出边的顶点,例如上图最右边的 -),且计算过程不会超过双精度浮点数的计算精度范围。

输出格式:

首先在第一行输出给定计算图的函数值。在第二行顺序输出函数对于每个变量的偏导数的值,其间以一个空格分隔,行首尾不得有多余空格。偏导数的输出顺序与输入变量的出现顺序相同。输出小数点后 3 位。

输入样例:

7
0 2.0
0 5.0
5 0
3 0 1
6 1
1 2 3
2 5 4

输出样例:

11.652
5.500 1.716

分析:结构体A中存储相关节点信息,de[i]表示第i个点是否被其他节点调用操作到,使用deal做dfs操作来根据题意进行题目的模拟运行,其中,c为1表示求导,c为0表示正常晕眩,index表示当前节点信息,to为求偏导数得目标,Record则是一个dfs下的记忆优化,start为一个可以作为出发点的节点。依题意输入数据后,遍历找出一个出发点节点,然后直接丢到deal函数中即可得到答案~注意导数运算的相关规则~

 

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版