时间戳

首页 > 解决方案 > 如何使递归解决方案返回所有可能的解决方案？

python - 如何使递归解决方案返回所有可能的解决方案？

问题描述

对于这个递归函数，当你输入一个如 的列表时[2,8,3,2,7,2,2,3,2,1,3,0]，它会找到从第一个索引到包含值 0 的索引的路径，但只能在列表中移动index[i]+iorindex[i]-i并且不能越过列表的边界或 go到已经访问过的索引。

所以，如果你在index[0]which 等于 2，你只能在列表中向前移动 2。或者，如果你在index[3]，你只能在列表中向前或向后移动 2；所以你可以去index[1]或index[5]。

对于 list [2,8,3,2,7,2,2,3,2,1,3,0]，我得到了一个解决方案[0,2,5,7,4,11]，但是还有更多的解决方案，例如[0,2,5,3,1,9,10,7,4,11]，我不知道如何让我的函数继续搜索所有其他的。

标签： pythonrecursion

解决方案

携带包含所有解决方案的第二个列表（列表），例如

def findAllPaths(vector, position, solution, all_solutions):
    if position not in solution and position >= 0 and position < len(vector):
        solution = solution + [position] 
        if vector[position] == 0:
            all_solutions.append(solution)
        else:
            stepsize = vector[position]
            findAllPaths(vector, position + stepsize, solution, all_solutions) #step forward
            findAllPaths(vector, position - stepsize, solution, all_solutions) #step back
    return all_solutions

def findPaths(vector):
    paths = findAllPaths(vector, 0, [], [])
    if paths:
        return paths
    else:
        print("No possible path")
        return 0

编辑：

每个递归调用都会产生一个新的堆栈帧，它是一个内存块，包含函数参数和在该调用期间创建的任何局部变量。每个调用依次进行两个递归调用，每个调用都有自己的堆栈帧位于前一个调用的顶部。这个非常宽的堆栈框架塔称为调用堆栈，它跟踪递归函数的执行。最终，我们要么超出界限，要么在向量中达到零，此时我们返回我们的解决方案。正如您正确指出的那样，position在这个堆栈帧中是 11。当我们命中 return 语句时，返回值被传递给堆栈中的前一帧，而当前堆栈帧中的其他所有内容都被丢弃。这样，每个堆栈帧，因此每个递归调用，都维护一个不同的值，position这不会影响position调用它的函数中的值。

那么我们如何确保我们没有重复的解决方案呢？在每次递归调用后考虑候选解决方案。对长度为nfindAllPaths的候选解的调用要么终止（如果），要么对 findAllPaths 进行两次递归调用，每个解的长度为n + 1。在这种情况下，两个各自候选解的最后一个元素是或。这些是相同的 iff ，在这种情况下我们已经终止了。因此，我们递归调用中的两个候选解决方案是不同的，并且候选解决方案的长度随着每次递归调用而增加。结合起来，这两个事实意味着我们永远不可能在解决方案中拥有相同的路径。vector[position] == 0position + vector[position]position - vector[position]vector[position] == 0]

推荐阅读