tensorflow提示没有初始化Attempting to use uninitialized value

昨天在看西瓜书强化学习的章节时,想对照着伪代码写一下\epsilon-greedy的代码:

import tensorflow as tf
import numpy as np

R = tf.Variable([1.0, 2.0, 3.0, 4.0, 5.0], dtype=tf.float32, name="R") # 5个摇臂的Reward函数



def epsilon_greedy(K, R, T, epsilon):
    Q = tf.Variable(tf.zeros([5], name="Q"))
    r = tf.Variable(0., dtype=tf.float32, name="r")
    count = tf.Variable(tf.zeros([K], name="count"))
    for t in range(T):
        sample_val = tf.random_uniform([1], minval=0, maxval=1, dtype=tf.float32, name="random_value")
        if True: #这里待更新,有误
            k = tf.random_uniform(shape=[], minval=0, maxval=K-1, dtype=tf.int32, name="k")
        else:
            k = tf.argmax(R, name="k")
        v = R[k]
        r = r + v
        Q[k].assign((Q[k]*count[k] + v) / (count[k] + 1))
        count[k].assign(count[k] + 1)
    return Q, r

with tf.Session() as sess:
    tf.summary.FileWriter("logs/", sess.graph)
    sess.run(tf.global_variables_initializer())
    Q, r = epsilon_greedy(R.get_shape()[-1], R, T=10, epsilon=0.1)
    print("Q: {}, r: {}".format(sess.run(Q), sess.run(r)))

当我写完代码的时候,出现了一个非常诡异的Error:

出错信息

变量没有初始化?奇怪,我明明加了sess.run(tf.global_variables_initializer())呀

修改后的代码

经过一番倒腾之后,终于发现了问题。

tf的计算图是在条用epsilon函数的时候进行构建的,也就是说,我在init的时候Variables都还没有声明,因此肯定会显示没有init的情况,解决方法是:将sess.run(tf.global_variables_initializer())移动到epsilon函数之后就好了:

真是一个小小的细节,让我debug了好久好久。

2018百度之星资格赛1002题-子串查询

【题目大意】

有多组测试样例。

每个样例给定一个字符串A[1, n],并给出q次询问[l, r]。

输出询问区间中,有多少个子串(非空)是所有非空子串中字典序最小的。

也就是说,加入询问区间为ABA,那么应该输出2,因为区间中最小字典序的子串是A,而A出现了两次。

【样例输入】

1
2 3
AB
1 1
1 2
2 2

【样例输出】

Case #1:
1
1
1

【简要分析】

首先想到最多有1e5次询问,最长的字符串可以达到1e5。也就是说,如果每次询问得到结果的复杂度为O(n)的话,也就是说整个算法复杂度为O(n^2),很大可能上会超时。

分析一下,有多少个最小字典序的子串。小心别被糊弄了,题目就是要求给定区间中最小的字符的个数。这里可以用反证法,倘若最小的子串长度大于等于2,那么它的第一个字符构成的子串一定小于这个最小子串,那么这个子串将不是最小的,矛盾,因此最小的子串一定是一个字符。

那么我们如何动态的求区间的最小值呢,倘若遍历一遍,那么复杂度一定是O(n),TLE在所难免。

我们很容易想到线段树是一个优秀的求区间最值、和的一种方法。

用线段树求区间最小值就不必赘述了。

关键是,如何知道这个最小值出现了几次。

我们不妨在每个区间维持一个长度为26的数组,记录下26个字母各自出现的次数,然后在线段树向上更新的时候逐位更新,这样就大功告成了~

【示例代码】

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define m (l + ((r - l) >> 1))
#define lson (k << 1), l, m
#define rson (k << 1 | 1), m + 1, r
using namespace std;
const int MAX = 1e5+7;
const int INF = 0x3f3f3f3f;
int T, n, q, ll, rr, kase = 0;
char ch[MAX];
int dat[MAX << 2], sum[MAX << 2][30];
void pushUp(int k) {
    dat[k] = min(dat[k << 1], dat[k << 1 | 1]);
    for (int i = 0; i < 26; i++) {
        sum[k][i] = sum[k << 1][i] + sum[k << 1 | 1][i];
    }
} 
void update(int L, int c, int k, int l, int r) {
    if (l == r) {
        dat[k] = c;
        sum[k][c]++;
        return;
    }
    if (L <= m) update(L, c, lson);
    else update(L, c, rson);
    pushUp(k);
}
int query_min(int L, int R, int k, int l, int r) {
    if (L <= l && r <= R) {
        return dat[k];
    }
    if (L > r || l > R) return INF;
    int res = min(query_min(L, R, lson), query_min(L, R, rson));
    return res;
}
int query_sum(int L, int R, int c, int k, int l, int r) {
    if (L <= l && r <= R) {
        return sum[k][c];
    } 
    if (L > r || l > R) return 0;
    int res = query_sum(L, R, c, lson) + query_sum(L, R, c, rson);
    return res;
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &q);
        fill(dat, dat + (n << 2), INF);
        memset(sum, 0, sizeof(sum));
        getchar();
        for (int i = 0; i < n; i++) {
            scanf("%c", &ch[i]);
            update(i + 1, (int)(ch[i] - 'A'), 1, 1, n);
        }
        printf("Case #%d:\n", ++kase);
        while (q--) {
            scanf("%d%d", &ll, &rr);
            int minn = query_min(ll, rr, 1, 1, n);
            printf("%d\n", query_sum(ll, rr, minn, 1, 1, n));
        }
    }
    return 0;
}

