启发式搜索
一、概念（极简背诵版）
- 状态空间：问题所有合法状态 + 状态转移规则构成的集合，搜索就是在状态空间里找路径。
- 图灵机：抽象计算模型，由读写头、纸带、状态集组成；能刻画所有可计算问题。
- 可行解：满足问题全部约束条件的一个解（不一定最好）。
- 目标函数：用来衡量解好坏的函数，求最大/最小。
- 最优解：所有可行解里，让目标函数取到极值的解。
- P vs NP
- P：多项式时间可求解的问题；
- 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)+α[Rt+1+γmaxaQ(St+1,a)−Q(St,At)]Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t) \right]Q(St,At)←Q(St,At)+α[Rt+1+γmaxaQ(St+1,a)−Q(St,At)]
4. PPO中Critic、Actor、Reward如何训练（Loss定义及意义）
- Actor（策略网络）：输出动作分布。
Loss：裁剪代理目标，限制新旧策略差距。意义：在保证策略稳定的前提下，提升优势大动作的概率。 - Critic（价值网络）：输出状态价值。
Loss：MSE 损失。意义：评估这个状态好不好，给 Actor 提供梯度信号。 - Reward：环境给出的即时奖励，用来计算回报、优势函数，是整个训练的监督信号，不单独训练网络。
深度学习基础练习
1. 一般卷积神经网络的构成及原理
CNN 由输入层、卷积层、激活层、池化层、全连接层、输出层构成。
原理：利用局部感受视野、权值共享，通过卷积核滑动提取图像局部特征，激活函数引入非线性，池化压缩特征、降低维度；最后全连接层整合高层特征，通过反向传播更新参数，自动学习特征完成预测。
2. 前向神经网络的一般训练过程
- 输入样本，前向传播，计算预测输出；
- 计算预测和标签的损失 loss；
- 反向传播，链式法则求各权重梯度；
- 梯度下降更新权重；
- 循环迭代，直到损失收敛。
3. 链式法则-对权值的偏导
4. Word2Vec Skip-Gram Model
输入中心词，预测它的上下文周边词；
用浅层网络，学习词向量，目标：让相近语义的词，向量在空间离得近；用负采样 / 层次 softmax 加速训练。