IT宅来解答所谓的12306的售票所谓库存算法难题

【引言】 在天涯上看到有人发帖，也在Iteye上看到相同论调，本人对某些人所谓的“库存”难题的思路不以为然，对此，鄙人给出个算法模型，献丑，只为打某些人的脸！

一下是iteye上一篇文章提出的问题

引用

好了，讲了这半天淘宝，可以说12306了吧？

我以北京西到深圳北的G71次高铁为例（这里只考虑南下的方向，不考虑深圳北到北京西的，那是另外一个车次，叫G72），它有17个站（北京西是01号站，深圳北是17号站），3种座位（商务、一等、二等）。表面看起来，这不就是3个商品吗？G71商务座、G71一等座、G71二等座。大部分轻易喷12306的技术人员（包括某些中等规模公司的专家、CTO）就是在这里栽第一个跟头的。

实际上，G71有136*3=408种商品（408个SKU），怎么算来的？请看：

如果卖北京西始发的，有16种卖法（因为后面有16个站），北京西到：保定、石家庄、郑州、武汉、长沙、广州、虎门、深圳。。。。都是一个独立的商品，

同理，石家庄上车的，有15种下车的可能，以此类推，单以上下车的站来计算，有136种票：16+15+14....+2+1=136。每种票都有3种座位，一共是408个商品。



好了，再看出票时怎么减库存，由于商务、一等、二等三种座位数是独立的，库存操作也是一样的，下文我就不再提座位的差别的，只讨论出发与到达站。另外，下文说的是理论世界的模型，不是说12306的数据库就是这么设计的。

旅客A买了一张北京西（01号站）到保定东（02号站）的，那【北京西到保定东】这个商品的库存就要减一，同时，北京西到石家庄、郑州、武汉、长沙、广州、虎门、深圳等15个站台的商品库存也要减一，也就是说，出一张北京到保定东的票，实际上要减16个商品的库存！



这还不是最复杂的，如果旅客B买了一张北京西（01号站）到深圳北（17号站）的票，除了【北京西到深圳北】这个商品的库存要减一，北京西到保定东、石家庄、郑州、武汉、长沙、广州、虎门等15个站台的商品库存也要减1，保定东到石家庄、郑州、武汉、长沙、广州、虎门、深圳北等15个站台的商品库存要减1。。。总计要减库存的商品数是16+15+14+……+1=120个。

当然，也不是每一张票都的库存都完全这样实时计算，可以根据往年的运营情况，在黄金周这样的高峰时段，预先对票做一些分配，比如北京到武汉的长途多一点，保定到石家庄的短途少一点。我没有证据证实铁道部这样做了，但我相信，在还没有12306网站的时候，铁道部就有这种人工预分配的策略了。

    这里是我给出的模型思路

　　1.假设一列车从 A站驶往Z站 ，车上共有500个座位，也就是500张票
　　途径站点示意图如下：（用专业的话说，一个长度26的数组）

　　A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

　　有乘客甲购买了从 C --> R 站的车票，则在本列车对应站点的数组位置 +1，这里注意R站下车，R站不加1

　　A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
　　0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

　　乘客乙购买了从 H--》V 的车票 ，同样在本列车对应站点的数组位置 +1

　　A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
　　0 0 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 1 1 1 1

　　那么当乘客丙要购买从 A --》 P 站的票时，系统只要计算，从数组A --> P位置上乘客数量是否都小于500即可

　　请问，这样的算法很逻辑很复杂么？？！！加一操作现在很多NoSQL数据库都能支持原子性操作的。

　　另外给出12306在系统架构上的2点可能可行的建议

　　第一，按不同列车划分服务器，需要同步的是列车的数据，不同列车可以分布在不同服务器计算
　　第二，同一列列车的票务计算应该分服务器，以“分销商”形式进行分布式结算

　　以上述例子为例，如果将500张票，从总服务器预售给5台子服务器，每台子服务器售出自己的100张票后，在向总服务器结算，并从其他子服务器进行重新调度，这样同样避免了中央服务器的负担，同时能保证数据一致性问题。

   上述设计只是个框架性草案，只想告诉大家，12306的设计虽然复杂，但绝对没有某些人吹嘘的那样不能解决。我的这些算法估计在淘宝工程师面前，只是小儿科，别跟我较真。

总之，想铁道部那么大的机构，搞不定这样的问题，只能喷它管理不善，

评论

