为什么我的回溯算法不能解决这个简单的问题？

Question

您好，我目前正在尝试解决以下问题：

假设您有一个随机排队的人名单。每个人都用一对整数(h, k)描述，其中h是人的身高，k是在这个人面前的身高大于或等于h的人数。编写算法以重建队列。

注意：人数不到1,100。

示例

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

这是我目前所能提供的解决方案：

answer = []
def reconstructQueue(people):
    if len(answer) == len(people) and is_valid(answer):
        return True

    for person in people:
        answer.append(person)
        if is_valid(answer):
            reconstructQueue([x for x in people if x != person])
        else:
            answer.pop()




def is_valid(answer):
    answer = answer[::-1]
    for i in range(len(answer)):
        count = 0
        for j in answer[i+1:]:
            if answer[i][0] <= j[0]:
                count+=1
        if count != answer[i][1]:
            return False
    return True

我的is_valid函数正在运行，但在recontructQueue中实现的回溯出错了！

我认为这应该起作用：

• 检查是否有一个包含所有原始列表值的有效答案，如果是，则完成。
• 如果不是，则将其他人添加到列表answer，然后查看是否有效。
• 如果有效，则递归调用该函数以删除我们刚刚添加的元素。
• 如果无效，则我们犯了一个错误，因此我们通过从答案中弹出该元素来回溯。

虽然它没有给我正确的答案。

[有人可以帮我解释我要去哪里了，回溯后我很糟糕！

谢谢。

Answer 1

将全局answer作为递归内部工作的一部分并不是一个好主意。我们将其替换为默认的第二个参数。

正如@MattTimmermans指出的那样，您使递归初学者犯了一个错误：让递归函数返回有用的结果，但是在递归调用时忽略该结果。该递归调用将导致成功或失败，因此您需要采取相应的行动：

def reconstructQueue(people, todo=None):
    if not todo and is_valid(people):
            return people

    if todo is None:
        todo = people
        people = []

    tossed = []

    while todo:
        people.append(todo.pop())

        if is_valid(people):
            result = reconstructQueue(people, todo + tossed)

            if result:
                return result

        tossed.append(people.pop())

    return None  # there is no solution from this starting point

def is_valid(answer):
    for index, (my_height, my_count) in enumerate(answer):
        their_count = sum(my_height <= their_height for their_height, _ in answer[:index])

        if their_count != my_count:
            return False

    return True

scrambled = [(7, 0), (4, 4), (7, 1), (5, 0), (6, 1), (5, 2)]

print(reconstructQueue(scrambled))

我还将您的数据结构从列表列表切换为元组列表，因为这对我来说在Python方面更有意义。

输出

> python3 test.py
[(5, 0), (7, 0), (5, 2), (6, 1), (4, 4), (7, 1)]
>