Python递归实现LCSS函数运行异常问题求助

首先给你明确一下：**LCSS（Longest Common Subsequence for Trajectories）**在这里是针对地理轨迹的最长公共子序列算法，用来找出两条轨迹中满足「空间距离小于阈值（你的代码里是500米）」且「子序列长度差小于阈值（5个点）」的最长匹配子序列，返回的长度N自然会小于等于两条轨迹长度的最大值max(len(A), len(B))。

接下来看你的代码为什么会一直运行不返回结果，以及存在的核心问题：

代码里的关键错误 #

• 拼写失误：在LCSS函数里调用距离计算时，把Distance写成了Disance，这会直接触发NameError；如果你的运行版本里这个错误被修正了，那还有更严重的问题
• 递归参数缺失：return LCSS()+1完全没传A、B参数，正确写法应该是return LCSS(A[:-1], B[:-1]) + 1——匹配当前最后一个点后，要递归处理两条轨迹去掉最后一个点的子序列
• 无记忆化的暴力递归：原代码的递归方式会重复计算大量相同的子问题，比如LCSS(A[:-1], B)和LCSS(A, B[:-1])会反复调用重叠的子序列，只要轨迹点数量稍多，就会导致计算量爆炸，程序陷入极长时间的运行（看起来像无限循环）

修复后的完整代码 #

我修正了所有语法和逻辑错误，还加上了记忆化缓存来避免重复计算，大幅提升运行效率：

import math
from functools import lru_cache

def Distance(P1, P2, R=6378137):
    # 提取经纬度：假设P1格式为[纬度, 经度]
    lat1, lon1 = P1[0], P1[1]
    lat2, lon2 = P2[0], P2[1]
    # 球面距离计算（保留原公式，格式化后更易读）
    dist = R * math.acos(
        1 - (
            math.pow(math.sin((90 - lat1)*math.pi/180)*math.cos(lon1*math.pi/180) - math.sin((90 - lat2)*math.pi/180)*math.cos(lon2*math.pi/180), 2)
            + math.pow(math.sin((90 - lat1)*math.pi/180)*math.sin(lon1*math.pi/180) - math.sin((90 - lat2)*math.pi/180)*math.sin(lon2*math.pi/180), 2)
            + math.pow(math.cos((90 - lat1)*math.pi/180) - math.cos((90 - lat2)*math.pi/180), 2)
        ) / 2
    )
    return round(dist, 2)

# 用lru_cache做记忆化，需将轨迹转为tuple才能被缓存
@lru_cache(maxsize=None)
def LCSS(A, B, e=500, f=5):
    # 边界条件：任意一条轨迹为空时返回0
    if len(A) == 0 or len(B) == 0:
        return 0
    # 检查最后一个点的距离是否达标，且当前子序列长度差符合要求
    if Distance(A[-1], B[-1]) < e and abs(len(A) - len(B)) < f:
        # 匹配成功，递归处理去掉最后一个点的子序列，结果加1
        return LCSS(A[:-1], B[:-1], e, f) + 1
    else:
        # 不匹配时，取两种情况的最大值：去掉A的最后一个点，或去掉B的最后一个点
        return max(LCSS(A[:-1], B, e, f), LCSS(A, B[:-1], e, f))

# 示例调用（需将轨迹列表转为tuple）
# trajectory_A = [(39.9042, 116.4074), (39.915, 116.403)]
# trajectory_B = [(39.9043, 116.4075), (39.9149, 116.4031)]
# print(LCSS(tuple(trajectory_A), tuple(trajectory_B)))

额外说明 #

1. 因为lru_cache只支持缓存可哈希的参数，所以调用时需要把轨迹列表转换成tuple（比如LCSS(tuple(A), tuple(B))）
2. 原代码里的abs(len(A)-len(B))<f是判断当前子序列的长度差，如果你的需求是判断原始轨迹的长度差，那这个条件应该放在函数外部提前判断
3. 修复后的代码会快速返回结果，且返回的N一定是小于等于max(len(A), len(B))的整数，完全符合你的需求

内容的提问来源于stack exchange，提问作者ChiWai Choi