ACM通信

最后一个字节

排他性探针

丹尼斯·沙沙村
ACM通信，2022年7月，第65卷第7期，第96-ff页
10.1145 / 3538640
评论

力场中有一定数量的粒子。根据排他性原理，它们之间的差别至少是相等的k在d每个维度都是二进制值的维度(例如，向上或向下自旋)。如果有帮助的话，把场景想象成d维超立方体。

已知粒子的数量，你想知道它们的位置。

位置上的“精确探头”p如果粒子在位置，将返回“是”p否则,“不”。

热身:有两个二元维度。有两个粒子，它们在两个维度上的位置必然不同。需要多少精确的探针才能找到这两个粒子的尺寸。

热身的解决方案:只有一个探针。粒子可以位于(0,0)和(1,1)的位置，也可以位于(0,1)和(1,0)的位置。在(0,0)位置上的单个探针可以区分这两种情况。

问题:假设有三个维度和三个粒子使得任意两个粒子至少在两个维度上不同。需要多少精确的探针才能找到这三种粒子的位置?

解决方案:

探针(0,0,0)。

如果探测返回'yes '，那么有三种可能:

(0,0,0)， (0,1,1)， (1,0,1)

(0,0,0)， (0,1,1)， (1,1,0)

(0,0,0)， (1,0,1)， (1,1,0)

(Case (0,0,0) yes， (0,1,1) no)如果探测返回'no'到(0,1,1)，那么三个位置是(0,0,0)，(1,0,1)，(1,1,0)。

数字有三种粒子使得每对粒子在这些维度中至少有两个不同。需要多少精确的探针才能找到这三种粒子的位置?

(情况(0,0,0)是，(0,1,1)是)但如果探测在(0,1,1)处发现了粒子，那么还剩下两种可能((1,0,1)和(1,1,0))，所以还需要一个探测。所以，在最坏的情况下，需要三个。(请注意(0,0,0)和(1,1,1)不能都返回'yes'，因为这样第三个粒子将与其中一个粒子相距一个维度。)

如果(0,0,0)探测返回'no '，那么尝试在(0,0,1)处进行探测。

(Case (0,0,0) no， (0,0,1) yes)如果探测在(0,0,1)处返回'yes '，那么可能性是

(0, 0, 1), (1, 1, 1), (1, 0, 0)

(0, 0, 1), (1, 1, 1), (0,1,0)

所以在(1,0,0)处再做一个探查就足够了。

如果两个精确探测(0,0,0)和(0,0,1)都返回'no '，那么尝试(0,1,1)。

(Case (0,0,0) no， (0,0,1) no， (0,1,1) no)如果探针返回'no '，那么有以下几种可能性(其中N意味着之前的探测已经排除了这种可能性)。

N (0, 0, 0)

N (0 0 1)

(0,1,0)

(0, 1, 1) N

(1,0,0)

(1,0, - 1)

(1, - 1, 0)

(1, 1, 1)

那么(0,1,0)一定有一个粒子(1,0,0)和(1,1,1)。没有其他三联在至少两个维度上是成对不同的。

(Case (0,0,0) no， (0,0,1) no， (0,1,1) yes)如果(0,1,1)返回'yes '，那么我们有

N (0, 0, 0)

N (0 0 1)

(0,1,0)

(0, 1, 1) Y

(1,0,0)

(1,0, - 1)

(1, - 1, 0)

(1, 1, 1)

在这种情况下，只有(0,1,1)，(1,0,1)和(1,1,0)是可能的。

最终的解决方案。

请注意，如果只有一个粒子，那么我们可能需要多达7个精确的探测器才能找到它。因此，让我们考虑对探头设计的一些改进。

一个d-离开探头在一个位置p如果粒子在，将返回'yes'p确切地说，或者粒子不在那里但在距离内至少有一个粒子d在哪里d是否有一定的汉明距离(0和1之间的维度差数)p，如果距离内没有粒子，则返回“no”d。

一次性探测有多有用?

问题:假设在三维空间中有一个粒子。使用精确的探测器，人们可能需要7个探测器才能找到粒子的位置。一次性探针和精确探针的组合是什么情况?

解决方案:

