DP算法多路径探索说明.md 7.4 KB
DP算法多路径探索说明：为什么不是只从最优解往下？
❓ 问题
上一行只会从最优解往下进行吗？上一行的其他解会往下计算吗？
✅ 答案
不是！算法会从上一行的所有有效解（经过剪枝后最多30个）往下计算，而不是只从最优解往下。
📝 代码证据
关键代码片段
# 第604行：获取上一行所有有效位置
valid_prev_indices = [j for j in range(n_paddle) if dp[i-1][j] > -np.inf]
# 第619-621行：剪枝优化（但仍然是多个状态）
if len(valid_prev_indices) > 30:
valid_prev_indices.sort(key=lambda j: dp[i-1][j], reverse=True)
valid_prev_indices = valid_prev_indices[:30] # 保留前30个，不是只保留1个！
# 第637行：遍历所有有效的上一行状态
for prev_j in valid_prev_indices: # 遍历多个状态，不是只有一个
prev_score = dp[i-1][prev_j]
# ... 从每个prev_j往下计算
🎯 原因分析
原因1：动态规划的核心思想
DP算法的本质是：考虑所有可能的状态转移，找到全局最优解。
全局最优 ≠ 局部最优的累积
示例：
HTML行0 → OCR组[0,1,2] 得分: 0.98 ← 局部最优
HTML行0 → OCR组[0,1] 得分: 0.95 ← 次优解
如果只从最优解(0.98)往下：
HTML行1 → OCR组[3,4] 得分: 0.98 + 0.90 = 1.88
如果也从次优解(0.95)往下：
HTML行1 → OCR组[2,3,4] 得分: 0.95 + 0.95 = 1.90 ← 更优！
结论：次优解可能通向全局最优！
原因2：局部最优 ≠ 全局最优
当前行的最优解可能不是全局最优路径的起点。
示例场景
DP状态矩阵（简化）:
OCR组索引 j →
HTML 0 1 2 3 4 5
行↓
0 [0.98] [0.95] [0.92] - - -
↑ ↑ ↑
最优 次优 第三
1 - - [1.88] [1.90] [1.85] -
↑
全局最优！
来自次优解(0.95)
说明：
- HTML行0的最优解是
dp[0][0] = 0.98 - 但如果只从
dp[0][0]往下，得到dp[1][3] = 1.88 - 而从次优解
dp[0][1] = 0.95往下，得到dp[1][4] = 1.90（更优！）
原因3：多路径探索的必要性
保留多个候选路径，避免过早剪枝导致错过最优解。
场景：OCR检测不准确
HTML行0的匹配情况:
┌─────────────────────────────────────────────────────────────┐
│ 匹配1: OCR组[0,1,2] 相似度: 0.98 ← 看起来最优 │
│ 但OCR组2可能包含了一些噪声 │
│ │
│ 匹配2: OCR组[0,1] 相似度: 0.95 ← 次优，但更干净 │
│ 没有噪声，可能后续匹配更准确 │
└─────────────────────────────────────────────────────────────┘
如果只保留匹配1：
→ HTML行1可能因为OCR组2的噪声影响，匹配不佳
→ 全局得分: 0.98 + 0.85 = 1.83
如果也保留匹配2：
→ HTML行1从OCR组2开始，匹配更准确
→ 全局得分: 0.95 + 0.92 = 1.87 ← 更优！
📊 可视化说明
场景1：只从最优解往下（错误做法）
DP状态转移（错误）:
OCR组索引 j →
HTML 0 1 2 3 4 5
行↓
0 [0.98] [0.95] [0.92] - - -
│
└─→ 只从最优解往下
│
1 - - - [1.88] - -
↑
唯一路径
可能错过全局最优
场景2：从多个解往下（正确做法）
DP状态转移（正确）:
OCR组索引 j →
HTML 0 1 2 3 4 5
行↓
0 [0.98] [0.95] [0.92] - - -
│ │ │
└─────┴─────┴─→ 从多个解往下探索
│ │ │
1 - - [1.88] [1.90] [1.85] -
↑ ↑
路径1 路径2（更优！）
最终选择: dp[1][4] = 1.90（来自dp[0][1]）
🔍 剪枝策略的平衡
为什么保留30个而不是全部？
原因：平衡准确性和性能
# 如果保留所有状态
valid_prev_indices = [0, 1, 2, ..., 47] # 48个状态
计算量: 48 × 15 × 4 = 2,880 次匹配/行
总计算量: 2,880 × 7 = 20,160 次
# 如果只保留最优解
valid_prev_indices = [0] # 1个状态
计算量: 1 × 15 × 4 = 60 次匹配/行
总计算量: 60 × 7 = 420 次
问题: 可能错过全局最优解 ❌
# 如果保留前30个（当前策略）
valid_prev_indices = [0, 1, 2, ..., 29] # 30个状态
计算量: 30 × 15 × 4 = 1,800 次匹配/行
总计算量: 1,800 × 7 = 12,600 次
平衡: 既保证准确性，又控制计算量 ✅
剪枝的合理性
保留前30个得分最高的状态，通常已经包含了所有有希望通向全局最优的路径。
得分分布示例:
dp[0][0] = 0.98 ← 第1名
dp[0][1] = 0.95 ← 第2名
dp[0][2] = 0.92 ← 第3名
...
dp[0][29] = 0.65 ← 第30名
dp[0][30] = 0.20 ← 第31名（被剪枝）
分析：
- 前30个状态得分都在0.65以上，有希望通向全局最优
- 第31个状态得分只有0.20，即使后续匹配完美，也很难超过前30个
- 剪枝是安全的 ✅
💡 实际案例
案例：银行流水表匹配
HTML行0（表头信息行）的匹配情况:
匹配1: OCR组[0,1,2] 得分: 0.98
文本: "部门department:01372403999柜员searchteller:ebf0000打印日期..."
但OCR组2可能包含了一些后续行的内容
匹配2: OCR组[0,1] 得分: 0.95
文本: "部门department:01372403999柜员searchteller:ebf0000"
更精确，没有混入后续内容
匹配3: OCR组[0,1,2,3] 得分: 0.92
文本: "部门department:...查询起日..."
包含了太多内容，可能影响后续匹配
如果只从匹配1往下：
HTML行1 → OCR组[3,4] 得分: 0.98 + 0.85 = 1.83
（因为OCR组2已经消耗了一些内容，导致HTML行1匹配不佳）
如果也从匹配2往下：
HTML行1 → OCR组[2,3,4] 得分: 0.95 + 0.92 = 1.87 ← 更优！
（从OCR组2开始，HTML行1能匹配到更完整的内容）
结论：保留多个候选路径，最终找到全局最优解！
📋 总结
核心要点
不是只从最优解往下
- 算法会从上一行的所有有效解（最多30个）往下计算
- 这是动态规划的标准做法
原因
- 局部最优 ≠ 全局最优
- 次优解可能通向全局最优
- 多路径探索保证找到全局最优解
剪枝策略
- 保留前30个得分最高的状态
- 平衡准确性和性能
- 通常已经包含了所有有希望的路径
实际效果
- 在保证准确性的同时，控制计算量
- 避免错过全局最优解
- 提高算法的鲁棒性
🎓 算法设计启示
这个设计体现了动态规划算法的精髓：
- 状态空间探索：考虑所有可能的状态转移
- 剪枝优化：在保证准确性的前提下，减少计算量
- 全局最优：通过多路径探索，找到全局最优解
这就是为什么这个算法能够准确匹配HTML行与OCR组的原因！