14 楼 lucky_god 2015-06-09  

13 楼 所谓码农 2015-01-06  

问题不是说不能解决，也没人说不能解决，别人只是说没那么简单。别动不动就想扇脸，免得不小心扇到自己

12 楼 所谓码农 2015-01-06  

自己行就是行，自己不行就是不行，没必要扯到淘宝工程师，事实上你所引用的文章作者对12306的理解比你更深刻。

11 楼 所谓码农 2015-01-06  

12306的模型要比你想的复杂的多，比如要有预留票，某个站能买某个车厢的票等等，要判断是否有票可售，理想情况下还需要考虑怎样提高座位利用率。

10 楼 所谓码农 2015-01-06  

明显是有问题的，A - D 有499个座位，D-G站有499个座位，不代表可以买从A - G，因为中途有人上下车，虽然总数不变，但座位变了。

9 楼 wangyuzhe04 2014-12-26  

如果一个服务器卖的快500张很快卖完了，然后去同步发现票池没票了于是就会告诉用户没票了，同时另一个服务器卖的慢还有票，会告诉用户说还有票买吧！这样会造成显示有票，但是买的时候就没了，返回显示还有票的现象，这种情况叫数据不同步。别忘了同时还有窗口，电话售票，如果你提前给服务器分配票，一直没卖完，就会一直不能同步，或者没及时同步，那窗口售票和电话售票会通知没票了，而网上还能买到。所谓服务器集群技术不是把大量服务器分开使用，而是把大量服务器当成一个服务器使用。12306算法没那么简单。其实12306引发的主要矛盾是一般人辛辛苦苦买不到票，而黄牛却能轻轻松松买到上千张票，所以大家很气愤。但是打击黄牛不是凭技术就能解决的，得从多方面入手

8 楼 lanmolsz 2014-03-21  

而且逻辑也特别清晰，比引用描述的要清晰很多。

7 楼 lanmolsz 2014-03-21  

方法十分巧妙

6 楼 lanmolsz 2014-03-21  

楼主真是聪明啊

5 楼 cetslj 2014-03-18  

不懂电脑的人最笨的方法：不管多少种席别，每种多少个座位，多少个站；把每一个相邻的站点席别当成一个独立的商品来卖(买一站也是要出票的)。

卖票的时候，只计算买票的站点是否连续相邻就行了。

假设全程只剩下最后一个空位置，但中间被人买了一站，这种情况要买全程是无票的，但中间任何站点，只要不是经过这个站的票(不考虑无座票)，都可以卖。

极端情况，每个人买的都是短途就下车，那这趟车就接近地铁了，如果短途非常严重，就接近公交了。我想，地铁应该就不控制票量的，哪里都卖，只控制每站容纳的最多进出人数，避免安全事故。

如果要限制起点终点和某些大站的票量控制，将这些连续站点设置为保留，优先保证起始和大站的票量。这些应该是平时工作中总结和预测的数，拿这些数字去控制票量。

别喷俺，俺不懂算法什么的，只会简单的电脑。我觉得这个方法最土最简单最靠谱，不会当成高深莫测的问题去研究。

4 楼 fengbin2005 2014-01-16  

其实多造几条铁路,就没我们什么事情了.

3 楼 linliangyi2007 2014-01-15  

yuliey 写道

算法还有问题，还要考虑坐位号问题如A——>C 坐位1号有1库存但库存也只有1
C——>F 坐位2号有库存但库存只有1
乘客要买A——>F 的时候你说是有票呢还是无票呢？现在12306应该是显示无票，如果分开买就会有票。这问题也要考滤进来。

这个算法的意义就是让你别把A-Z的各种组合作为库存来计算。

关于座位问题，一个萝卜一个坑，可以先计算是否有票，再让乘客选择座位，就跟飞机航班的座位自选系统一样的，位置和票分开算，没有必然联系

另外，说实话，你说的我没看懂啥意思。

2 楼 yuliey 2014-01-15  

算法还有问题，还要考虑坐位号问题如A——>C 坐位1号有1库存但库存也只有1
C——>F 坐位2号有库存但库存只有1
乘客要买A——>F 的时候你说是有票呢还是无票呢？现在12306应该是显示无票，如果分开买就会有票。这问题也要考滤进来。

1 楼 liuchaoyong 2014-01-15  

短途的让长途的，还有站票要考虑，
考虑 卖票的经济效益问题。