如何用最少调用次数找到三维空间中的未知预设点？

一、实现距离函数f #

按照要求实现输入任意点后，返回其与随机生成未知点距离的函数，核心计算欧几里得距离：

// 随机生成未知点（x、y、z为0-100的整数）
const targetPoint = {
  x: Math.floor(Math.random() * 101),
  y: Math.floor(Math.random() * 101),
  z: Math.floor(Math.random() * 101),
};

// 距离函数f：输入点s，返回与未知点的欧几里得距离
const f = (s) => {
  const dx = s.x - targetPoint.x;
  const dy = s.y - targetPoint.y;
  const dz = s.z - targetPoint.z;
  return Math.sqrt(dx * dx + dy * dy + dz * dz);
};

二、核心定位算法（仅需4次调用f） #

随机尝试的效率极低（最坏情况需上万次调用），而利用几何方程求解，仅需4次调用就能精准定位未知点：

算法原理 #

通过获取未知点到4个已知参考点的距离，建立平方距离方程求解坐标：

• 参考点1：(0,0,0)，距离平方 d0² = x² + y² + z²
• 参考点2：(100,0,0)，距离平方 d1² = (100-x)² + y² + z²
• 参考点3：(0,100,0)，距离平方 d2² = x² + (100-y)² + z²
• 参考点4：(0,0,100)，距离平方 d3² = x² + y² + (100-z)²

将方程两两相减消去平方项，可直接解出坐标：

• x = (10000 + d0² - d1²) / 200
• y = (10000 + d0² - d2²) / 200
• z = (10000 + d0² - d3²) / 200

由于目标坐标为整数，计算结果取整即可得到精准值。

代码实现 #

const locateTarget = () => {
  // 调用4次距离函数，获取四个参考点的距离
  const d0 = f({x: 0, y: 0, z: 0});
  const d1 = f({x: 100, y: 0, z: 0});
  const d2 = f({x: 0, y: 100, z: 0});
  const d3 = f({x: 0, y: 0, z: 100});

  // 计算距离平方值
  const d0Sq = d0 * d0;
  const d1Sq = d1 * d1;
  const d2Sq = d2 * d2;
  const d3Sq = d3 * d3;

  // 求解坐标（取整适配整数目标点）
  const x = Math.round((10000 + d0Sq - d1Sq) / 200);
  const y = Math.round((10000 + d0Sq - d2Sq) / 200);
  const z = Math.round((10000 + d0Sq - d3Sq) / 200);

  return {x, y, z, attempts: 4};
};

// 执行测试
const result = locateTarget();
console.log("找到的未知点：", result);
console.log("实际未知点：", targetPoint);
console.log("总尝试次数：", result.attempts);

三、算法优势对比 #

• 随机尝试：平均需数百到数千次调用，最坏情况次数无上限
• 方程求解法：固定4次调用即可精准定位，时间复杂度O(1)，是理论最优解

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