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

KeyTo9_Fans

有$n$个城市，这些城市都在同一条直线上。 我们想设计若干条 在$2$个城市之间直飞 的航线， 使得任意$2$个城市都满足以下条件： ———————————————————— 从一个城市出发，坐飞机到另一个城市，最多只需转机$k$次， 并且总飞行路程不得大于两个城市之间的距离。 ———————————————————— 于是，$k=0$就意味着任意$2$个城市都能直飞，至少需要$(n(n-1))/2$条航线。 问题$1$：当$k=1$时，至少需要多少条航线？ 问题$2$：当$k=2$时，至少需要多少条航线？ 问题$3$：当$k=3$时，至少需要多少条航线？

KeyTo9_Fans

我先给问题$1$抛块砖～ 我们用$1,2,3,...,n$表示$n$个城市，用$a$~$b$表示来往城市$a$和城市$b$的直飞航班， 于是： 当$n=1$时，需要$0$条航线； 当$n=2$时，需要$1$条航线：$1$~$2$； 当$n=3$时，需要$2$条航线：$1$~$2$、$2$~$3$； 当$n=4$时，需要$4$条航线：$1$~$2$、$2$~$3$、$3$~$4$、$1$~$4$； 当$n=5$时，需要$6$条航线：$1$~$2$、$2$~$3$、$3$~$4$、$4$~$5$、$1$~$3$、$3$~$5$； 当$n=6$时，需要$8$条航线：$1$~$2$、$2$~$3$、$3$~$4$、$4$~$5$、$5$~$6$、$1$~$3$、$3$~$5$、$3$~$6$； 当$n=7$时，需要$10$条航线：$1$~$2$、$2$~$3$、$3$~$4$、$4$~$5$、$5$~$6$、$6$~$7$、$1$~$4$、$2$~$4$、$4$~$6$、$4$~$7$。 综上所述，问题$1$的部分答案是：

1. n A1(n)
2. 1 0
3. 2 1
4. 3 2
5. 4 4
6. 5 6
7. 6 8
8. 7 10

复制代码

好了，“砖”抛完了，看看有没有“引玉”的效果

KeyTo9_Fans

找到了$1$个数列： http://oeis.org/A061168 该数列仅供参考。 是否问题$1$的答案有待查证。 ##### 问题$1$已经做出来了，答案就是这个数列 接下来看看问题$2$和问题$3$的答案是多少吧（估计oeis上不会有答案了吧）

wayne

3# KeyTo9_Fans fans大牛总能提出高质量的问题，我很好奇fans的职业呢。

wayne

4# wayne n=8,的确是13，我没动什么脑子，用最笨的穷举法算出来，只有4个，还比较快： {{1, 2}, {1, 3}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {3, 5}, {4, 5}, {5, 6}, {5, 7}, {5, 8}, {6, 7}, {7, 8}}, {{1, 2}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {4, 5}, {4, 6}, {4, 7}, {4, 8}, {5, 6}, {5, 7}, {6, 7}, {7, 8}}, {{1, 2}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {4, 5}, {4, 6}, {4, 7}, {4, 8}, {5, 6}, {6, 7}, {6, 8}, {7, 8}}, {{1, 2}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}, {5, 6}, {5, 7}, {5, 8}, {6, 7}, {7, 8}} n=9就力不从心了，有300多万循环

zeroieme

一维空间等于单轨铁路。所以只有相邻城市有航线。 LZ的问题估计是讨论同一条直线上城市上的垂直平面。那是2维了。

KeyTo9_Fans

有道理喔 飞机在一个城市起飞，然后在空中划过一道弧线，然后在一个城市降落， 于是航线就是$2$维的了。。。 这时 “总飞行路程不得大于两个城市之间的距离” 得改成 “乘机人在地面上的投影移动过的总路程不得大于两个城市之间的距离” 了。。。

KeyTo9_Fans

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

我们将第$\lfloor(n+1)/2\rfloor$个城市作为“中转城市”，为其余所有城市各建立一条到中转城市的航线，如下图所示：



于是当出发地和目的地位于不同的左右半区时，只需在中转城市转机$1$次。

于是只剩下出发地和目的地位于相同的半区的情况需要考虑，

这种情况只需要分别解决两个城市规模为$(n-1)/2$的问题即可。

记规模为$n$的问题所需航线数量为$T(n)$，于是我们有：

$T(n)=2T((n-1)/2)+O(n)$

解之，得：

$T(n)=O(n\log n)$

KeyTo9_Fans

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

我们将第$\sqrt{n}$、$2\sqrt{n}$、$3\sqrt{n}$、$(\sqrt{n}-1)\sqrt{n}$个城市作为“一线城市”，其余城市作为“二线城市”。

于是二线城市被一线城市分成了$\sqrt{n}$个区域，每个区域有$\sqrt{n}$个二线城市，如下图所示：



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

我们为任意两个一线城市都建立$1$条航线，使得任意两个一线城市都能直达，一共需要$O(n)$条航线。

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

于是只剩下两个城市属于相同的区域的情况，只需要分别解决$\sqrt{n}$个规模为$\sqrt{n}$的问题即可。

记规模为$n$的问题所需的航线数量为$T(n)$，于是我们有：

$T(n)=\sqrt{n}T(\sqrt{n})+O(n)$

解之，得：

$T(n)=O(n\log\log n)$

注意：所有带根号的数值都需要取整并酌情加减$1$。

#####

当转机次数$k=3$时，结果如何呢？

sunwukong

以下问题的解是 LZ 问题的解的下限：

已知，\(n\) 阶连通图中最大的路径长度为 \(k+1\)，求边的最小数 \(T(n)\)。