基礎數學：圖論與信息論

微積分與概率論由此進：基礎數學：微積分和概率與統計-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))$

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/diannao/78742.shtml
繁體地址，請注明出處：http://hk.pswp.cn/diannao/78742.shtml
英文地址，請注明出處：http://en.pswp.cn/diannao/78742.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！