使用BFS的蛇梯

Question

给定一个蛇梯板，我们必须找到最后一个顶点到第0个顶点的最小距离。（在第0个顶点，我们掷骰子并向前移动）

请阅读此处的问题->LINK

我的代码：

from collections import defaultdict

global INT_MAX
INT_MAX = 3 ** 38


class Graph:
    def __init__(self):
        self.vertList = defaultdict(list)

    def addEdge(self, u, v):
        self.vertList[u].append(v)

    def distanceBFS(self, src, target):
        queue = []
        queue.append(src)
        distanceDict = {}
        for v in self.vertList:
            distanceDict[v] = INT_MAX
        distanceDict[src] = 0
        visited = set()

        while (len(queue) > 0):
            curr = queue.pop(0)
            visited.add(curr)

            for vertex in self.vertList[curr]:
                if vertex not in visited:
                    queue.append(vertex)
                    distanceDict[vertex] = distanceDict[curr] + 1

        print(distanceDict[target])

    def solveSnakesLadder(self):
        snakeLadderDict = {2: 13, 5: 2, 9: 18, 18: 11, 17: -13, 20: -14, 24: -8, 25: 10, 32: -2, 34: -22}
        # we have 36 boxes --> i
        # we can throw a dice at each of these 36 boxes and it can be from 1 to 6
        # j is new position on the board after throwing a dice
        for i in range(0, 37):
            for dice in range(1, 7):
                j = i + dice
                if j in snakeLadderDict:
                    j += snakeLadderDict[j]
                if j <= 36:
                    self.addEdge(i, j)
        self.distanceBFS(0, 36)


g = Graph()
g.solveSnakesLadder()

电流输出：

10

正确输出：

4

我做错了什么？这和逻辑有关吗？在添加到队列中之前，我还可以检查distanceDict中的值，但是访问集也会做同样的事情

Answer 1

您的算法中有两个错误。最重要的是：

distanceDict[vertex] = distanceDict[curr] + 1

这可能会用更差的距离覆盖现有距离。所以你应该：

distanceDict[vertex] = min(distanceDict[vertex], distanceDict[curr] + 1)

并且，distanceDict中缺少一个顶点，因为节点36没有传出边。这可能不是一个真正的错误，而是一个遗漏。但是，在图形中为所有节点设置一个条目是合乎逻辑的。因此，您应该处理这个问题，例如通过初始化：

distanceDict[target] = INT_MAX

找到目标后退出循环也是一个好主意，这样可以避免不必要地访问所有其他节点，这永远不会改变结果

最后，不需要跟踪每个节点与源的距离，也不需要使用队列。如果分隔BFS遍历树的每个“级别”，则可以为每个级别使用新列表，并增加单个距离变量以跟踪它

def distanceBFS(self, src, target):
    distance = 0
    visited = set()
    frontier = [src]
    while frontier:
        if target in frontier:
            return distance  # found
        visited.update(frontier)
        frontier = [vertex for curr in frontier for vertex in self.vertList[curr] 
                               if vertex not in visited]
        distance += 1
    return -1  # cannot be reached

请注意，此函数返回距离，因此仍需打印：

print(self.distanceBFS(0, 36))

Answer 2

基本上，问题在于以下代码块：

    queue.append(src)
    distanceDict[src] = 0
    visited = set()
    while (len(queue) > 0):
        curr = queue.pop(0)
        visited.add(curr)

        for vertex in self.vertList[curr]:
            if vertex not in visited:
                queue.append(vertex)
                distanceDict[vertex] = distanceDict[curr] + 1

我将尝试用以下基本图表来解释这一点：

假设，您需要在下图中找到从顶点1到顶点3的最短路径。使用上述实现，您将有以下迭代：

1. 将顶点1添加到队列Q，并将其距离设置为0
2. 接下来，在while循环中从Q弹出1，并将其标记为已访问
3. 接下来，访问它的所有邻居并将它们添加到队列Q

因此，此时，不同对象的状态如下所示：

我们在队列Q中有顶点2和3，而distance字典将作为distance[1] = 0, distance[2] = 1, distance[3] = 1，这就是问题的开始，因为我们还没有将顶点2和3添加到visited如果我们从其他邻居处再次访问这些顶点，我们将在下一次迭代中再次开始更新这些顶点的距离

1. 再次回到我们的算法，现在我们再次转到while循环的开始，从它开始pop顶点2，并将其标记为已访问
2. 当我们下一步通过其未访问的邻居时，我们将再次访问我们已经访问过的3，并将使用不正确的值更新distance字典

访问vertex2及其相邻对象后，不同对象的状态如下：

我们在队列中有顶点3，距离字典将为distance[1] = 0, distance[2] = 1, distance[3] = 2distance[3]被错误地更新了，正如我们在迭代中看到的那样

然而，修复是非常直接的，在这里，我们需要在访问顶点之后将其标记为已访问，这样我们就不会通过其他邻居将其再次放入队列中

到目前为止，您已经猜到BFS函数的正确实现应该如下所示：

from collections import defaultdict

global INT_MAX
INT_MAX = 3 ** 38


class Graph:
    def __init__(self):
        self.vertList = defaultdict(list)

    def addEdge(self, u, v):
        self.vertList[u].append(v)

    def distanceBFS(self, src, target):
        queue = []
        queue.append(src)
        distanceDict = {}
        for v in self.vertList:
            distanceDict[v] = INT_MAX
        distanceDict[src] = 0
        visited = set()
        visited.add(src)
        while (len(queue) > 0):
            curr = queue.pop(0)

            for vertex in self.vertList[curr]:
                if vertex not in visited:
                    queue.append(vertex)
                    visited.add(vertex)
                    distanceDict[vertex] = distanceDict[curr] + 1

        print(distanceDict[target])



    def solveSnakesLadder(self):
        snakeLadderDict = {2: 13, 5: 2, 9: 18, 18: 11, 17: -13, 20: -14, 24: -8, 25: 10, 32: -2, 34: -22}
        # we have 36 boxes  > i
        # we can throw a dice at each of these 36 boxes and it can be from 1 to 6
        # j is new position on the board after throwing a dice
        for i in range(0, 37):
            for dice in range(1, 7):
                j = i + dice
                if j in snakeLadderDict:
                    j += snakeLadderDict[j]
                if j <= 36:
                    self.addEdge(i, j)
        self.distanceBFS(0, 36)


g = Graph()
g.solveSnakesLadder()