使用DFS实现骑士最短路径时陷入无限递归循环求助

背景 #

尝试用**DFS（深度优先搜索）实现国际象棋骑士的最短路径算法，虽然知道BFS（广度优先搜索）**更高效，但希望通过DFS实现加深对两种算法的理解。

问题 #

nextMove(curRow, curCol, moves)函数出现栈溢出。基础逻辑能正常触发（初始栈可返回），但遍历到后期会陷入带着相同数组值的无限循环，最终导致栈溢出。

预期目标 #

递归函数在无更多可探索场景时能正常退出，且能找到最短路径。

已尝试操作 #

在递归返回时对路径数组执行pop操作，试图避免重复使用相同数组值。

代码实现 #

function knightMoves(start, finish) {

  let shortestPath = []
  
    function nextMove(curRow, curCol, moves) {
        //console.log(moves)
            if (curRow === finish[0] && curCol === finish[1]) {
            if (shortestPath.length === 0) {
                shortestPath = moves
            }
            else {  
                shortestPath = moves.length < shortestPath.length ? moves : shortestPath
            }

            console.log(shortestPath)
        
            return
        }
    
        // 骑士可移动的8个方向
        let options = [[1,2], [1,-2], [-1,2], [-1,-2], [2,1], [2,-1], [-2,1], [-2,-1]]
        for (let i=0; i<options.length; i++) {
            let moveRow = options[i][0]
            let moveCol = options[i][1]

            let newRow = curRow + moveRow
            let newCol = curCol + moveCol
            
            let proceed = validMove(newRow, newCol, moves)
            
            if (proceed) {
                let arr = [...moves]
                arr.push([newRow, newCol])
                nextMove(newRow, newCol, arr)
                arr.pop()
            }
        }    
        return 
    }   

    nextMove(start[0], start[1], [start])
    return shortestPath
}

function validMove(row, col, moves) {
    // 检查坐标是否已访问
  let coordinate = [row, col]
    let newSpot = true
    if (moves.length > 0) {
    for (let i = 0; i <moves.length; i++) {
      let seen = moves[i].length === coordinate.length && moves[i].every((value, index) => value === coordinate[index])
      if (seen) {
        return false
      }
    }
  }
  else {
    newSpot = true
  }
  
  // 检查是否在棋盘范围内
  if (newSpot) {
    if ((row >= 0 && row < 8) && (col >= 0 && col < 8)) {
      return true
    }
    else {
      //debugger;
      return false
    }
  }
}

// console.log(knightMoves([0,0],[3,3]))

问题根源与修复方案 #

核心问题 #

1. 无效的arr.pop()操作：代码中通过let arr = [...moves]创建了当前路径的独立副本，递归调用nextMove后对副本执行pop完全多余——副本是局部变量，不会影响其他递归分支的路径，这个操作无法解决重复访问问题，属于无意义代码。
2. 无剪枝的深度遍历：DFS会优先探索一条路径到尽头，而棋盘有64个格子，当路径过长时，递归深度会超过JavaScript调用栈的限制，直接触发栈溢出。更关键的是，即使找到最短路径后，DFS仍会继续遍历所有更长的路径，完全没有终止无效分支的逻辑，导致资源浪费和无限递归风险。

修复步骤 #

1. 移除无效的arr.pop()

直接删除arr.pop()即可，因为路径副本是独立的，递归调用后不需要修改它。

2. 添加剪枝逻辑

当当前路径长度已经大于等于已找到的最短路径长度时，直接终止当前分支——继续遍历不可能得到更短的路径，没必要浪费资源。修改nextMove函数：

function nextMove(curRow, curCol, moves) {
    // 剪枝：当前路径已不短于已知最短路径，直接返回
    if (shortestPath.length > 0 && moves.length >= shortestPath.length) {
        return;
    }

    if (curRow === finish[0] && curCol === finish[1]) {
        if (shortestPath.length === 0) {
            shortestPath = moves;
        } else {  
            shortestPath = moves.length < shortestPath.length ? moves : shortestPath;
        }
        console.log(shortestPath);
        return;
    }

    let options = [[1,2], [1,-2], [-1,2], [-1,-2], [2,1], [2,-1], [-2,1], [-2,-1]];
    for (let i=0; i<options.length; i++) {
        let moveRow = options[i][0];
        let moveCol = options[i][1];

        let newRow = curRow + moveRow;
        let newCol = curCol + moveCol;
        
        let proceed = validMove(newRow, newCol, moves);
        
        if (proceed) {
            let arr = [...moves];
            arr.push([newRow, newCol]);
            nextMove(newRow, newCol, arr);
        }
    }    
    return;
}

3. 优化validMove效率

当前检查已访问坐标的方式是遍历整个路径数组，效率较低。可以改用字符串化坐标的方式简化检查：

// 优化后的validMove
function validMove(row, col, moves) {
    // 先检查边界，快速排除无效坐标
    if (row < 0 || row >= 8 || col < 0 || col >= 8) {
        return false;
    }
    // 检查是否已访问
    const target = `${row},${col}`;
    return !moves.some(([r, c]) => `${r},${c}` === target);
}

修复效果 #

添加剪枝逻辑后，一旦找到最短路径，后续所有长度不小于该路径的分支都会被直接终止，大幅减少递归深度和遍历次数，既避免了栈溢出，又提升了运行效率。

内容的提问来源于stack exchange，提问作者Mschreider