基础数学：图论与信息论-EW帮帮网

微积分与概率论由此进：基础数学：微积分和概率与统计-CSDN博客

线代与优化理论由此进：基础数学：线性代数与优化理论-CSDN博客

数值分析与离散数学由此进：基础数学：数值分析与离散数学-CSDN博客

四、图论与搜索算法

1.图结构基础

(1) 图的表示方法

邻接矩阵：

定义：对于图 $G=(V,E)$ ，邻接矩阵 $A\in \left \{ 0,1 \right \}^{|V| \times |V|}$ ，其中

$A_{ij}=\left\{\begin{matrix} 1 \quad (i,j)\in E\\ 0 \quad otherwise \end{matrix}\right.$

适用：稠密图的存储，快速判断节点间是否联通

邻接表：

定义：为每个节点存储其邻居列表，例如 $Adj[v]=\left \{ u|(v,u)\in E \right \}$

适用：稀疏图的高效存储，节省空间

权重图的扩展：

定义：邻接矩阵元素 $A_{ij}$ 表示边权，邻接表存储 $(u,w_{vu})$ 对

(2) 树与图遍历

树的性质：

无环联通图，任意两节点间有唯一路径

节点数 $|V|=|E|+1$

深度优先搜索（DFS）：

算法步骤：

1.从起点出发，访问未被访问的邻居节点

2.递归访问邻居的邻居，直到无法继续

3.回溯到最近未探索完的节点继续

复杂度：时间复杂度 $O(|V|+|E|)$ ，空间复杂度 $O(|V|)$ （递归栈）

应用：树形思维（ToT）中的深度探索

广度优先搜索（BFS）：

算法步骤：

1.使用队列管理待访问节点

2.访问当前节点的所有邻居，再访问邻居的邻居

复杂度：时间复杂度 $O(|V|+|E|)$ ，空间复杂度 $O(|V|)$ （队列）

应用：寻找最短路径（无权图）

2.最短路径算法

(1)Dijkstra算法

核心思想：贪心策略，逐步扩展当前最短路径
数学描述：

初始化距离 $d(s)=0$ ，其他节点 $d(u)=\infty$

优先队列按距离排序，每次取出距离最小的节点 $u$

对 $u$ 的邻居 $v$ ，松弛操作：

$d(v)=min(d(v),d(u)+w(u,v))$

复杂度：使用优先队列（如斐波那契堆）： $O(|E|+|V|log|V|)$
限制：仅适用于非负权边

(2)A*算法

启发式搜索：

定义评估函数 $f(n)=g(n)+h(n)$ ，其中

$g(n)$ ：从起点到节点 $n$ 的实际代价

$h(n)$ ：启发函数，估计 $n$ 到终点的代价

算法步骤：

1.优先队列按 $f(n)$ 排序

2.每次扩展 $f(n)$ 最小的节点

3.到达终点或队列为空时终止

应用：PRM路径规划中的全局搜索

3.搜索策略优化

(1) 剪枝策略

Alpha-Beta算法：

用于博弈树搜索，剪除对最终决策无影响的分支

核心思想：若某分支的评估值已不可能优于当前最优解，则停止搜索

应用场景：树形思维（ToT）中减少无效路径的探索

(2)多路径生成与自洽性验证

蒙特卡洛树搜索（MCTS）：

四步骤：选择（Selection）、扩展（Expansion）、模拟（Simulation）、回溯（Backpropagation）

选择策略：

使用Upper Confidence Bound（UCB）平衡探索与利用：

$UCB_{v_{i}}=\frac{Q(v_{i})}{N(v_{i})}+c\sqrt{\frac{ln(N(v))}{N(v_{i})}}$

其中 $Q(v_{i})$ 为节点价值， $N(v_{i})$ 为访问次数， $c$ 为探索系数

自洽性：

通过生成多条路径 $\left \{ p_1,p_2,...,p_k \right \}$ ，投票选择最一致的答案

投票规则：多数投票，广义投票等...

4.应用

(1)PRM路径规划：从理论到实践：带你快速学习基于PRM的三种搜索方法-CSDN博客

流程：

采样阶段：在构型空间中随机采样节点（蒙特卡洛采样）
连接阶段：对邻近节点尝试连接，过滤碰撞边
查询阶段：使用A*或Dijkstra算法在路线图中搜索路径

(2)树形思维：从理论到实践：树形思维探索(ToT)-CSDN博客

树结构构建：

根节点为初始问题，子节点为推理步骤的中间假设
节点扩展策略：基于概率或启发式生成子节点

(3)并行采样与顺序修订：从理论到实践：并行采样+顺序修订的联合优化-CSDN博客

联合优化框架：

并行采样：生成多条候选路径 $\left \{ p_i \right \}$
顺序修订：对每条路径局部优化（如梯度下降修正参数）
聚合结果：选择综合得分最高的路径

5.核心公式

Dijkstra松弛操作： $d(v)=min(d(v),d(u)+w(u,v))$

A*评估函数： $f(n)=g(n)+h(n)$

UCB选择策略： $UCB_{v_{i}}=\frac{Q(v_{i})}{N(v_{i})}+c\sqrt{\frac{ln(N(v))}{N(v_{i})}}$

五、信息论

1.熵与信息度量

(1)信息熵

定义：信息熵衡量随机变量 $X$ 的不确定性，定义为：

$H(X)=-\sum_{x\in X}^{}P(x)logP(x)$

单位：以2为底的对数单位为比特（bits），以自然对数 ln⁡ln 为单位为奈特（nats）

直观解释：熵越大，不确定性越高。例如，均匀分布的熵最大

示例：抛一枚公平硬币，P(正面) = P(反面) = 0.5，熵为：

$H(X)=-0.5log0.5-0.5log0.5=1\:bit$

若硬币不均匀（如P(正面) = 0.9），则熵降低为：

$H(X)=-0.9log0.9-0.1log0.1\approx 0.469 \:bit$

(2)交叉熵

定义：衡量用分布 $Q$ 近似真实分布 $P$ 的额外成本：

$H(P,Q)=-\sum_{x}^{}P(x)logQ(x)$

应用：

分类任务的损失函数（如交叉熵损失）

语言模型训练中，最小化预测分布与真实分布的交叉熵

(3)KL散度

定义：衡量分布 $P$ 与 $Q$ 的差异：

$D_{KL}(P||Q)=\sum_{x}^{}P(x)log\frac{(P(x))}{Q(x)}=H(P,Q)-H(P)$

性质：非负性 $D_{KL}(P||Q)\geq 0$ ，非对称性 $D_{KL}(P||Q) \neq D_{KL}(Q||P)$

应用：

变分推断中，最小化 $D_{KL}(Q||P)$ 以近似后验分布

模型蒸馏中，让学生模型分布逼近教师模型

(4)互信息

定义：衡量两个随机变量 $X$ 和 $Y$ 的相关性：

$I(X;Y)=H(X)-H(X||Y)=H(Y)-H(Y||X)=D_{KL}(P(X,Y)||P(X)P(Y))$

应用：

特征选择：选择与目标变量互信息高的特征

多路径生成：筛选与问题相关性高的推理路径

2.编码理论

(1)压缩编码基础

霍夫曼编码（Huffman Coding）：

原理：为高频符号分配短码，低频符号分配长码，构建最优前缀码

数学形式：最小化平均码长 $L=\sum_{x}^{}P(x)l(x)$ ，其中 $l(x)$ 是符号 $x$ 的码长

算术编码（Arithmetic Coding）：

原理：将整个输入序列映射到一个区间 [0,1)，用区间长度编码概率

优势：接近香农熵极限，尤其适合高阶统计依赖的数据

(2)BPE算法的数学原理：从理论到实践：字节对编码(BPE)算法-CSDN博客

3.应用

(1)注意力机制中的信息瓶颈：从理论到实践：Pytorch实现注意力机制到Triton优化-CSDN博客

(2)模型不确定性的量化：从理论到实践：absmax、zeropoint和LLM.int8()在gpt-2的应用-CSDN博客

(3)多路径生成的自洽性验证：从理论到实践：CoT的多路径生成与自洽性-CSDN博客

4.核心公式

信息熵： $H(X)=-\sum_{x\in X}^{}P(x)logP(x)$

交叉熵： $H(P,Q)=-\sum_{x}^{}P(x)logQ(x)$

KL散度： $D_{KL}(P||Q)=\sum_{x}^{}P(x)log\frac{(P(x))}{Q(x)}=H(P,Q)-H(P)$

互信息： $I(X;Y)=H(X)-H(X||Y)=H(Y)-H(Y||X)=D_{KL}(P(X,Y)||P(X)P(Y))$

基础数学：图论与信息论