找回密码
 欢迎注册
查看: 25929|回复: 13

[原创] 一维空间中的航线设计问题

[复制链接]
发表于 2013-2-3 22:29:27 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
有$n$个城市,这些城市都在同一条直线上。

我们想设计若干条 在$2$个城市之间直飞 的航线,

使得任意$2$个城市都满足以下条件:

————————————————————
从一个城市出发,坐飞机到另一个城市,最多只需转机$k$次,

并且总飞行路程不得大于两个城市之间的距离。
————————————————————

于是,$k=0$就意味着任意$2$个城市都能直飞,至少需要$(n(n-1))/2$条航线。

问题$1$:当$k=1$时,至少需要多少条航线?

问题$2$:当$k=2$时,至少需要多少条航线?

问题$3$:当$k=3$时,至少需要多少条航线?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-2-3 22:54:09 | 显示全部楼层
我先给问题$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
复制代码
好了,“砖”抛完了,看看有没有“引玉”的效果
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-2-4 01:19:22 | 显示全部楼层
找到了$1$个数列:

http://oeis.org/A061168

该数列仅供参考。

是否问题$1$的答案有待查证。

#####

问题$1$已经做出来了,答案就是这个数列

接下来看看问题$2$和问题$3$的答案是多少吧(估计oeis上不会有答案了吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-2-4 08:46:40 | 显示全部楼层
3# KeyTo9_Fans
fans大牛总能提出高质量的问题,我很好奇fans的职业呢。

评分

参与人数 1经验 +3 收起 理由
KeyTo9_Fans + 3 我还在读研,还没工作呢

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-2-5 01:28:22 | 显示全部楼层
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多万循环

评分

参与人数 1贡献 +3 收起 理由
KeyTo9_Fans + 3 挺好的程序,因为方案数也可看作一数列。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-2-8 20:59:42 | 显示全部楼层
一维空间等于单轨铁路。所以只有相邻城市有航线。
LZ的问题估计是讨论同一条直线上城市上的垂直平面。那是2维了。

评分

参与人数 1经验 +3 收起 理由
KeyTo9_Fans + 3 飞机在空中划过一条弧线,弧线是2维的:)

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-2-8 22:25:05 | 显示全部楼层
有道理喔

飞机在一个城市起飞,然后在空中划过一道弧线,然后在一个城市降落,

于是航线就是$2$维的了。。。

这时

“总飞行路程不得大于两个城市之间的距离”

得改成

“乘机人在地面上的投影移动过的总路程不得大于两个城市之间的距离”

了。。。

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2015-1-30 16:32:56 | 显示全部楼层
当转机次数$k=1$,城市规模为$n$时,航线的设计方案如下:

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

1.png

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

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

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

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

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

解之,得:

$T(n)=O(n\log n)$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2015-1-30 18:25:48 | 显示全部楼层
当转机次数$k=2$,城市规模为$n$时,航线的设计方案如下:

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

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

2.png

我们为所有的二线城市各建立$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$时,结果如何呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-2-6 15:53:05 | 显示全部楼层
以下问题的解是 LZ 问题的解的下限:

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

点评

当$k\geq 1$时,为第$1$个点和其余$(n-1)$个点各连$1$条边,一共只需$(n-1)$条边。所以只能得到$(n-1)$这个下界。  发表于 2015-2-7 19:15
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 08:22 , Processed in 0.052825 second(s), 20 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表