|
题义分析
本题的背景是N个太空站及往返于空间站与地球月球之间的太空船，问最少需要多少时间，使得规定的人数能够全部由地球到达月球。题目中的要求主要有：
1． 有许多个太空船，每个太空船的航线是固定的，某一太空船任一时刻的位置是事先确定的。同时每个太空船有各自规定的容量限制。
2． 地球、月球及太空站没有容量限制。
3． 初始时所有人都在地球，人往返于地球、月球及太空站的唯一途径是搭乘太空船。在移动过程中，各个人之间的行动是并行的。
4． 最终所有人到达月球，要求总时间最短。
算法讨论
如果不考虑数据量的限制，本题的解法很多。例如可变下界搜索法。但是由于人数较多（最多有50个人），每次可供选择的太空船也较多（最多有13个太空船），可以想象搜索量是比较大的，所以搜索并不是最理想的算法。
如果放宽条件，只求一个近似解（即时间尽可能短），贪心算法也是种可行的选择。最朴素的贪心就是使每个人按顺序由地球向月球移动，使得每次移动耗费最少的时间。这样做可以保证无解的数据得出正确答案，但对于有解的数据可能无法得到最优解。
由于本题要求时间最短，所以贪心无法得到符合要求的解。我们考虑从问题的图论模型入手，探索较为高效的求最优解算法。
网络流模型
本题中人的移动是并行的，在移动过程中又受到太空船容量的限制，这使我们联想到流网络。可以把太空船看作网络中的结点而把人的移动理解为容量。但仅仅这样建立流网络是不合理的，因为网络中的有向弧无法确定。在不同时刻，太空站之间的容量是不一样的，所以在网络的结点状态表示中加入时间一维，将时间与太空船编号结合，作为状态参量。
将时间加入后，又有了新的问题，即时间的不确定性，最短时间是问题的所求，初始时无法得知。为了适应模型的需要，我们不妨将原问题作一个变化，从反面来思考这个问题：
原问题是已知人数，求最短的移动时间；我们提出新的问题：已知某一时间T，求在时间T内能够移动到月球上的最多人数MaxMove(T)。这样，原问题的解就为  。
为了求解MaxMove(T)，建立以下网络G = (V，E)：
V = (I, J) (0<=I<=T，0<=J<=N+1)
其中I表示时刻I
J表示太空站或地球、月球。用0表示地球，N+1表示月球，1~N表示对应编号的太空站。以下将
月球地球、月球及太空站统称为站点。
E = (I,J) à (I+1, K)
边用来表示在站点I逗留或者通过太空船飞往其他站点K。由于这两种行为都耗费单位1的时间
所以两个点的时间参量相差1。
由于太空船有容量限制，所以给边加上容量限制：
其中Stay(s,I)表示太空船s时刻I停留的位置
Lim(s)表示太空船s的容量
由于站点是没有容量的，所以表示逗留的边容量是正无穷大
网络的源点是(0,0)，表示初始时所有人都在地球上。汇点是(T,N+1)，表示时刻T所有人到达月球。
在网络G中，人的移动表示为图G中的路径。由于由于人的移动是并行的，所以不同的人的移动可以分开考虑。从点(0,0)到点(T,N+1)的一条路径可以理解为第一个人从地球到月球的移动过程。同时，该条路径上的所有边流量为1。当第二个人考虑移动路线时，则要使得移动满足容量限制。通过不断增加人数，网络达到饱和，即无法再找到一条由(0,0)→(T,N+1)的增广路径，也就无法通过更多的人。这时得到的人数即为MaxMove(T)。
以上增加人数的过程就是增加流量的过程，网络能够通过的最多人数即为网络G的最大流。可以看出，一个流量为F的网络流与实际问题中F个人在T时刻内由地球到达月球的方案是互相唯一对应的；而网络G的最大流量即为在T时刻内由地球到达月球的最多人数。
至此，求解MaxMove(T)的方法已经确定。现在的问题就是如何通过MaxMove(T)的求解得到原问题的解。最为朴素的方法就是将变量T由1从小到大循环，直到MaxMove(T)≥K。但求解最大流的时间费用已经较为昂贵，这种算法势必导致求解整个问题的时间效率低下。所以必须寻找优化的途径来提高效率。
实现方法
朴素的循环思想虽然效率不高，但给了我们一个启发，可以通过逐步扩大T来得到最短时间。但如果每一次扩大T都对网络重新作一次最大流，时间复杂度又太高。可以看出当时间为T时，已经求解了T - 1次最大流，那么在求解MaxMove(T)时是否能够利用到以前的结果呢？
首先，T的扩大使得流网络增加了一些结点，即V(T,I) (I=0,1,2,..,N+1)。其次，网络的汇也由V(T-1,N+1)变为V(T,N+1)。但是存在容量为正无穷大的边E0 = V(T-1,N+1)àV(T,N+1)，所以原网络的所有流量都可以通过E0由原来的汇流到现在的汇。又因为原网络的所有结点都包含在新网络中，所以原网络的所有流量都可以在新网络中得到继承。也就是说，在用最大流求解MaxMove(T)时，初始的流量为MaxMove(T-1)，在MaxMove(T-1)的网络流基础上求最大流即可。算法如下：
1． 初始化流网络
2． NowFlow ← 0
3． T ← 0
4． Repeat
5． T ← T + 1
6． 增加新的结点，将汇点设为(T, N+1)
7． NowFlow ← NowFlow + MaxFlow(T) {最大的新增流量}
8． Until NowFlow ≥ K
9． 输出T
这样，原问题得到解决。时间复杂度为O((K + T) x once)，其中once表示找一次增广路径的时间复杂度。如果采用广度搜索找增广路径，时间复杂度（最坏情况）为O(once) = O((N x T x M)。当然，由于T是变量，所以这些估计都是较为粗糙的。
由于问题可能存在无解的情况，所以还必须对此作一个特殊处理。可以看出，如果对于T = +∞，网络G中存在由V(0,0)→V(X,N+1) (X = 1,2,3,4,…)的一条路径，那么问题一定有解。判断问题是否有解只要设定T=MaxT(一个足够大的时间)，寻找一次增广路径，如果存在增广路径，则问题有解，否则问题无解。
总结
本题的算法涉及到求解最大流过程，因此编程复杂度较大。我在比赛时由于时间紧张，对于解的存在性判断没有编程实现，因此无解的数据无法通过。同时在时间与空间上的优化不足，数据较大时无法通过。
通过家园一题的解题，我的感受是：
1． 对于基本算法及其数学模型的熟练掌握是解决实际问题的前提。实际问题的背景千变万化，只有对各种基本算法有一定程度的理解和认识，才能较快、较为准确地看出问题的模型，找到正确的解决方法。
2． 程序实现技巧与编程熟练程度是竞赛重要的基本功。本题涉及的最大流问题编程复杂度较大，同时还必须考虑空间和时间上的优化。在较少的竞赛时间内，必须同时考虑算法的效率和编程的时间代价。只有平时加强基本算法的编程训练，才能在较短时间内完成所设想的算法的程序设计。 |
网友评论：（只显示最新10条。评论内容只代表网友观点，与本站立场无关！） 
