时间戳

首页 > 解决方案 > 计算网格中从左上到右下的路径数

python-3.x - 计算网格中从左上到右下的路径数

问题描述

我需要计算从左上角到右下角的路径数，其中有效路径是穿过网格中所有正方形的路径（每个正方形恰好一次）

我正在使用回溯技术。不幸的是，count是0在计算结束。打印t，我看到它永远不会到达n-1。

我的算法有什么问题？

n = 4
count = 0
m = [[False for x in range(n)] for y in range(n)] 

def num_of_paths(m, x, y, t):

    print(t)

    global count

    # check if we reached target
    if x == (n - 1) and y == (n - 1):
        if t < (n * n):
            # not on time, prune the tree here
            return 
        elif t == n * n:
            # completed a full path in the grid and on time
            count += 1 

    if t > n * n:
        return

    # Right
    if x + 1 < n and m[x + 1][y] == False:
        m[x + 1][y] = True
        num_of_paths(m, x + 1, y, t + 1)
        m[x + 1][y] = False

    # Left
    if x - 1 > 0 and m[x - 1][y] == False:
        m[x - 1][y] = True
        num_of_paths(m, x - 1, y, t + 1)
        m[x - 1][y] = False

    # Down
    if y + 1 < n and m[x][y + 1] == False:
        m[x][y + 1] = True
        num_of_paths(m, x, y + 1, t + 1)
        m[x][y + 1] = False

    # Up
    if y - 1 > 0 and m[x][y - 1] == False:
        m[x][y - 1] = True
        num_of_paths(m, x, y - 1, t + 1)
        m[x][y - 1] = False


num_of_paths(m, 0, 0, 0)
print(count)

标签： python-3.xalgorithmrecursionbacktrackingpruning

解决方案

有以下问题：

  • 起始单元格没有标记m[0][0] = True，因此向右走后，算法将再次向左走，实际上访问了两次该单元格。要解决此问题，您可以将用于管理m值的代码从您现在拥有的位置移开（4 次）并将其应用到当前单元格（一次）。这包括检查以及和if m[..][..]的分配。TrueFalse
  • if与左和上方向相关的条件应将坐标与 进行比较>= 0，而不是与> 0：坐标的零值仍在范围内。
  • t应该从 1 开始，因为您将其值与n * n. 否则你应该与n * n - 1. 在下面的更正中，我将从t = 1.
  • 不是一个真正的问题，但是在这样做之后count += 1立即有意义return，因为不再有可能进一步扩展路径。

其他一些评论：

  • 当n为偶数时，没有有效路径，因此即使更正，该函数在这种情况下也必然返回 0
  • 这个算法访问的路径数量是指数的，O(2 n² )。对于n > 6，不要等待它......

这是您的代码的更正版本。评论应阐明更改的内容和原因：

n = 5
count = 0
m = [[False for x in range(n)] for y in range(n)] 

def num_of_paths(m, x, y, t):
    global count
    # Moved the "visited" check to here. No need to add `== True`.
    if m[x][y]: 
        return
    if x == (n - 1) and y == (n - 1):
        if t < (n * n):
            return 
        else: # Removed the unnecessary condition here
            count += 1 
            # Added a return here
            return
    # Removed an if-block of which the condition could never be true
    # Moved the "visited" marking to here:
    m[x][y] = True
    if x + 1 < n:
        num_of_paths(m, x + 1, y, t + 1)
    # Corrected "> 0" to ">= 0"
    if x - 1 >= 0:
        num_of_paths(m, x - 1, y, t + 1)
    if y + 1 < n:
        num_of_paths(m, x, y + 1, t + 1)
    # Corrected "> 0" to ">= 0"
    if y - 1 >= 0:
        num_of_paths(m, x, y - 1, t + 1)
    # Moved the "visited" unmarking to here:
    m[x][y] = False

# Corrected the last argument
num_of_paths(m, 0, 0, 1)
print(count)

推荐阅读