离散Fréchet距离计算JS代码while循环出现死循环问题求助

核心错误点 #

• 二维数组访问语法错误：JS中二维数组取值应为arr[i][j]，你代码中大量使用S[i-1, j]这类写法，逗号运算符会忽略前一个值，实际取到的是S[j]，导致所有计算值异常
• 动态规划数组初始化错误：你初始化S和backpointers时只写了固定两行，当输入序列长度大于2时会出现数组越界，值为undefined
• 动态规划转移逻辑错误：三个转移选项全部错误取了S[i-1][j]，实际应该分别对应S[i-1][j]/S[i][j-1]/S[i-1][j-1]，导致backpointers存储的回溯方向完全错误
• Math.min用法错误：Math.min不能直接接收数组作为参数，需要用扩展运算符Math.min(...options)，否则返回NaN，导致回溯方向索引无效
• while循环终止条件完全错误：你当前的终止条件逻辑混乱永远无法满足，回溯只需要判断当前i和j是否都回到0即可
• 回溯偏移量取值逻辑错误：backpaths的取值、偏移量赋值的语法都存在错误，导致i和j无法正常递减，出现死循环

修复后完整代码 #

// 欧氏距离计算函数，如已实现可删除重复定义
function euclidian(X, Y, i, j) {
  const dx = X[i][0] - Y[j][0];
  const dy = X[i][1] - Y[j][1];
  return Math.sqrt(dx*dx + dy*dy);
}

function discreteFrechet(X, Y) {
  const M = X.length;
  const N = Y.length;
  // 正确初始化二维动态规划数组和回溯指针数组
  const S = Array.from({length: M}, () => new Array(N).fill(0));
  const backpointers = Array.from({length: M}, () => new Array(N).fill(0));
  // 三个回溯方向：上/左/左上
  const backpaths = [[-1, 0], [0, -1], [-1, -1]];

  // 边界初始化
  S[0][0] = euclidian(X, Y, 0, 0);
  // 第一列只能从上方转移
  for (let i = 1; i < M; i++) {
    S[i][0] = Math.max(S[i-1][0], euclidian(X, Y, i, 0));
    backpointers[i][0] = 0;
  }
  // 第一行只能从左方转移
  for (let j = 1; j < N; j++) {
    S[0][j] = Math.max(S[0][j-1], euclidian(X, Y, 0, j));
    backpointers[0][j] = 1;
  }

  // 填充动态规划表
  for (let i = 1; i < M; i++) {
    for (let j = 1; j < N; j++) {
      const optionVals = [
        S[i-1][j],    // 选项0：从上转移
        S[i][j-1],    // 选项1：从左转移
        S[i-1][j-1]   // 选项2：从左上转移
      ];
      // 取最小值对应的索引
      const minVal = Math.min(...optionVals);
      const minIdx = optionVals.indexOf(minVal);
      backpointers[i][j] = minIdx;
      S[i][j] = Math.max(minVal, euclidian(X, Y, i, j));
    }
  }

  // 回溯找路径
  const path = [];
  let i = M - 1;
  let j = N - 1;
  // 正确终止条件：回到起点(0,0)就停止
  while (i > 0 || j > 0) {
    path.push([i, j]);
    const backDir = backpaths[backpointers[i][j]];
    i += backDir[0];
    j += backDir[1];
  }
  // 加入起点后反转得到正序路径
  path.push([0, 0]);
  path.reverse();

  // 返回离散Fréchet距离（瓶颈值）和对应路径，可直接用于d3可视化
  return {
    distance: S[M-1][N-1],
    path: path
  };
}

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