编辑“︁随机化近似算法”︁

{{DISPLAYTITLE:随机化近似算法}}  
'''随机化近似算法'''（Randomized Approximation Algorithms）是一类通过引入随机性来高效求解难解问题的算法，能够在多项式时间内提供近似最优解。这类算法在[[NP难问题]]、组合优化和大型数据处理中尤为重要，其特点是牺牲精确性换取计算效率，同时保证解的质量以高概率满足需求。  

== 概述 ==  
随机化近似算法结合了'''随机性'''与'''近似性'''两大核心思想：  
* '''随机性'''：通过随机选择（如随机采样、随机决策）避免最坏情况，降低时间复杂度。  
* '''近似性'''：允许算法返回的解与最优解存在一定误差，但保证误差范围可控。  

这类算法的性能通常用以下指标衡量：  
* '''近似比'''（Approximation Ratio）：算法解与最优解比值的上界。  
* '''成功概率'''：算法返回优质解的概率（例如 ≥ 2/3）。  

== 经典算法示例 ==  

=== 随机化最小割算法（Karger's Algorithm） ===  
用于求解无向图的最小割问题，通过随机收缩边来逼近最优解。  

==== 算法步骤 ====  
1. 随机选择一条边并收缩其两端点。  
2. 重复步骤1，直到图中仅剩两个顶点。  
3. 剩余边构成一个候选割集。  

==== 代码实现 ====  
<syntaxhighlight lang="python">  
import random  

def karger_min_cut(graph):  
    while len(graph) > 2:  
        u = random.choice(list(graph.keys()))  
        v = random.choice(graph[u])  
        # 收缩边 (u, v)  
        for node in graph[v]:  
            if node != u:  
                graph[u].append(node)  
                graph[node].remove(v)  
                graph[node].append(u)  
            graph[u].remove(v)  
        del graph[v]  
    # 返回剩余边数（即割集大小）  
    return len(graph[list(graph.keys())[0]])  

# 示例输入（邻接表表示）  
graph = {  
    'A': ['B', 'C'],  
    'B': ['A', 'C', 'D'],  
    'C': ['A', 'B', 'D'],  
    'D': ['B', 'C']  
}  
print("候选割集大小:", karger_min_cut(graph))  
</syntaxhighlight>  

==== 输出示例 ====  
<pre>  
候选割集大小: 2  
</pre>  

=== 随机化近似算法分析 ===  
Karger算法的时间复杂度为<math>O(n^2)</math>，成功概率为<math>\Omega(1/n^2)</math>。通过重复运行<math>O(n^2 \log n)</math>次，可高概率得到最小割。  

== 实际应用案例 ==  
'''案例：推荐系统的相似性估计'''  
在大规模用户行为数据中，计算用户间的精确相似度（如Jaccard系数）代价高昂。随机化近似算法（如MinHash）通过哈希映射和随机采样，将计算复杂度从<math>O(n^2)</math>降至<math>O(n)</math>，同时保证相似度估计误差可控。  

<mermaid>  
graph LR  
    A[原始数据] --> B(MinHash签名生成)  
    B --> C[随机投影到低维空间]  
    C --> D[近似相似度计算]  
</mermaid>  

== 数学基础 ==  
随机化近似算法的理论支撑包括：  
* '''Chernoff Bound'''：控制随机变量偏离期望的概率。  
* '''马尔可夫不等式'''：<math>P(X \geq a) \leq \frac{E[X]}{a}</math>。  

== 总结 ==  
随机化近似算法通过巧妙引入随机性，为传统难解问题提供了高效解决方案。其核心优势在于：  
* 适用于大规模数据或高复杂度问题。  
* 允许灵活权衡精度与效率。  
* 理论保证（如概率界限）确保可靠性。  

初学者可通过实现Karger算法或MinHash等案例深入理解其设计思想，进阶者可进一步研究[[拉斯维加斯算法]]与[[蒙特卡洛算法]]的分类差异。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:随机化算法]]