2.2 Global Comparison using Dynamic Programming

2.2 利用动态规划进行全局比对

• 输入输出

  

• 比对方法

  • 穷举法(理论可行，实践难)：

    

  • 动态规划法

    • 最好的比对 = 之前最好的比对 + 当前最好的比对

      

    • 全局最优解 = 局部最优解之和

      

    • Step

      

    • Formula

      

      例：

      

      1. 边边的格子

         

         左方和上方对应的格子 0 + -5 = -5 -5 + -5 = -10 -10 + -5 = -15

      2. 中间的格子

         

         三个来源：

         1、左方格子 + -5 = -10

         2、上方格子 + -5 = -10

         3、 斜上方格子 + 替换矩阵中的AA对应分数 = 2

         

         取最大值为2 并标出来源指向箭头

      3. 中间的格子

         

         问：为啥会有两个箭头指向3？

         答：说明有两个来源

         左方格子 + -5 = -3

         上方格子 + -5 = -15

         斜上方格子 + 2 = -3

      4. 从最后回溯得到最优比对结果

         

         向上向左的箭头对应着空即 ‘-’，斜对角的箭头就对应着表格里的横纵双方