找到并回答后如何停止我的回溯算法？

Question

我编写这段代码是为了解决 class 中给我的一个问题，任务是使用回溯解决 "toads and frogs problem"。我的代码解决了这个问题，但一旦达到解决方案就不会停止（它不断打印“状态”，显示其他不是问题解决方案的路径），有没有办法做到这一点？这是代码：

def solution_recursive(frogs):
    #Prints the state of the problem (example: "L L L L _ R R R R" in the starting case
    #when all the "left" frogs are on the left side and all the "right" frogs are on
    #the right side)
    show_frogs(frogs)

    #If the solution is found, return the list of frogs that contains the right order
    if frogs == ["R","R","R","R","E","L","L","L","L"]:
        return(frogs)

    #If the solution isn't the actual state, then start (or continue) recursion
    else:

        #S_prime contains possible solutions to the problem a.k.a. "moves"
        S_prime = possible_movements(frogs)

        #while S_prime contains solutions, do the following
        while len(S_prime) > 0:
            s = S_prime[0]
            S_prime.pop(0)
            #Start again with solution s
            solution_recursive(s)

感谢进步！

Answer 1

How do I stop my backtracking algorithm once I find an answer?

您可以使用 Python exception facilities 来达到这样的目的。

您也可以采用您的 solution_recursive returns 布尔值停止回溯的约定。

这也是品味或意见的问题。

Answer 2

我想扩展一下你的递归代码。

您的问题之一是您的程序显示的路径不是解决方案。这是因为每次调用 solution_recursive 都以

开头

show_frogs(frogs)

不管frogs是不是解

然后，你说程序在找到解决方案后仍在继续。这有两个原因，第一个是你的while循环不关心是否已经找到解决方案，它会遍历所有可能的动作：

while len(S_prime) > 0:

另一个原因是每次调用此函数时您都在重新初始化 S_prime。我真的很惊讶它没有进入无限循环只是一遍又一遍地检查第一步。

由于这是class中的一个问题，我不会给你一个确切的解决方案，但这些问题需要解决，我相信你的教学material可以指导你。

找到并回答后如何停止我的回溯算法？

How do I stop my backtracking algorithm once I find and answer?

python

recursion

backtracking