强化学习笔记
强化学习
强化学习的总体目标:寻找最优策略。
关键名词
智能体(Agent)
状态(State):智能体相对于环境的状态 $s∈S$
状态空间(State space):把所有状态放在一起,所有状态的集合(set)$S={s_1,s_2,…,s_n}$
动作(Action):对于每个状态,所可能采取的行动 $a∈A(s)$
动作空间(Action space):某状态下所可能采取的所有动作的集合(动作依赖于状态)$A(s)={a_1,a_2,…,a_m}$
状态转移(State transition):通过采取一个动作,智能体从一个状态进入另一个
状态转移概率(State transition probability):用条件概率描述状态转移 $P(s′∣s,a)$
策略(Policy):策略告诉智能体在某一状态下应采取什么行动
在数学上,策略被定义为在给定状态 $s$ 时选择行动 $a$ 的概率,即 $π(a∣s)$。
策略 $π$ 需要满足以下条件:对于所有状态 $s∈S$,所有可能行动 $a∈A(s)$ 的概率之和等于 1:
\sum_{a∈A(s)}π(a∣ ...
Hello World
Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.
Quick StartCreate a new post1$ hexo new '[post]' "title"
More info: Writing
Run server1$ hexo server
More info: Server
Generate static files1$ hexo generate
More info: Generating
Deploy to remote sites1$ hexo deploy
More info: Deployment
数位DP样题
数位dp的题目一般会问,某个区间内,满足某种性质的数的个数。
利用前缀和,比如求区间[l,r]中的个数,转化成求[0,r]的个数 [0,l-1]的个数。
利用树的结构来考虑(按位分类讨论)P8764 [蓝桥杯 2021 国 BC] 二进制问题
12345678910111213141516171819202122232425262728293031323334353637383940#include<bits/stdc++.h>using namespace std;const int N=70;long long f[N][N];long long n,k;void init(){ for(int i=0;i<N;i++) for(int j=0;j<=i;j++) if(!j) f[i][j]=1; else f[i][j]=f[i-1][j]+f[i-1][j-1];}long long dp(long long n){ if(!n) return 0; vect ...
奎恩-麦克拉斯基化简法 (Q-M 法)化简逻辑代数式
《数字电子技术基础(第6版)》(阎石)极度暴力的模拟实现,不保熟的代码QAQ:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158#include<bits/stdc++.h>using namespace std;int n,m,cnt;vector<int>vec[11],temp;int ...
FFT求多项式乘积
引入之前在b站上看到了一些介绍FFT的视频:
《快速傅里叶变换(FFT)——有史以来最巧妙的算法?》
《这个算法改变了世界》
于是打算写一篇记录一下qwq(本博客中的截图基本上来源于第一个视频)
Fast Fourier Transform 是一种能在$O(nlogn)$的时间内将一个用系数表示的多项式转化成点值表示。
$P(x)=p_0+p_1x+p_2x^2+…+p_dx^d$
系数表示法:$[p_0,p_1,p_2,…,p_d]$
点值表示法:${(x_0,P(x_0),(x_1,P(x_1),…,(x_d,P(x_d))}$
(n+1个不同点可以确定一个n次的多项式:可以用矩阵列式求解)
当我们试图算两个多项式相乘的结果:
$A(x)=a_0+a_1x+…+a_dx^d$
$B(x)=b_0+b_1x+…+b_dx^d$
传统的做法需要$O(n^2)$,而如果我们先求出若干个点的坐标(多少个点根据最后算出的会是几次多项式而定,比如A是三次多项式,B是五次多项式,算出来的C会是八次多项式,那么就需要找九个点),最后再根据这些点把多项式还原成系数表示,但是对于每个点,知道一个 ...
Course Review
Through this semester’s study, I understand the basic framework of a paper, which generally includes title, abstract, introduction, literature review, experiment/method, results, discussion, conclusion, references and appendix.
The title of the paper seeks to be concise, accurate, which can reflect the core theme of the paper.
The abstract is a short article with complete logic. It should briefly introduce the whole paper’s aim, process, method, research result, and conclusion. The purpose of w ...
二分图的判定及最大匹配
如果一张无向图的N个结点可以分成A,B两个非空集合,其中$A\cap B=\emptyset$,并且在同一集合内的点之间都没有边相连,则称这张图为二分图。
二分图判定定理:一张图是二分图,当且仅当图中不存在奇环(长度为奇数的环)。
P1330 封锁阳光大学
染色法判定:尝试用黑白两色标记,当一个结点被标记后,它的所有相邻结点应该被标记与之相反的颜色,若该标记过程中出现冲突,则说明图中存在奇环。
下用BFS、DFS、并查集分别实现。
BFS123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include<bits/stdc++.h>using namespace std;const int N=1e4+10,M=2e5+10;int head[N],ver[M],nex[M],vis[N];int n,m,u,v,tot=0,ok=1;int sum[5],ans;void add(int u ...
LIS LCS LCIS相关问题
P1020 [NOIP1999 普及组] 导弹拦截P1020 [NOIP1999 普及组] 导弹拦截
导弹拦截应该是接触DP的第一题(只不过洛谷上的数据加强了,按照上图的$O(N^2)$做法过不去QAQ可以改用二分。
Dilworth定理:偏序集能划分成的最少的全序集个数等于最大反链的元素个数
把一个数列划分成最少的最长不升子序列的数目就等于这个数列的最长上升子序列的长度(LIS)
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include<bits/stdc++.h> using namespace std;int a[100010],LDS[100010],LIS[100010];int main(){ int x,i=0,len=1; while(~scanf("%d",&x)) a[i++]=x; LDS[0]=a[0]; for(int j=1;j<i;j++) { if(a[ ...
矢量场的散度和旋度
散度散度是一个标量,用于体现矢量场各点发散的强弱程度。对于矢量场${ \textbf{F}}$:
${\color{DarkRed} div \textbf{F} = \displaystyle \lim{ \Delta V \to 0}\tfrac{\oint{S} \textbf{F}\cdot d\textbf{S}}{\Delta V} = \nabla \, \cdot \, \textbf{F}}$
${ div \textbf{F}}$描述通量源的密度。
散度定理(高斯定理):
${\color{Red} \int{V}\nabla\,\cdot \,\textbf{F}dV = \oint{S}\textbf{F}\,\cdot \,d\textbf{S}}$
旋度散度是一个矢量,用于体现矢量场各点附近环流的强弱程度。对于矢量场${ \textbf{F}}$:
${\color{DarkRed} rot \textbf {F} = \displaystyle \lim{ \Delta S \to 0}\tfrac{1}{\Delta S}\oint{S} \tex ...