启发式搜索

一、概念（极简背诵版）

1. 状态空间：问题所有合法状态 + 状态转移规则构成的集合，搜索就是在状态空间里找路径。
2. 图灵机：抽象计算模型，由读写头、纸带、状态集组成；能刻画所有可计算问题。
3. 可行解：满足问题全部约束条件的一个解（不一定最好）。
4. 目标函数：用来衡量解好坏的函数，求最大/最小。
5. 最优解：所有可行解里，让目标函数取到极值的解。
6. P vs NP
   • P：多项式时间可求解的问题；
   • NP：多项式时间可验证答案的问题；
   • P vs NP：猜想 P 是否等于 NP（至今未证明）。

二、算法

1. 广度搜索 BFS
   队列FIFO，一层一层向外扩展；代价相同时可得最优解，完备。

2. 深度搜索 DFS
   栈LIFO，一路往深处钻，走不通再回溯；不保证最优，省空间。

3. 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))
   表格法：维护距离表，每次选出距离最小未访问点，松弛邻接点。

4. A算法*
   

5. 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（为什么能改善策略）

1. 避免局部最优：纯贪心（ε=0）会一直选当前看起来最好的，可能错过更优动作；随机探索给了"纠错机会"。
2. 持续更新 Q 值：不探索就永远采不到次优动作的样本，Q 值估计不准；探索保证所有动作都有机会被采样，估值更准。
3. ε 衰减：前期 ε 大（多探索），后期 ε 小（多利用），兼顾"找方向"和"收敛稳"。

3.Q-Learning 迭代公式

公式（离线策略 TD 更新）：

Q(St,At)←Q(St,At)+α[Rt+1+γmax⁡aQ(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​+γmaxa​Q(St+1​,a)−Q(St​,At​)]

4. PPO中Critic、Actor、Reward如何训练（Loss定义及意义）

• Actor（策略网络）：输出动作分布。
  Loss：裁剪代理目标，限制新旧策略差距。意义：在保证策略稳定的前提下，提升优势大动作的概率。
• Critic（价值网络）：输出状态价值。
  Loss：MSE 损失。意义：评估这个状态好不好，给 Actor 提供梯度信号。
• Reward：环境给出的即时奖励，用来计算回报、优势函数，是整个训练的监督信号，不单独训练网络。

深度学习基础练习

1. 一般卷积神经网络的构成及原理

CNN 由输入层、卷积层、激活层、池化层、全连接层、输出层构成。

原理：利用局部感受视野、权值共享，通过卷积核滑动提取图像局部特征，激活函数引入非线性，池化压缩特征、降低维度；最后全连接层整合高层特征，通过反向传播更新参数，自动学习特征完成预测。

2. 前向神经网络的一般训练过程

1. 输入样本，前向传播，计算预测输出；
2. 计算预测和标签的损失 loss；
3. 反向传播，链式法则求各权重梯度；
4. 梯度下降更新权重；
5. 循环迭代，直到损失收敛。

3. 链式法则-对权值的偏导

4. Word2Vec Skip-Gram Model

输入中心词，预测它的上下文周边词；
用浅层网络，学习词向量，目标：让相近语义的词，向量在空间离得近；用负采样 / 层次 softmax 加速训练。

其他