BYR Achieve · 镜像论坛

【求助】火车票调度问题

2012/3/23镜像同步1 回复

最近在做一个简单的网上火车订票系统（接近于12306），但现在对于票、座位的分配问题有些纠结。我们考虑的情况是，列车不是直达的，中途有停站，如火车从 A——>B——>C——>D ，则该车上的任何一个座位的票，它不是只可以有一张票被售出，即它可以只被售出A——>D的票，也可以被售出一张A——>C的票和一张C——>D的票，或者被售出 A——>B， B——>C和C——>D 共三张票。我们想做到的是，该订票系统可以最大限度的合理的利用座位，即能在不浪费空座而且每个座位售出的所有票中，不能有道路交叉的情况下给人分配座位，并给出座位号。所以需要一个售票的调度算法。目前想到的比较笨的方法是，给每个座位建一个一维数组，数组长度=途径的站数-1, 表示最近的两站的区间数，分配一个座位时，只要保证该座位的每张票所对应的乘车区间没有交叉即可。火车上有多少座位，就开辟多少数组，但是这样空间开销很大。想问下版上众神，对于这个问题该如何思考比较好，能用什么样的数据结构和算法呢？或者是否有类似的经典的问题模型可以提供给我们参考的。谢谢

订阅后，新回复会通过你的通知中心匿名送达。