计算网格中从左上到右下的路径数

Question

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

我正在使用回溯技术。不幸的是，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)

Answer 1

存在以下问题：

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

一些其他备注：

当n为偶数时，没有有效路径，所以即使更正后，函数也绑定到return 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)

Answer 2

此代码有效

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

def num_of_paths(m,x,y):


    # setting (x,y) position in m = True as we have crossed this square now


    m[y][x]=True
    global count
    # check if we reached target

    if x == (n - 1) and y == (n - 1):

        # check if we haven't missed any square

        for i in m:   
            if False in i:
                m[y][x]=False
                return 

        # increment count if we visited all squares

        count+=1    
        m[y][x]=False
        return 


     # setting up legel directions in which current point(x,y) should head next
    dir={'up','down','left','right'}
    if x==0:
        dir-={'left'}
    if x==n-1:
        dir-={'right'}
    if y==0:
        dir-={'up'}
    if y==n-1:
        dir-={'down'}
    # now we have all legal directions that (x,y) could go to

    # now iterate over all possible directions of (x,y)
    for i in dir:
        if i=='left':      # left means (x,y) will change to (x-1,y) i.e. change is (-1,0)
            if m[y][x-1]==False:   # it means left of (x,y) havent yet crossed i.e. it is legel to visit now
                num_of_paths(m,x-1,y)
    # similiarly for other possible directions

        if i=='right':
            if m[y][x+1]==False:
                num_of_paths(m,x+1,y)

        if i=='up':
            if m[y-1][x]==False:
                num_of_paths(m,x,y-1)

        if i=='down':
            if m[y+1][x]==False:
                num_of_paths(m,x,y+1)


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

如果有问题请告诉我

计算网格中从左上到右下的路径数

Calculate the number of paths in a grid from top left to bottom right

python-3.x

algorithm

recursion

backtracking

pruning