应该使用哪个算法来找到这个点？

Question

你需要在三维空间中找到一个未知的、预定的点，使用只能返回从任何传递给它的点到所需未知点的距离的函数，在最少的尝试次数内找到该点。

为了解决这个问题，首先要实现一个函数f，通过取任意点s(x, y, z)的坐标，返回该点与条件未知的随机生成点之间的距离。

你可以任意生成点r(x, y, z)，其中x、y、z可以是0到100之间的整数。例如，对于任意生成的点r(0, 0, 10)和传递给函数的点s(0, 0, 0)，函数的结果将如下所示：f(s) = 10 // s(0, 0, 0)与r(0, 0, 10)之间的距离为10。接下来，实现分配本身的算法。该算法应该找到任意生成点的坐标，并且调用函数f的次数最少。

我只有一个随机器而不是算法，请帮忙。

const pointToFound = {
  x: 12,
  y: 9,
  z: 76,
};

let attemts = 0;
let isXFound = false;
let isYFound = false;
let isZFound = false;

const pointHistory = [];

const getRandomPoint = () => {
  return {
    x: isXFound ? isXFound : Math.floor(Math.random() * 101),
    y: isYFound ? isYFound : Math.floor(Math.random() * 101),
    z: isZFound ? isZFound : Math.floor(Math.random() * 101),
  };
};

const getDifference = (point, pointToCompare) => {
  return {
    x:
      Math.max(point.x, pointToCompare.x) - Math.min(point.x, pointToCompare.x),
    y:
      Math.max(point.y, pointToCompare.y) - Math.min(point.y, pointToCompare.y),
    z:
      Math.max(point.z, pointToCompare.z) - Math.min(point.z, pointToCompare.z),
  };
};

const condition = !isXFound && !isYFound && !isZFound;

while (condition) {
  const point = getRandomPoint();

  const difference = getDifference(point, pointToFound);
  pointHistory.push(point);

  attemts += 1;

  if (isXFound && isYFound && isZFound) {
    console.log("Total attempts: ", attemts);
    console.log(point);
    break;
  }

  if (difference.x === 0 && !isXFound) {
    isXFound = point.x;
  }

  if (difference.y === 0 && !isYFound) {
    isYFound = point.y;
  }

  if (difference.z === 0 && !isZFound) {
    isZFound = point.z;
  }
}

console.log(pointHistory);

我只有一个随机生成器，没有算法。请帮忙。

- Ryan Celsius

---

如果你选择两个随机点，你几乎拥有了所有需要的东西。想象一下如果没有程序或电脑，你会如何做到这一点。 - Pointy

尝试在纸上绘制问题的二维版本图表。给自己一个目标点，然后选择几个测试点。对于每个测试点，计算距离，然后突出显示所有其他具有相同距离值的点。如果您对所有测试点都这样做，可能会发现一些有用的东西。 - John

Answer 1

一个想法如下：

你选择一个初始的随机点，对于每个维度，找到确切的值。怎么做？为了对称起见，假设你要找到目标点的x。将x增加一，计算新点与目标点的距离。如果更远了，意味着你应该朝相反的方向移动。因此，你可以运行一个二分查找，并得到距离，以找到目标点的确切x。否则，它意味着你沿着X轴朝正确的方向前进。因此，在所有具有相同y和z的点之间进行二分搜索，这些点的x值可以从x+1到100变化。以下是更正式的解决方案（伪代码）。

你也应该询问这个解决方案的复杂性。由于点的维数是常数（3），检查这些条件需要常数时间，调用getDifference函数的次数的复杂度为O(log(n))。这里的n是坐标的有效范围的长度（这里是100）。

1. p: (x,y,z) <- Pick a random coordinate
2. dist: (dist_x, dist_y, dist_z) <- getDifference(p, TargetPoint)
3. For each dimension, do the following (i can be 0 (x), 1 (y), 2 (3)):
4.       if(dist == 0):
5.           isFound[i] <- p[i]
6.           continue

7.     new_i <- p[i] + 1
8.     new_point <- p
9.     new_point[i] <- new_i
10.    new_dist <- getDifference(new_point, pointToFound)
11.    if(new_dist == 0):
12.        isFound[i] <- new_point[i];
13.        continue
    
14.    if(new_dist[i] > dist[i]):
15.        isFound[i] <- binary_search for range [0, p[i]-1] to find the exact value of the pointToFound in dimension i
15.        continue
16.    else:
17.        isFound[i] <- binary_search for range [p[i] + 1, 100] to find the exact value of the pointToFound in dimension i      
18.        continue

