如何在JavaScript中逐次对比决策树单条路径解决大数据量栈溢出问题

核心优化逻辑 #

• 替换原递归全路径存储方案为迭代DFS遍历，从根节点出发逐节点探索路径，全程仅保留1个当前最优路径变量，不需要存储所有生成的路径
• 每探索到一条完整的终止路径（到达0节点），立刻与当前最优路径对比，保留更符合要求的路径，丢弃当前探索的路径
• 增加节点剪枝逻辑：对同一个节点，若当前到达该节点的路径总和小于已记录的该节点最大总和、且长度也无优势，直接终止该分支的探索，减少无效计算

路径对比规则（可根据需求调整） #

两条路径对比时优先级如下：

1. 长度与目标长度6的差值绝对值越小，优先级越高
2. 差值绝对值相同时，路径元素总和越大，优先级越高

完整实现代码 #

const numbers = [9, 8, 6, 5, 3, 2, 0];
const RANGE = 3; // 实际使用可替换为360
const TARGET_LENGTH = 6;
const starting_node = Math.max(...numbers) + RANGE;

// 辅助函数：计算路径评分，分数越高越优
function getPathScore(path) {
  const lengthDiff = Math.abs(path.length - TARGET_LENGTH);
  const sum = path.reduce((acc, cur) => acc + cur, 0);
  // 长度差权重远大于sum，确保先满足长度要求，再比sum
  return -lengthDiff * 1000000 + sum;
}

// 迭代DFS遍历，逐路径对比
function findBestPath() {
  // 栈结构存储待探索的节点：[当前节点, 当前路径]
  const stack = [[starting_node, []]];
  // 仅存储当前最优路径
  let bestPath = null;
  let bestScore = -Infinity;
  // 剪枝缓存：key为节点值，value为到达该节点的最高评分
  const pruneMemo = {};

  while (stack.length > 0) {
    const [currentNode, currentPath] = stack.pop();

    // 到达终止节点0，开始对比
    if (currentNode === 0) {
      const currentScore = getPathScore(currentPath);
      if (currentScore > bestScore) {
        bestScore = currentScore;
        bestPath = currentPath;
      }
      // 直接丢弃当前路径，不存储
      continue;
    }

    // 剪枝判断：如果当前路径到该节点的评分低于已记录的最高评分，直接终止该分支
    const currentPathScore = getPathScore(currentPath);
    if (pruneMemo[currentNode] && pruneMemo[currentNode] >= currentPathScore) {
      continue;
    }
    pruneMemo[currentNode] = currentPathScore;

    // 长度超过目标值太多也剪枝，可根据需求调整阈值
    if (currentPath.length > TARGET_LENGTH + 2) continue;

    // 找到下一层符合range要求的节点
    const nextNodes = numbers.filter(n => n >= currentNode - RANGE && n < currentNode).reverse();
    for (const nextNode of nextNodes) {
      stack.push([nextNode, [...currentPath, nextNode]]);
    }
  }

  return bestPath;
}

console.log(findBestPath());

性能优化说明 #

• 无全路径存储：全程仅保留当前最优路径和待探索的栈节点，内存占用从O(2^N)降低到O(N)，不会出现内存溢出问题
• 剪枝逻辑避免无效路径探索：同节点只保留最优的前置路径，后续更差的路径直接丢弃，数据量越大剪枝效果越明显
• 迭代遍历避免递归栈溢出：原递归深度过大会触发调用栈上限，迭代实现无该问题

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