白书P368页:禁止字符串

这道题属于字符串上的DP之单字符串的情况

题目大意:考虑仅仅由’A’,’G’,’C’, ‘T’组成的DNA串,给定一个长度为k的字符串S。计算所有长度为n,却不包含S的字符串的个数,输出结果需要模10009

限制条件:

1 ≤ k ≤ 100
1 ≤ n ≤ 10000

解题思路:

最简单的想法就是暴力枚举,对于一个长度为n的字符串,其中每个字符的可能性为4个,那么这样的话,总共需要枚举4^n种情况,这样绝对会TLE的

所以,与其我们将所有情况都枚举出来,然后去判断这些情况下的字符串是否含有S。不如我们直接在搜索(也就是从字符串头到尾进行4种情况的枚举)并在串最后添加字符时,直接判断添加后的串的最后k个字符是否为S就好了。这样一来,最后k个字符前面的字符都不予考虑了,因为他们对于后面的搜索都没有影响了。我们可以得到一个以剩余字符的个数和最后k – 1个字符的状态进行动态规划。

但是这样一来,还是有n*4^{k-1}种情况,复杂度并没有缩减多少。

但是实际上可以进行等价状态的归并,为啥,其实很多状态都是一样的,比如s=’ATG’的话,实际上’TAT’与’SAT’这两种情况是等价的,因为我们只需要考虑后面的两位AT就好了,前面的都不需要考虑了。因此可以发现,其实所有等价的情况归并后,每种情况都是s的前缀。因为我们可以s的前缀长度作为状态,包含0 … k-1,当然前缀长度为k的话,就是禁止字符串了,这种情况需要跳过。

也就是说,状态i等于前缀长度

这些做完了后,我们可以定义

dp[i][j]表示,字符串长度为i且以状态j结尾的合法数。

因此,最后的结果就是Σdp[n][j]其中j为所有可能的前缀长度,也就是0…k-1

状态转移方程就是:

dp[t][next[i][j]]+=dp[t-1][i]其中next[i][j]就是状态i后面加上字符j的下一个状态

这个是很显然的,DP的精髓就是状态转移方程,这个状态等于所有可以转移到这个状态之和

那么这时我们就是要处理一下next[i][j]了

next[i][j]表示当前状态i添加了字符j后将要转移到的状态。

为了方便起见,暂时不考虑模10009的限制条件

解题代码:

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
const int MAX_K = 107;
const int MAX_N = 1e4+7;
const char* AGCT = "AGCT";
int n, k;
string str;
// next[i][j]: 状态为i时,加上字符j,转移到状态next[i][j]
// dp[i][j]: 长度为i的字符串,以状态结尾的所有合法种数
int nxt[MAX_K][4];
int dp[MAX_N][MAX_K];
void cal_next(const int &k, const string &str) {
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < 4; j++) {
            string next_str = str.substr(0, i) + AGCT[j];
            while (next_str != str.substr(0, next_str.size())) {
                next_str = next_str.substr(1);
            }
            nxt[i][j] = next_str.size();
        }
    }
}
int cnt_num(const int &n, const int k) {
    dp[0][0] = 1; //长度为0,匹配串为0的话,算是合法的一种情况的
    for (int t = 1; t <= n; t++) {
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < 4; j++) {
                if (nxt[i][j] == k) continue;
                dp[t][nxt[i][j]] += dp[t - 1][i];
            }
        }
    }
    int res = 0;
    for (int i = 0; i < k; i++) {
        res += dp[n][i];
    }
    return res;
}
int main() {
    //freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &k);
    cin >> str;
    cal_next(k, str);
    printf("%d\n", cnt_num(n, k));
    return 0;
}

