启发式搜索一、概念极简背诵版状态空间问题所有合法状态 状态转移规则构成的集合搜索就是在状态空间里找路径。图灵机抽象计算模型由读写头、纸带、状态集组成能刻画所有可计算问题。可行解满足问题全部约束条件的一个解不一定最好。目标函数用来衡量解好坏的函数求最大/最小。最优解所有可行解里让目标函数取到极值的解。P vs NPP多项式时间可求解的问题NP多项式时间可验证答案的问题P vs NP猜想 P 是否等于 NP至今未证明。二、算法广度搜索 BFS队列FIFO一层一层向外扩展代价相同时可得最优解完备。深度搜索 DFS栈LIFO一路往深处钻走不通再回溯不保证最优省空间。Dijkstra求单源最短路径边权≥0。递推dist[v]min(dist[v],dist[u]w(u,v))dist[v]\min(dist[v],dist[u]w(u,v))dist[v]min(dist[v],dist[u]w(u,v))表格法维护距离表每次选出距离最小未访问点松弛邻接点。A算法*MCTS 蒙特卡洛树搜索4步循环①选择从根向下用UCT选到叶子节点②扩展给叶子新增子节点③模拟从新节点随机走直到终止得到结果④回溯把胜负结果往回更新整条路径节点统计值EoH 是用大模型做进化搜索自动生成启发式算法。把启发式方案当个体大模型负责生成、修改方案靠效果反馈不断优化用来解决组合优化问题。ReEvo 在 EoH 的基础上加了反思一边看当前方案好坏一边记住之前的经验指导大模型改进找更好的启发式方案搜索效率更高。强化学习复习材料速记版1.增量蒙特卡洛更新核心思想不用每次存完整回报序列再求平均而是边采样边更新。公式Q(St,At)←Q(St,At)1N(Gt−Q(St,At))Q(S_t, A_t) \leftarrow Q(S_t, A_t) \frac{1}{N}(G_t - Q(S_t, A_t))Q(St,At)←Q(St,At)N1(Gt−Q(St,At))2.ε-greedy Exploration为什么能改善策略避免局部最优纯贪心ε0会一直选当前看起来最好的可能错过更优动作随机探索给了纠错机会。持续更新 Q 值不探索就永远采不到次优动作的样本Q 值估计不准探索保证所有动作都有机会被采样估值更准。ε 衰减前期 ε 大多探索后期 ε 小多利用兼顾找方向和收敛稳。3.Q-Learning 迭代公式公式离线策略 TD 更新Q(St,At)←Q(St,At)α[Rt1γmaxaQ(St1,a)−Q(St,At)]Q(S_t, A_t) \leftarrow Q(S_t, A_t) \alpha \left[ R_{t1} \gamma \max_a Q(S_{t1}, a) - Q(S_t, A_t) \right]Q(St,At)←Q(St,At)α[Rt1γmaxaQ(St1,a)−Q(St,At)]4. PPO中Critic、Actor、Reward如何训练Loss定义及意义Actor策略网络输出动作分布。Loss裁剪代理目标限制新旧策略差距。意义在保证策略稳定的前提下提升优势大动作的概率。Critic价值网络输出状态价值。LossMSE 损失。意义评估这个状态好不好给 Actor 提供梯度信号。Reward环境给出的即时奖励用来计算回报、优势函数是整个训练的监督信号不单独训练网络。深度学习基础练习1. 一般卷积神经网络的构成及原理CNN 由输入层、卷积层、激活层、池化层、全连接层、输出层构成。原理利用局部感受视野、权值共享通过卷积核滑动提取图像局部特征激活函数引入非线性池化压缩特征、降低维度最后全连接层整合高层特征通过反向传播更新参数自动学习特征完成预测。2. 前向神经网络的一般训练过程输入样本前向传播计算预测输出计算预测和标签的损失 loss反向传播链式法则求各权重梯度梯度下降更新权重循环迭代直到损失收敛。3. 链式法则-对权值的偏导4. Word2Vec Skip-Gram Model输入中心词预测它的上下文周边词用浅层网络学习词向量目标让相近语义的词向量在空间离得近用负采样 / 层次 softmax 加速训练。其他
启发式搜索一、概念极简背诵版状态空间问题所有合法状态 状态转移规则构成的集合搜索就是在状态空间里找路径。图灵机抽象计算模型由读写头、纸带、状态集组成能刻画所有可计算问题。可行解满足问题全部约束条件的一个解不一定最好。目标函数用来衡量解好坏的函数求最大/最小。最优解所有可行解里让目标函数取到极值的解。P vs NPP多项式时间可求解的问题NP多项式时间可验证答案的问题P vs NP猜想 P 是否等于 NP至今未证明。二、算法广度搜索 BFS队列FIFO一层一层向外扩展代价相同时可得最优解完备。深度搜索 DFS栈LIFO一路往深处钻走不通再回溯不保证最优省空间。Dijkstra求单源最短路径边权≥0。递推dist[v]min(dist[v],dist[u]w(u,v))dist[v]\min(dist[v],dist[u]w(u,v))dist[v]min(dist[v],dist[u]w(u,v))表格法维护距离表每次选出距离最小未访问点松弛邻接点。A算法*MCTS 蒙特卡洛树搜索4步循环①选择从根向下用UCT选到叶子节点②扩展给叶子新增子节点③模拟从新节点随机走直到终止得到结果④回溯把胜负结果往回更新整条路径节点统计值EoH 是用大模型做进化搜索自动生成启发式算法。把启发式方案当个体大模型负责生成、修改方案靠效果反馈不断优化用来解决组合优化问题。ReEvo 在 EoH 的基础上加了反思一边看当前方案好坏一边记住之前的经验指导大模型改进找更好的启发式方案搜索效率更高。强化学习复习材料速记版1.增量蒙特卡洛更新核心思想不用每次存完整回报序列再求平均而是边采样边更新。公式Q(St,At)←Q(St,At)1N(Gt−Q(St,At))Q(S_t, A_t) \leftarrow Q(S_t, A_t) \frac{1}{N}(G_t - Q(S_t, A_t))Q(St,At)←Q(St,At)N1(Gt−Q(St,At))2.ε-greedy Exploration为什么能改善策略避免局部最优纯贪心ε0会一直选当前看起来最好的可能错过更优动作随机探索给了纠错机会。持续更新 Q 值不探索就永远采不到次优动作的样本Q 值估计不准探索保证所有动作都有机会被采样估值更准。ε 衰减前期 ε 大多探索后期 ε 小多利用兼顾找方向和收敛稳。3.Q-Learning 迭代公式公式离线策略 TD 更新Q(St,At)←Q(St,At)α[Rt1γmaxaQ(St1,a)−Q(St,At)]Q(S_t, A_t) \leftarrow Q(S_t, A_t) \alpha \left[ R_{t1} \gamma \max_a Q(S_{t1}, a) - Q(S_t, A_t) \right]Q(St,At)←Q(St,At)α[Rt1γmaxaQ(St1,a)−Q(St,At)]4. PPO中Critic、Actor、Reward如何训练Loss定义及意义Actor策略网络输出动作分布。Loss裁剪代理目标限制新旧策略差距。意义在保证策略稳定的前提下提升优势大动作的概率。Critic价值网络输出状态价值。LossMSE 损失。意义评估这个状态好不好给 Actor 提供梯度信号。Reward环境给出的即时奖励用来计算回报、优势函数是整个训练的监督信号不单独训练网络。深度学习基础练习1. 一般卷积神经网络的构成及原理CNN 由输入层、卷积层、激活层、池化层、全连接层、输出层构成。原理利用局部感受视野、权值共享通过卷积核滑动提取图像局部特征激活函数引入非线性池化压缩特征、降低维度最后全连接层整合高层特征通过反向传播更新参数自动学习特征完成预测。2. 前向神经网络的一般训练过程输入样本前向传播计算预测输出计算预测和标签的损失 loss反向传播链式法则求各权重梯度梯度下降更新权重循环迭代直到损失收敛。3. 链式法则-对权值的偏导4. Word2Vec Skip-Gram Model输入中心词预测它的上下文周边词用浅层网络学习词向量目标让相近语义的词向量在空间离得近用负采样 / 层次 softmax 加速训练。其他
