202109-3 脉冲神经网络

70% 数据——模拟

先不考虑具体时间复杂度，思考朴素做法应该怎么做：

枚举 \([0,T]\) 每个时刻，这里应为一个外层循环；
对脉冲源进行处理：通过 \(r\) 参数判断是否会发射脉冲；
对神经元进行处理：通过 \(v_k\) 判断是否会发射脉冲；如果发射脉冲，则更新 \(u_k,v_k\)。

判断脉冲源是否发射脉冲相对容易。但对于神经元来说，由于传播延迟的存在，我们需要知道 \(I_k\)，即神经元在 \(k\) 时刻接收到所有脉冲输入的强度之和。又由于每个神经元是否发射脉冲是互相独立的，我们需要知道每个神经元在每个时刻接收到的脉冲和。

一种思路是开一个 \(\mathrm{O}(NT)\) 的二维数组来记录。由于空间大小的限制，我们只能通过 \(70%\) 数据。

再来考虑时间复杂度：枚举时刻是 \(\mathrm{O}(T)\)，枚举脉冲、神经元及发射脉冲需要 \(\mathrm{O}(N+S+P)\)，整体复杂度 \(\mathrm{O}(T(N+S+P))\)，可以通过所有的数据。

100% 数据——滚动数组优化

为了得到满分，目前的任务是缩小记录每个神经元 \(I_k\) 的空间复杂度。

提示

题目给出的量的大小一般都是有用的。如果没有思路时，可以从这些貌似“没用”的量上进行突破，比如本题的 \(D\)。

考虑耗费空间的位置：虽然有传播延迟 \(d\) 的存在，但在某个时刻 \(t\)，能影响到神经元 \(I_k\) 的时刻范围在 \([t, t+\max\{d\}]\) 范围内。一方面，对于 \(k>t+\max\{d\}\) 的 \(I_k\) 我们没必要记录，因为不会有脉冲对其造成影响；另一方面，对于 \(k<t\) 的 \(I_k\) 我们没必要保留。我们只需要维护 \(k\in [t, t+\max\{d\}]\) 的 \(I_k\) 值就可以完成任务。在这种情况下我们可以利用{\heiti{滚动数组}}进行优化。

滚动数组

滚动数组是一种思想，通过对数组“取余”来缩小空间。设目前需要保留值的个数为 \(p\)，则在使用滚动数组后，原数组在 \(i\) 的位置由 \(i \bmod p\) 替代。

不妨设求解原数组中 \(i\) 位置值涉及的位置有 \([i-p, i-1]\)，当计算出原数组 \(i\) 位置的值后，直接覆盖 \(i \bmod p\) 位置的值即可。因为被覆盖的值为 \(i-p\) 位置的值，在下次计算 \(i+1\) 位置的值时，需要的区间为 \([i-p+1,i]\)，已经不需要存储该位置的值了，所以可以放心覆盖。

在选取合适的 \(p\) 的时候，可以尽量大一些，防止覆盖需要保留的数据。

对于这道题，我们可以利用滚动数组的思路，将空间优化到 \(\mathrm{O}(ND)\)，即可通过此题。

代码实现

C++

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 1010;
const int maxD = 1010;

// 如果使用原题的 next 可能会 CE，这里改成 nxt
static unsigned long nxt = 1;
/* RAND_MAX assumed to be 32767 */
int myrand(void) {
    nxt = nxt * 1103515245 + 12345;
    return ((unsigned)(nxt / 65536) % 32768);
}

int N, S, P, T;
double dt;
// 脉冲源只需要 r 参数即可
int r[maxn];

// 神经元
struct Neuron {
    double v, u, a, b, c, d;
    int activate_times;
} neuron[maxn << 1];

// 突触
struct Synapse {
    int s, t;
    double w;
    int D;
} synapse[maxn << 1];

// 存图
vector<int> G[maxn << 1];
// 存储每个时刻每个节点的 Ik 值
double I[maxD][maxn];

int main() {
    scanf("%d%d%d%d", &N, &S, &P, &T);
    scanf("%lf", &dt);
    int cur = 0, rn;
    double ru, rv, ra, rb, rc, rd;
    while (cur < N) {
        scanf("%d", &rn);
        scanf("%lf%lf%lf%lf%lf%lf", &rv, &ru, &ra, &rb, &rc, &rd);
        while (rn--) {
            neuron[cur].v = rv;
            neuron[cur].u = ru;
            neuron[cur].a = ra;
            neuron[cur].b = rb;
            neuron[cur].c = rc;
            neuron[cur].d = rd;
            neuron[cur].activate_times = 0;
            ++cur;
        }
    }
    for (int i = 0; i < P; ++i) {
        scanf("%d", &r[i]);
    }
    for (int i = 0; i < S; ++i) {
        scanf("%d%d", &synapse[i].s, &synapse[i].t);
        scanf("%lf", &synapse[i].w);
        scanf("%d", &synapse[i].D);
        // 连边
        G[synapse[i].s].push_back(i);
    }

    // 按时间递增
    for (int t = 0; t < T; ++t) {
        // 滚动数组清零
        for (int i = 0; i < N; ++i) {
            I[(t - 1 + maxD) % maxD][i] = 0;
        }
        // 脉冲源
        for (int i = 0; i < P; ++i) {
            if (r[i] > myrand()) {
                // 脉冲激发
                for (int j = 0; j < G[N + i].size(); ++j) {
                    Synapse tmps = synapse[G[N + i][j]];
                    I[(t + tmps.D) % maxD][tmps.t] += tmps.w;
                }
            }
        }
        // 神经元
        for (int i = 0; i < N; ++i) {
            double u = neuron[i].u, v = neuron[i].v;
            neuron[i].v =
                v + dt * (0.04 * v * v + 5 * v + 140 - u) + I[t % maxD][i];
            neuron[i].u = u + dt * neuron[i].a * (neuron[i].b * v - u);
            if (neuron[i].v >= 30) {
                // 脉冲激发
                neuron[i].v = neuron[i].c;
                neuron[i].u += neuron[i].d;
                ++neuron[i].activate_times;
                for (int j = 0; j < G[i].size(); ++j) {
                    Synapse tmps = synapse[G[i][j]];
                    I[(t + tmps.D) % maxD][tmps.t] += tmps.w;
                }
            }
        }
    }

    // 输出结果
    double minv = 1e18, maxv = -1e18;
    int mint = 1e9, maxt = 0;
    for (int i = 0; i < N; ++i) {
        if (neuron[i].v < minv)
            minv = neuron[i].v;
        if (neuron[i].v > maxv)
            maxv = neuron[i].v;
        if (mint > neuron[i].activate_times)
            mint = neuron[i].activate_times;
        if (maxt < neuron[i].activate_times)
            maxt = neuron[i].activate_times;
    }
    printf("%.3lf %.3lf\n%d %d", minv, maxv, mint, maxt);
    return 0;
}

202109-3 脉冲神经网络

70% 数据——模拟

100% 数据——滚动数组优化

评论