一维空间中的航线设计问题

KeyTo9_Fans

当转机次数$k=3$，城市规模为$n$时，航线的设计方案如下：

我们将第$\log n$、$2\log n$、$3\log n$、……、$n/(\log n)*\log n$个城市作为“一线城市”，其余城市作为“二线城市”。

于是二线城市被一线城市分成了$n/(\log n)$个区域，每个区域有$\log n$个二线城市。

我们为所有的二线城市各建立$2$条航线，分别连接左右两边最近的一线城市，一共需要$O(n)$条航线。

对于一线城市，我们解决一个转机次数为$1$、城市规模为$n/(\log n)$的航线设计问题，一共需要$n/(\log n)*\log(n/(\log n))=O(n)$条航线。

于是任意两个城市，只要属于不同的区域，都可以转机不超过$3$次到达。

于是只剩下两个城市属于相同的区域的情况，只需要分别解决$n/(\log n)$个转机次数为$3$、城市规模为$\log n$的航线设计问题即可。

记转机次数为$3$、城市规模为$n$的问题所需的航线数量为$T(n)$，于是我们有：

$T(n)=n/(\log n)*T(\log n)+O(n)$

解之，得：

$T(n)=O(n\log^{**}n)$

注：所有$\log$运算的底数均为$2$，运算结果都需要取整并酌情加减$1$。

$\log^{**}n$表示至少需要对$n$进行多少次$\log$运算，其结果才小于$2$。

#####

当转机次数$k=4$，城市规模为$n$时，航线的设计方案如下：

我们将第$\log\log n$、$2\log\log n$、$3\log\log n$、……、$n/(\log\log n)*\log\log n$个城市作为“一线城市”，其余城市作为“二线城市”。

于是二线城市被一线城市分成了$n/(\log\log n)$个区域，每个区域有$\log\log n$个二线城市。

我们为所有的二线城市各建立$2$条航线，分别连接左右两边最近的一线城市，一共需要$O(n)$条航线。

对于一线城市，我们解决一个转机次数为$2$、城市规模为$n/(\log\log n)$的航线设计问题，一共需要$n/(\log\log n)*\log\log(n/(\log\log n))=O(n)$条航线。

于是任意两个城市，只要属于不同的区域，都可以转机不超过$4$次到达。

于是只剩下两个城市属于相同的区域的情况，只需要分别解决$n/(\log\log n)$个转机次数为$4$、城市规模为$\log\log n$的航线设计问题即可。

记转机次数为$4$、城市规模为$n$的问题所需的航线数量为$T(n)$，于是我们有：

$T(n)=n/(\log\log n)*T(\log\log n)+O(n)$

解之，得：

$T(n)=O(n\log^{**}n)$

#####

对于更大的转机次数$k$，结果如何呢？

KeyTo9_Fans

当转机次数$k\geq 5$，城市规模为$n$时，航线的设计方案如下：

我们将第$\log^{** ** ... **}n$、$2\log^{** ** ... **}n$、$3\log^{** ** ... **}n$、……、$n/(\log^{** ** ... **}n)*\log^{** ** ... **}n$个城市作为“一线城市”，其余城市作为“二线城市”。

于是二线城市被一线城市分成了$n/(\log^{** ** ... **}n)$个区域，每个区域有$\log^{** ** ... **}n$个二线城市。

我们为所有的二线城市各建立$2$条航线，分别连接左右两边最近的一线城市，一共需要$O(n)$条航线。

对于一线城市，我们解决一个转机次数为$k-2$、城市规模为$n/(\log^{** ** ... **}n)$的航线设计问题，一共需要$n/(\log^{** ** ... **}n)*\log^{** ** ... **}(n/(\log^{** ** ... **}n))=O(n)$条航线。

于是任意两个城市，只要属于不同的区域，都可以转机不超过$k$次到达。

于是只剩下两个城市属于相同的区域的情况，只需要分别解决$n/(\log^{** ** ... **}n)$个转机次数为$k$、城市规模为$\log^{** ** ... **}n$的航线设计问题即可。

记转机次数为$k$、城市规模为$n$的问题所需的航线数量为$T(n)$，于是我们有：

$T(n)=n/(\log^{** ** ... **}n)*T(\log^{** ** ... **}n)+O(n)$

（以上所有的$\log$上面均有$\lfloor(k-3)/2\rfloor$个$**$）

解之，得：

$T(n)=O(n\log^{** ** ... **}n)$（$\lfloor(k-1)/2\rfloor$个$**$）

注：$\log^{** ** ... **}n$（$k+1$个$**$）表示至少需要对$n$进行多少次$\log^{** ** ... **}$（$k$个$**$）运算，其结果才小于$2$。

#####

根据上面的结果，我们有以下推论：

当城市数量为$n$，航线数量为$c*n$（$c$为大于等于$4$的常数）时，

最佳的航线设计方案可以使得任意两个城市之间都最多只需转机$2\alpha(n)$次就可以到达。

注：

