递归顶点搜索生成器中lru_cache的有效性验证及优化咨询

首先直接给你答案：你的lru_cache目前确实在正常工作，但当前实现有不少可以优化的效率点，下面给你拆解细节和改进建议：

一、为什么现在缓存能生效？ #

你做了两个关键的正确操作：

1. 所有传入函数的参数都是可哈希的tuple类型，满足lru_cache对参数的哈希要求，装饰器能正常生成缓存键。
2. 你在把新的移除节点传入递归时，对new_removed_nodes做了排序再转成tuple——这一步非常重要！它能让不同移除顺序的同一组节点（比如先删2再删3，和先删3再删2）变成完全相同的缓存键，lru_cache就能识别出这是同一个计算场景，直接返回之前缓存的结果，避免了重复计算。

如果想直观验证缓存是否生效，可以在函数开头加一行打印：

print(f"Processing removed_nodes: {removed_nodes}")

运行后你会发现，像(2,3)这样的组合只会被打印一次，而不是两次，这就证明缓存命中了。

二、当前实现的效率痛点 #

虽然缓存起作用了，但你的代码有不少重复的冗余操作，会拖慢整体速度：

1. 每次调用都重复构建图：每次进入函数都要把t_matrix转成numpy数组，再重建NetworkX图，还要手动移除removed_nodes里的节点——这部分操作在缓存命中的时候其实可以完全跳过，而你现在哪怕缓存命中，只要进入函数就会先执行这些步骤（直到缓存返回结果）。
2. 递归中频繁复制图：每次尝试移除新节点时，都要G.copy()再删节点，对于大图来说这是很大的内存和时间开销。
3. 生成器处理冗余：你把递归返回的生成器转成list再循环yield，这会把整个生成器的结果一次性加载到内存里，浪费内存，也没必要。

三、针对性优化建议 #

1. 提前构建原始图，避免重复重建 #

不要在递归函数里每次从矩阵重建图，而是在函数外提前构建好原始图，然后换个思路：直接基于原始图，通过移除节点集合来判断连通性，而不是每次修改图。

示例代码：

from functools import lru_cache
import networkx as nx
import numpy as np
from itertools import combinations

# 提前在函数外构建原始图，避免重复操作
original_mat = np.array([
    [0,0,1,0,1,],
    [0,0,0,1,1,],
    [1,0,0,1,0,],
    [0,1,1,0,0,],
    [1,1,0,0,0,],
])
original_G = nx.from_numpy_array(original_mat)
must_retain = (0,1)

@lru_cache(maxsize=None)
def iter_node_optimized(
    must_retain_nodes: tuple,
    removed_nodes: tuple,
):
    # 直接基于原始图生成当前剩余节点的子图
    retained_nodes = [n for n in original_G.nodes if n not in removed_nodes]
    current_G = original_G.subgraph(retained_nodes)
    
    for node in retained_nodes:
        if node not in must_retain_nodes:
            # 排序确保相同节点组合的缓存键一致
            new_removed = sorted([*removed_nodes, node])
            new_removed_tuple = tuple(new_removed)
            # 生成移除当前节点后的子图，判断连通性
            temp_retained = [n for n in retained_nodes if n != node]
            temp_G = original_G.subgraph(temp_retained)
            if all(nx.has_path(temp_G, *pair) for pair in combinations(must_retain_nodes, 2)):
                # 用yield from直接传递递归结果，无需转list
                yield from iter_node_optimized(must_retain_nodes, new_removed_tuple)
                yield new_removed

# 调用优化后的函数
solutions = list(iter_node_optimized(must_retain, ()))
print(solutions)

2. 优化生成器递归逻辑 #

把原来的：

temp_sol = list(iter_node_2(...))
for sol in temp_sol:
    yield sol

改成yield from iter_node_2(...)，这样可以直接把递归生成器的结果传递出去，不需要把所有结果先存到list里，既节省内存又提升效率。

3. 可选：预计算连通性判断对 #

如果must_retain_nodes的数量固定，可以提前计算所有需要判断的节点对（即combinations(must_retain_nodes,2)的结果），转成tuple作为参数传入函数，避免每次在递归中重复计算组合。

最后总结 #

你的缓存策略是正确的，排序移除节点的操作确实让lru_cache能有效命中相同的节点组合；但通过提前构建原始图、优化图操作和生成器逻辑，能让代码的运行效率提升很多，尤其是在处理大图的时候。

备注：内容来源于stack exchange，提问作者avringo