1、其思路为，遍历所有可行路径，比喻成现实生活中的路径选择问题，地点A到B有很多路径，遍历所有路径，而不重复的方法是，每一条路径的最后一个分支点，进行封闭，就像施工封闭一样。从而实现路径不重复访问。
2、首先构造一个求字斤谯噌最大值以及数据来源的方法。以获得我们需要的信息。#calculate the maximum number and the directiondef maximum(one ,two ,three): max=((one if one>two else two) if (one if one>two else two)>three else three) pos=0 if max==one: if max==two: if max==three: pos=7 else: pos=4 else: if max==three: pos=6 else: pos=1 else: if max==two: if max==three: pos=5 else: pos=2 else: pos=3 return max,pos
3、再构建一个填充矩阵的方法，填充数值。def HD(s,t): import numpy as np h=np.zeros((len(s)+1,len(t)+1)) d=np.zeros((len(s)+1,len(t)+1)) for i in range(len(s)+1): h[i][0]=-2*i if i!=0: d[i][0]=1 for i in range(len(t)+1): h[0][i]=-2*i if i!=0: d[0][i]=3 for i in range(1,len(s)+1): for j in range(1,len(t)+1): score=-1 if s[i-1]==t[j-1]: score=1 h[i][j],d[i][j]=maximum(h[i-1][j]+(-2),h[i-1][j-1]+score,h[i][j-1]+(-2)) return h,d
4、接着我们构架回溯的方法对，序列进行回溯：
5、使用循环获得所有比对后的结果。
