我的递归寻路函数中的哪些算法冗余导致了本质上无限的运行时间？

Question

通常当出现这种问题时，答案是某种无限循环。但是我无法确定在我的代码中可以引入的位置。

假设我们正在处理一个标准的 8x8 棋盘，我想找到从一个方格到另一个方格的最有效路径，比如从红色到绿色。解决方案是3步。

def calculate_dest(curr, path):
    return (curr[0] + path[0], curr[1] + path[1])

def curr_is_valid(curr):
    return 0 <= curr[0] <= 7 and 0 <= curr[1] <= 7

def helper(dest, soFar):
    # if len(soFar) > 4:
    #     return 63
    if not curr_is_valid(soFar[-1]):
        return 63
    elif soFar[-1] in soFar[:-1]:
        return 63
    elif soFar[-1] == dest:
        return len(soFar) - 1
    else:
        return min(helper(dest, soFar + [calculate_dest(soFar[-1], p)]) for p in [(2, 1),
                                                                                  (2, -1),
                                                                                  (-2, 1),
                                                                                  (-2, -1),
                                                                                  (1, 2),
                                                                                  (1, -2),
                                                                                  (-1, -2),
                                                                                  (-1, 2)])

dest：目标点表示为元组（即(0, 1)）

soFar：记录遍历的所有点，表示为元组列表（即[(0, 1), (1, 3)]）

当我运行上面的代码 注释未注释时 , helper((0, 1), [(0, 0)]) returns 3 就像我在 2 中期望的那样秒。不太好，但是当我把评论放回去时，因为该功能应该适用于棋盘上的任意数量的移动，它保持运行ning，基本上永远（我试着等了几分钟，但那时你知道出事了）。

我很确定基本情况 soFar[-1] in soFar[:-1] 应该处理开始重新交叉的路径，这肯定会引入无限循环，所以我不确定为什么函数运行进入无限循环？

也有可能是我设计函数的方式从根本上来说效率低下。我的想法是在这种情况下递归是必要的。

Answer 1

您想做一个 BFS 因为它保证 return 最短路径。

代码如下：

def is_valid(curr):
    return 0 <= curr[0] <= 7 and 0 <= curr[1] <= 7

def get_neighbors(cur):
    for offset in [(2, 1),
                    (2, -1),
                    (-2, 1),
                    (-2, -1),
                    (1, 2),
                    (1, -2),
                    (-1, -2),
                    (-1, 2)]:
        nxt = (cur[0] + offset[0], cur[1] + offset[1])
        if is_valid(nxt):
            yield nxt

def helper(start, dest):
    visited = set()
    q = [(start, 0)]
    while q:
        front, distance = q.pop(0)
        visited.add(front)
        if front == dest:
            return distance
        for neighbor in get_neighbors(front):
            if neighbor not in visited:
                q.append((neighbor, distance + 1))
print(helper((0, 0), (0, 1)))

输出：

我的递归寻路函数中的哪些算法冗余导致了本质上无限的运行时间？

What algorithmic redundancies in my recursive pathfinding function are causing essentially infinite runtime?

python

python-3.x

path-finding