如何通过回溯输出迷宫的最快路径？

Question

我正在尝试解决 python 中的回溯问题。我的代码不仅应该能够识别并达到目标，还应该输出到达它的最快路径。迷宫是这样的：

xxxxxxx
xSx   x
x xx  x
x     x
xxxx  x
x     x
x xx xx
x E   x
xxxxxxx 

Start [1,1]
End   [7,2]

到目前为止我写的回溯函数如下所示：

def find_escape(rN, cN, route=[]):
    route.append([rN, cN])
    if is_escape(rN, cN):
        return route
    else:
        escapeRoutes = []
        relCoordinates = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        for relN in relCoordinates:
            absN = [rN + relN[0], cN + relN[1]]
            if is_free(absN[0], absN[1]) and absN not in route:
                temp = find_escape(absN[0], absN[1], route)
                if len(temp) > 0:
                    escapeRoutes.append(temp)
        if len(escapeRoutes) > 0:
            min = escapeRoutes[0]
            for i in escapeRoutes:
                if len(i) < len(min):
                    min = i
            return min
        else:
            return []

我的问题是，输出显示的不是路径，而是他按时间顺序“走过”的每个坐标：

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

辅助功能“is_escape”和“is_free”很简单。所以没问题。

Answer 1

尝试始终递归传递路由副本。这对我行得通。否则，该函数会将算法输入的每个字段添加到原始路由中，并且不属于最佳路由的字段永远不会再次从路由中删除。如果您只通过路线的副本，您永远不会更改原始路线，而只会更改回避通行证的相应副本。每个副本都包含一条独立于其他尝试过的路线的可能路线。然后返回最短路径，不包含其他路径的其他字段。

def find_escape(rN, cN, route=[]):
    route.append([rN, cN])
    if is_escape(rN, cN):
        return route
    else:
        escapeRoutes = []
        relCoordinates = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        for relN in relCoordinates:
            absN = [rN + relN[0], cN + relN[1]]
            if is_free(absN[0], absN[1]) and absN not in route:
                temp = find_escape(absN[0], absN[1], route.copy())
                if len(temp) > 0:
                    escapeRoutes.append(temp)
        if len(escapeRoutes) > 0:
            min = escapeRoutes[0]
            for i in escapeRoutes:
                if len(i) < len(min):
                    min = i
            return min
        else:
            return []

Answer 2

使用像 [] 这样的非原始默认值通常不是一个好主意，因为你会得到奇怪的行为。它不会像您期望的那样在每次执行函数时创建新值，而是 re-use 相同的数组 call-to-call.

试试运行这段代码看看我的意思：

def router(route=[]):
    route.append("a")
    return route

print(router()) # "['a']"
print(router()) # "['a', 'a']"

你可能天真地期望它两次都打印 "['a']"，但第二次打印 "['a', 'a']"，因为数组没有被刷新。

相反，将默认参数设置为 None，并在函数内部检查它是否为 None，如果是，则将其替换为数组：

def router(route=None):
    if route == None:
        route = []
    route.append("a")
    return route

print(router()) # "['a']"
print(router()) # "['a']"

如何通过回溯输出迷宫的最快路径？

How do I output the quickest path of a maze via backtracking?

python

recursive-backtracking