Dynamic Time Warping（动态时间序列扭曲匹配，简称DTW）是时间序列分析的经典算法，用来比较两条时间序列之间的距离，发现最短路径。以下为两种不同实现方式的代码示例： #### 第一种：使用`dtw_distance`函数 ```python import numpy as np def dtw_distance(ts_a, ts_b, d=lambda x,y: abs(x-y), mww=10000): """ Computes dtw distance between two time series Args: ts_a: time series a ts_b: time series b d: distance function mww: max warping window, int, optional (default = infinity) Returns: dtw distance """ # Create cost matrix via broadcasting with large int ts_a, ts_b = np.array(ts_a), np.array(ts_b) M, N = len(ts_a), len(ts_b) cost = np.ones((M, N)) # Initialize the first row and column cost[0, 0] = d(ts_a[0], ts_b[0]) for i in range(1, M): cost[i, 0] = cost[i-1, 0] + d(ts_a[i], ts_b[0]) for j in range(1, N): cost[0, j] = cost[0, j-1] + d(ts_a[0], ts_b[j]) # Populate rest of cost matrix within window for i in range(1, M): for j in range(max(1, i - mww), min(N, i + mww)): choices = cost[i-1, j-1], cost[i, j-1], cost[i-1, j] cost[i, j] = min(choices) + d(ts_a[i], ts_b[j]) # Return DTW distance given window return cost[-1, -1] ``` #### 第二种：使用递归方式 ```python import random import math import numpy x=[0]*1000 y=[0]*1000 n=eval(input()) m=eval(input()) con=0# con记录路径长度 for i in range(n): x[i]=random.randint(0,100) for i in range(m): y[i]=random.randint(0,100)#生成x,y对比序列 D=numpy.zeros((m,n))# 构造距离矩阵 def DTW(i,j,con):#进行规划 if(i==0): for k in range(j): con+=D[0][k] return con if(j==0): for k in range(i): con+=D[k][0] return con con+=min(DTW(i-1,j,con)+D[i][j],DTW(i,j-1,con)+D[i][j],DTW(i-1,j-1,con)+2*D[i][j]) return con for i in range(m):#对距离矩阵赋值 for j in range(n): D[i][j]=math.sqrt(x[i]**2+y[j]**2) print("最短距离是",DTW(m-1,n-1,0)) ```