- OmG

Answer 2

最多只需要3次猜测，通常只需要2次猜测就可以完成：

• 第一次猜测为[0, 0, 0]，并询问距离
• 在100x100x100的立方体中找到所有与[0, 0, 0]距离为那个的点。可能有大约100-200个点具有该距离：考虑所有这些候选项。
• 将第一个候选项作为第二次猜测，并询问距离
• 在其他候选项中查找那些与第一个候选项的距离恰好相等的点。通常只有一个点满足此条件。在这种情况下，我们可以返回该候选项，只需要2次猜测。
• 否则（当仍有多个候选项时）重复上一步，这现在肯定会导致单个点。

以下是一个实现，它提供了一个黑盒函数，该函数选择本地变量中的秘密点，并返回两个函数：f用于调用者提交猜测，report用于验证算法结果并报告猜测次数。这不是算法本身的一部分，算法本身在findPoint函数中提供。

const rnd = () => Math.floor(Math.random() * 101);

const distance = (a, b) =>
    a.reduce((acc, x, i) => acc + (x - b[i]) ** 2, 0) ** 0.5;

function findPoint(f) {
    // First guess is always the zero-point
    let guess = [0, 0, 0];
    let dist = f(guess);
    if (dist === 0) return guess; // Extremely lucky!
    // Find the points in the cube that have this distance to [0,0,0]
    let candidates = [];
    const limit = Math.min(100, Math.round(dist));
    for (let x = 0; x <= limit; x++) {
        const p = [x, limit, 0];
        // Follow circle in X=x plane
        while (p[1] >= 0 && p[2] <= limit) {
            const d = distance(p, guess);
            const diff = d - dist;
            if (Math.abs(diff) < 1e-7) candidates.push([...p]);
            if (diff >= 0) p[1]--;
            else p[2]++;
        }
    }
    // As long there are multiple candidates, continue with a guess
    while (candidates.length > 1) {
        const candidates2 = [];
        // These guesses are taking the first candidate as guess
        guess = candidates[0];
        dist = f(guess);
        if (dist === 0) return guess; // lucky!
        for (const p of candidates) {
            let d = distance(p, guess);
            let diff = d - dist;
            if (Math.abs(diff) < 1e-7) candidates2.push(p);
        }
        candidates = candidates2;
    }
    return candidates[0]; // Don't call f as we are sure!
}

function blackbox() {
    const secret = [rnd(), rnd(), rnd()];
    console.log("Secret", JSON.stringify(secret));
    let guessCount = 0;
    const f = guess => {
        guessCount++;
        const dist = distance(secret, guess);
        console.log("Submitted guess " + JSON.stringify(guess) + " is at distance " + dist);
        return dist; 
    };
    const report = (result) => {
        console.log("Number of guesses: " + guessCount);
        console.log("The provided result is " + (distance(secret, result) ? "not" : "") + "correct");
    }
    return {f, report};
}

// Example run
const {f, report} = blackbox();
const result = findPoint(f);
console.log("Algorithm says the secret point is: " + JSON.stringify(result));
report(result);

每次运行都会生成一个新的秘密点。当运行数千次时，结果表明算法需要第三次猜测的概率为1/9。在其余8/9的情况下，算法需要两次猜测。

- trincot

Answer 3

以下方法适用于具有正值或负值实数坐标的情况。

假设您正在搜索点P的坐标。作为第一个查询点，请使用原点O。让到原点O的距离为|PO|。此时，您知道P在球体表面上。

(P.x)^2 + (P.y)^2 + (P.z)^2 = |PO|^2  (1)

作为第二个查询点，使用Q = (|PO|，0，0)。不太可能但如果您发现距离|PQ|为零，Q是您要查找的点。否则，您会得到另一个球面方程，并且您知道P也在这个球面的表面上：

(P.x - |PO|)^2 + (P.y)^2 + (P.z)^2 = |PQ|^2   (2)

现在，如果你从（2）中减去（1），你会得到

(P.x - |PO|)^2 - (P.x)^2 = |PQ|^2 - |PO|^2  (3)

由于此方程式中唯一未知数是 P.x，因此您可以得到它的值：

P.x = (((-|PQ|^2 + |PO|^2) / |PO|) + |PO|)/2)

通过类似的步骤，您可以使用 R = (0, |PO|, 0) 和 S = (0, 0, |PO|) 获取 P.y 和 P.z。因此，通过使用四个查询点 O、Q、R 和 S，您可以获取 P 的坐标。

- burkay