python - 最短路线优化不起作用

Question

我试图用 Python 解决 Ruby Quiz 问题 60，这里给出: http://rubyquiz.com/quiz60.html

人们基本上必须通过将一个数字加倍、减半或加 2 来找到从一个数字到另一个数字的最短路径。

编写一个程序来实际解决这个问题并不太难:

def maze_solver(a, b):
    paths = [[a]]
    final = []

    for ind, path in enumerate(paths):

        if path[-1] == b:
            return path

        last = path[-1]

        paths.append(path + [last * 2])
        paths.append(path + [last + 2])
        if last % 2 == 0:
            paths.append(path + [last / 2])


print maze_solver(979, 2)


>>> maze_solver(9, 2)
[9, 18, 20, 10, 12, 6, 8, 4, 2]
>>> maze_solver(2, 9)
[2, 4, 8, 16, 18, 9]

但是当我尝试优化它时，却失败了。我想如果两条路径有相同的终点并且一条路径比另一条路径短，那么可以消除较长的路径。

我试过这个优化:

def maze_solver(a, b):
    paths = [[a]]
    final = []

    for ind, path in enumerate(paths):

        if path[-1] == b:
            return path

        for other in paths:
            if ind != paths.index(other):
                if path[-1] == other[-1] and len(other) >= len(path):
                    paths.remove(other)

        last = path[-1]

        paths.append(path + [last * 2])
        paths.append(path + [last + 2])
        if last % 2 == 0:
            paths.append(path + [last / 2])

但这甚至没有产生正确的答案:

>>> maze_solver(9, 2)
[9, 11, 22, 24, 48, 24, 12, 6, 8, 4, 2]

我不知道为什么这段代码不起作用，所以如果有人能向我解释我做错了什么，那将非常有帮助，谢谢!

Answer 1

在遍历列表时修改列表可能很危险。

参见 this answer