补充知识点–链式前向星
- 图的实现中邻接表是不好写但效率好,邻接矩阵是好写但效率低的话,链式前向星是个折衷方案,它以边为基本存储索引,存储过程可以描述为加边函数。链式前向星其实就是静态建立的邻接表,时间效率为O(m),空间效率也为O(m)。遍历效率也为O(m)。
- 对于一条边的集合<a,b,w>,其中a是起点,b是终点,w是权重,构建图的加边函数过程如下:
void add_edge(int a,int b,int w) { /*cnt表明这个边是构图的第几条边,也就是边的序号*/ edge[cnt].to=b; edge[cnt].w=w; /*next函数表明以a为起点构建的边集中cnt下一条边的序号*/ edge[cnt].next=h[a]; /*h[a]存储起点a指向的下一条边的序号,其实就是头插法*/ h[a]=cnt++; }
- 链式前向星结构的遍历方法
边为存储索引单位,每来一条边就构建一个图,但链式前向星的结构仍然类似于邻接表,遍历的时候需要以起点为单位遍历
for(int i=1;i<=n;i++)//i为起点编号 { for(int j=h[i];~j;j=edge[j].next) { ... } }
注意上述代码中的~j用法,他的含义是j!=-1,加快函数编译,是一种很高端的写法,值得掌握。
读懂题目系列
这道题文字代码很多,因此需要化繁为简,把问题转化为代码解决。
- 时间间隔Δt,表示相邻两个时刻的间隔。
- 神经元有参数u,v,变化公式题目已给出,神经元会发放一个脉冲,脉冲经过突触传播到其他神经元,发送脉冲后u,v的值也会发生变化。注意神经元不一定会发送脉冲,是有条件的。
- 突触用于传递脉冲,是无条件传递,但会将脉冲大小整形到W,延时为D。
- 脉冲源负责产生脉冲。
这道题的要求是输入相关数据,计算传递过程中的相关指标。
突触的输入数据包含入节点,和出节点,以及s,d。有了突触的连接数据,可以构造脉冲神经网络图,也就是将问题转化成了图结构。
如下图所示,突触因为一定传送脉冲,可以看为边,w可以看成权重,d为d个Δt
暂时忽略下方高亮
一共有T个时刻,每个时候存储所有脉冲源和神经元的状态,从零时刻按照图的结构遍历即可最终得到T时刻的状态,总时间复杂度为T*(n+s+p),空间复杂度为T*(n+s+p)个double,显然空间复杂度过大,接近800M内存,超过程序的最大内存512M。因此不能存储每个时刻的节点状态。由题目可知其实神经元传递脉冲是个马尔可夫链的过程,具有无记忆性,当前时刻的值只影响下一个时刻,因此理论上只需要两个时间单位用于存储当前时间状态和吓一时刻状态。但这道题比较特殊,有1000的延时,因此将时间轴延长到1000。