在(0,0,0)处使用一个单向探针。如果是，那么可能是:

0 0 0

0 0 1

0 1 0

1 0 0

在(0,1,1)处使用一个单向探针。如果粒子距离为1，那么有两种可能(0,0,1)和(0,1,0)。如果没有，则再次出现两种可能性(0,0,0)和(1,0,0)。不管怎样，只需要一个精确的探针。

如果在(0,0,0)处的单向探测为no，则又有四种可能:

0 1 1

1 0 1

1 1 0

1 1 1

同样，从0 0 1开始，一个单距离探测后面跟着一个精确探测就足够了。

最终的解决方案。

一个“精确的单距离”探测为位置上的探测提供了三个答案p：

1. “精确的”，如果有一个粒子在p完全
2. 如果粒子距离为1，则为“近”
3. '不'，如果没有粒子p或者在距离1之内。

问题:考虑与前面相同的设置:三维和三个粒子，使每两个粒子至少在两个维度上不同。在最坏的情况下，需要多少精确的单向探针才能找到所有三个粒子的位置?是否有可能仅用一个精确的一次性探针就知道所有粒子的位置?

解决方案:

在最坏的情况下，它仍然可能需要多达三个。尝试(0,0,0)一个精确的单距离探测。如果探测器发现了一个粒子，那么仍然有三种可能性:

(0, 0, 0)、(0,1,1),(1,0,- 1)

(0, 0, 0)、(0,1,1),(1 1 0)

(0, 0, 0)、(1,0,- 1),(1 1 0)

如果下一个探测在(0,1,1)处，那么如果粒子在那里，第三个粒子可能在(1,0,1)或(1,1,0)处，因此可能需要三个探测。

然而，如果(0,0,0)没有粒子，也没有距离1的粒子，那么只有以下几种可能性:

(0, 1, 1)

(1,0, - 1)

(1, - 1, 0)

(1, 1, 1)

在这三种情况中，只有前三种情况彼此相距两个距离，所以它们是唯一的可能性。在这种情况下，我们只需要一个精确的单向探针。

最终的解决方案。

独家物理公司提出了一种“径向探头”，当应用到一个位置p，会说是否有粒子在p还有离它有多少p，有多少两个距离p以此类推，直到空间的维数。

问题:再次考虑与上一个问题相同的设置:三维和三个粒子，使任意两个粒子至少在二维上不同。在最坏的情况下，需要多少径向探针才能找到所有三个粒子的位置?

---

给你一些粒子，你想知道它们的位置。

---

解决方案:

在最坏的情况下，可能仍然需要三个探测。用径向探针尝试(0,0,0)。如果探测器发现了一个粒子，那么我们也有同样的可能性。

(0, 0, 0)、(0,1,1),(1,0,- 1)

(0, 0, 0)、(0,1,1),(1 1 0)

(0, 0, 0)、(1,0,- 1),(1 1 0)

径向探针会说在距离(0,0,0)为2的地方有两个粒子，但我们已经知道了。如果第二个径向探针测试(0,1,1)并发现一个粒子，那么径向探针将再次表示在距离2的地方有另一个粒子。但要确定哪一个需要再做一次探查。

最终的解决方案。

根据问题、探针类型和分析类型的不同，可能有许多新贵。这里有一些。

Upstart 1:假设我们有k维度,n任何两个粒子都必须相差f尺寸，我们只有精确的探测器。找到一个能给出最小最坏情况结果的算法，在所有能达到最小最坏情况结果的算法中，给出最好的可能的平均情况结果。

Upstart 2:与Upstart 1相同，但探测可以是d了,完全d离开或径向。

Upstart 3:如果粒子的构型C被放置的方式使其他构型C不能满足下列任一条件，则称其为“最大扩散”:

1. C'中所有成对距离的最小值，即minpair(C')，具有minpair(C') < minpair(C)的性质。
2. minpair(C') = minpair(C)但C'， sumpair(C')中的成对距离之和具有sumpair(C') < sumpair(C)的性质。

如果一个配置被最大限度地扩展，你能否针对upstart 1或upstart 2改进你的算法?

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2022 ACM, Inc.

---

没有发现记录