当$x\geq 4$时，$\alpha(x)-2$表示至少需要多少个$**$，$\log^{** ** ... **}x$才小于$4$。

例如：$\alpha(4)=2$，$\alpha(16)=3$，$\alpha(65536)=4$，$\alpha(2^{2^{2^{...}}})=5$（$65536$层指数塔），，……

KeyTo9_Fans

以上结果讨论的都是“上界”，但是光给出上界还不算完美解决此问题。

实际上，前面讨论的所有结果早在$35$年前（也就是$1982$年）就被Yao【参考文献[1]】发表了。

而$10$楼提到了“下界”，也就是讨论【至少需要多少条航线】。

此问题一直没能完美解决，直到$2017$年Hu等人（楼主只是“等人”之一）发表了【参考文献[2]】：

https://link.springer.com/article/10.1007%2Fs00453-017-0307-3

此问题才在大欧表示法下完美解决，只剩下常数因子需要进一步确定。

该论文的摘要如下。



摘要里的$t$是本贴的$(k+1)$，可以理解成【乘机次数】。

该论文的全文如下。

rangesum.pdf (331.93 KB, 下载次数: 2)

2018-8-14 19:31 上传

点击文件名下载附件

该论文把此贴的【航线设计问题】说成数据库领域里的【半群下区间之和查询问题】，把【乘机次数】说成【查询所需时间】，把【航线数量】说成【查询所需空间】，是为了将此问题说得很高大上罢了，实际上与本贴讨论的是相同的问题。

该论文的主要贡献如下。

$1$、当转机次数$k=1$时，证明了至少需要$\Omega(n\log n)$条航线，证明过程如下：

首先长度为$1$的航线至少需要$\Omega(n)$条；

然后由于距离为$3$的城市无法转机$1$次到达，必需建立长度为$2$或$3$的航线，易证该长度的航线至少需要$\Omega(n)$条；

然后由于距离为$7$的城市无法转机$1$次到达，必需建立长度为$4$到$7$的航线，易证该长度的航线至少需要$\Omega(n)$条；

然后由于距离为$15$的城市无法转机$1$次到达，必需建立长度为$8$到$15$的航线，易证该长度的航线至少需要$\Omega(n)$条；

然后由于距离为$31$的城市无法转机$1$次到达，必需建立长度为$16$到$31$的航线，易证该长度的航线至少需要$\Omega(n)$条；

……

依次类推，得到转机次数$k=1$时，$n$个城市至少需要$\Omega(n\log n)$条航线。

这个结果与上界$O(n\log n)$是同一个级别的增长速度，他们只是差了一个常数因子。

$2$、当转机次数$k=2$时，证明了至少需要$\Omega(n\log\log n)$条航线，证明的要点如下：

长度为$1$到$2$的航线至少需要$\Omega(n)$条；

长度为$3$到$8$的航线至少需要$\Omega(n)$条；

长度为$9$到$(3^4-1)$的航线至少需要$\Omega(n)$条；

长度为$3^4$到$(3^8-1)$的航线至少需要$\Omega(n)$条；

长度为$3^8$到$(3^16-1)$的航线至少需要$\Omega(n)$条；

长度为$3^16$到$(3^32-1)$的航线至少需要$\Omega(n)$条；

……

依次类推，得到转机次数$k=2$时，$n$个城市至少需要$\Omega(n\log\log n)$条航线。

这个结果与上界$O(n\log\log n)$是同一个级别的增长速度，他们只是差了一个常数因子。

$3$、当转机次数$k\geq 3$时，利用转机次数$(k-2)$的结果，通过数学归纳法证明了至少需要$\Omega(n\log^{** ** ** ... **}n)$（$\lfloor(k-1)/2\rfloor$个$**$）条航线，证明的要点如下：

长度为$A_k(i)$到$A_k(i+1)$的航线至少需要$\Omega(n)$条。

其中$A_k(i)$的增长速度与$i$的$\lfloor(k+3)/2\rfloor$阶超运算的增长速度相当，其反函数的增长速度与$log^{** ** ** ... **}(i)$（$\lfloor(k-3)/2\rfloor$个$**$）的增长速度相当，

由此可得至少需要$\Omega(n\log^{** ** ** ... **}n)$（$\lfloor(k-1)/2\rfloor$个$**$）条航线。

这个结果与上界$O(n\log^{** ** ** ... **}n)$（$\lfloor(k-1)/2\rfloor$个$**$）是同一个级别的增长速度，他们只是差了一个常数因子。

于是给定变量$k$和$n$，所需航线数量的上下界在大欧表示法下已经完全一致了，只剩下常数因子需要进一步确定（不在文献[2]的讨论范围）。

参考文献：

[1] Andrew Chi-Chih Yao. Space-time tradeoff for answering range queries (extended abstract). In STOC, pages 128 - 136, 1982.

[2] Hu X, Tao Y, Yang Y, et al. Semi-Group Range Sum Revisited: Query-Space Lower Bound Tightened. Algorithmica, 80(4): 1315-1329, 2018.