POJ 3420 Quad Tiling【矩阵快速幂+DP】

题目链接:POJ 3420 Quad Tiling

题目大意:和POJ2663基本一个套路,就是更加复杂了些。往一个4*N的矩形中填入2*1的小矩形的种数,由于答案过大,每个case都指定了M。

解题思路:

我将通过这道题,让矩阵快速幂这种类型的题目完全解决。

我们知道,矩阵快速幂,是可以快速求解递推式某项值的一种高效的解法。基于快速幂运算,可以使得幂运算的复杂度从O(N)变为O(logN)

对于POJ3420这题,如果列数不固定,且较小的话,那么可以考虑采用状压DP求解。但是这道题列数为4,那么很容易枚举出DP的转移方程。

我们考虑在我们尽力铺满第n行的时候,可能会“突出”到n+1行,这种情况是可以枚举出来的。

我们不妨如下定义,当铺满第n行后,“突出”到n+1行的情况只有一下几种:(插图来自于http://blog.sina.com.cn/s/blog_69c3f0410100vnhj.html

接下来进行状态转移:

  • a_n=a_{n-1}+b_{n-1}+c_{n-1}+d_{n-1}
  • b_n=a_{n-1}
  • c_n=a_{n-1}+e_{n-1}
  • dx_n=a_{n-1}+dy_{n-1}
  • dy_n=a_{n-1}+dx_{n-1}
  • e_n=c_{n-1}

令d_n=dx_n+dy_n则,状态转移方程为:

  • a_n=a_{n-1}+b_{n-1}+c_{n-1}+d_{n-1}
  • b_n=a_{n-1}
  • c_n=a_{n-1}+e_{n-1}
  • d_n=2*a_{n-1}+d_{n-1}
  • e_n=c_{n-1}

所以我们可以构造矩阵

[[1, 1, 1, 1, 0],
 [1, 0, 0, 0, 0],
 [1, 0, 0, 0, 1],
 [2, 0, 0, 1, 0],
 [0, 0, 1, 0, 0]]

接下来就是套模板了:

矩阵快速幂+DP解这道题的代码如下:

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<int> vec;
typedef vector<vec> mat;

int N, M;

mat mul(mat &A, mat &B) {
    mat C(A.size(), vec(B[0].size()));
    for (int i = 0; i < A.size(); i++) {
        for (int k = 0; k < B.size(); k++) {
            for (int j = 0; j < B[0].size(); j++) {
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % M;
            }
        }
    }
    return C;
}

mat pow(mat &A, ll n) {
    mat B(A.size(), vec(A[0].size()));
    for (int i = 0; i < A.size(); i++) {
        B[i][i] = 1;
    }
    while (n > 0) {
        if (n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}

int main() {
    while (~scanf("%d%d", &N, &M)) {
        if (!N && !M) break;
        mat A(5, vec(5));
        A[0][0] = A[0][1] = A[0][2] = A[0][3] = 1;
        A[1][0] = 1;
        A[2][0] = A[2][4] = 1;
        A[3][0] = 2; A[3][3] = 1;
        A[4][2] = 1;
        A = pow(A, N);
        printf("%d\n", A[0][0]);
    }
    return 0;
}

本人在校生,如有不足之处敬请指正!

又是一年高考季

三年前的今天,我是迷茫的。

我承认状态相当糟糕,于是只能反复安慰自己,该会的都会的,一切随缘。

从小就喜欢胡思乱想,那时我认为,四人帮每次总有人发挥失常,高考会不会轮到我。

一语成谶。

比平常考试少了40分左右。

也许命中注定我会来到这座美丽的海滨城市,开启一段新的旅程。

在中山广场对面的鸽子边,我突然感觉一切似曾相识。

我对妈妈说:“妈,我好像来过这里。”

妈妈摸了摸我的头说:

孩子,也许你本来就属于这里。

谁可知,这是我第一次踏上这块土地。

从此,我便疯狂地爱上了这座城市,我爱这天这山这海,我爱这美丽的邂逅。

如今妹妹也要高考了,我想打电话鼓励,却又放下手机。

高考本就是一次多么普通的考试呀,普通到我们都快忘了那年的作文题目,还有深恶痛绝的压轴大题。

高考不过是一次小小的随堂测试。她告诉你,你的青春将在此刻起舞。

高考也许就是离别,我们从此天南地北。

初夏,是绽放的时刻。

希望她心静如水,面对高考从容不迫。

愿手可摘星辰,一路有光。