Knight walk回溯解决问题

Question

我对我为以下问题编写的回溯解决方案有疑问：

Given a square chessboard of N x N size, the position of Knight and the position of a target are given. We need to find out the minimum steps a Knight will take to reach the target position

我的回溯解决方案是：

    #knight walk problem
 #knight walk problem
#cx---crnt x value
#cy---crnt y value
#Dx---destintion X value
#Dy----destintion Y value
#count---count of steps


def kingnight(Cx,Cy,Dx,Dy,outboard,steps):
  if Cx==Dx and Cy==Dy:
    outboard[Cx][Cy]=1
    return steps
  if Cx<0 or Cy<0 or Cx>=len(outboard) or Cy>=len(outboard) or outboard[Cx][Cy]==1:
    return float('inf')
  outboard[Cx][Cy]=1
  min1=kingnight(Cx+2,Cy-1,Dx,Dy,outboard,steps+1)
  min2=kingnight(Cx+2,Cy+1,Dx,Dy,outboard,steps+1)
  min3=kingnight(Cx-2,Cy+1,Dx,Dy,outboard,steps+1)
  min4=kingnight(Cx-2,Cy-1,Dx,Dy,outboard,steps+1)
  min5=kingnight(Cx+1,Cy+2,Dx,Dy,outboard,steps+1)
  min6=kingnight(Cx+1,Cy-2,Dx,Dy,outboard,steps+1)
  min7=kingnight(Cx-1,Cy+2,Dx,Dy,outboard,steps+1)
  min8=kingnight(Cx-1,Cy-2,Dx,Dy,outboard,steps+1)
  crntmin=min(min1,min2,min3,min4,min5,min6,min7,min8)
  outboard[Cx][Cy]=0 #backtracking
  return crntmin

当我调用函数时：

n=4
board=[[0 for _ in range(n)] for i in range(n)]
kingnight(1,1,0,0,board,0)

它显示了预期的输出。但是当我用下面的电话打电话时：

n=6
board=[[0 for _ in range(n)] for i in range(n)]
kingnight(2,3,5,5,board,0)

它应该 return 3 但它是一个无限循环。

我哪里错了？

Answer 1

问题是您的算法正在寻找马从起始位置可以走的每条可能路径。在更大的电路板上，路径数量呈指数增长。你的循环不是无限的；它只是需要检查太多路径。

如果我们稍微简化一下，假设马在 6x6 棋盘上平均可以走 4 步，路径平均长 20 步，那么我们有 4²⁰ 路径，即 1e+12 路径。这是一个低估。

如何解决

这个暴力算法不够好

使用广度优先搜索而不是深度优先搜索，并在每个访问过的图板单元格上记录与源（也用作访问标记）的（最短）距离。未访问的字段应初始化为 -1。源将得到 0，...等等

这将是您需要的主要改进。您还可以应用一些启发式方法，并将其转化为 A* 算法，其中估计到目标的步数应该被低估，例如出租车距离除以 3。

实施

我选择了一种实现方式，其中您不将棋盘传递给函数，而只是 n，而函数 returns 是一条坐标路径。

然后该函数将在本地创建它的棋盘，并在广度优先期间用代表骑士在其最佳路径（到那个方块）上的位置的值填充它。

代码如下：

def kingnight(cx,cy,dx,dy,n):
    board=[[0 for _ in range(n)] for i in range(n)]
    q = [(cx, cy)]
    board[cx][cy] = (-1, -1)
    while q:
        frontier = []
        for cx, cy in q:
            for mx, my in ((-2,-1),(-1,-2),(1,-2),(2,-1),(1,2),(2,1),(-2,1),(-1,2)):
                tx = cx + mx
                ty = cy + my
                if 0 <= tx < n and 0 <= ty < n and not board[tx][ty]:
                    board[tx][ty] = (cx, cy)
                    if tx == dx and ty == dy:
                        # build path
                        path = []
                        while tx >= 0:
                            path.append((tx, ty))
                            tx, ty = board[tx][ty]
                        return path[::-1]
                    frontier.append((tx, ty))
        q = frontier
    return  # Not possible

# Demo
n=6
print(kingnight(2,3,5,5,n))

Knight walk回溯解决问题

Knight walk backtracking solution issue

python

algorithm

recursion

backtracking

recursive-backtracking

如何解决

实施