12
Mar

12306选座算法分析和应用

分类: 技术分享   |  标签: , ,   |  共有: 2,171 次浏览 , 暂无评论

train

事情的起因是最近经常要来回于杭州和北京,由于比较讨厌来回机场的奔波,所以如果有高铁的话我尽量就选择高铁了。而从杭州到北京的高铁最快也要5个小时,由于公司报销的原因,屌丝只能选择二等座,所以,就想着怎样才能用相同的价格选到更加舒服的位置。国内高铁的二等座,采用的是3+2的作为布局方式,分别为A.B.C+D.F的座位编号,所以位置的优劣应该就是F>A>D>C>B。而我们的目标,就是如何能通过网站或者客户端软件选中里面的F座。

首先,要知道的是国内的12306网站只允许在一天内三次取消订单,而最后的座位编号是在出订单以后才确认的,所以下面的操作需要多个帐号进行配合操作。

接下来,我们就来说说12306的选座算法(这是我经过了几十次取消订单估算出来的,虽然说不能确保100%准确,但是实际验证下来,我后面连续七八次都可以操作成功,所以这个算法应该差不多了)。现在看来,12306采用的保留最大连续区块的算法,也就是用户发起订票操作以后,会优先选取当前车厢中的零散票,然后,再一次从前往后销售车票。

下面用实际场景来说几个案例,假设当前车厢第7排位置全空为例:

如果买1张车票,分配7A;继续买1张车票,7B;依次顺推;

tr-1

如果买2张车票,分配7A,7B;继续买两张车票,分配7D,7F;

tr-2

如果买3张车票,分配7A,7B,7C;

tr-3

如果买4张车票,分配7A,7B,7C,7D;

tr-4

我们的目的,就是要把当前的座位行的A,B,C,D填充满,但同时保留最后一个F座空闲,就可以达到我们的目标了。

但现在有一个问题,就是我们要确定当前排具体的剩余位置情况,也就是填充的初始值。所以,先发起1张订票申请。

  • 情况A:

如果这1张订票获取到的是7A,也就说明待分配的这一行全空,那么取消这张订票,然后发起一次4张订票,占据7A,7B,7C,7D就可以了

tr-x1

  • 情况B:

如果这1张订票是7B,那么分配前座位可能是 A,_,_,_,_,或者是A,_,C,D,F。

tr-x2

接下来我们再发起3张订票,如果分配到的是7C,7D,7F,说明是前者,如果分配到8A,8B,8C则说明是后者。

tr-x3

如果是前者,接下来我们参考(情况A)再发起4张订票就能挤出F座,如果是后者,取消这个3张订票,再按(情况A)发起4张也就能挤出F座了。

  • 情况C:

如果这1张订票是7C,那么分配前的位置要么是A,B,_,_,_,要么是A,B,_,D,F。

tr-x4

接下来我们再发起2张订票,如果分配到的是7D,7F,说明是前者,如果分配到的是8A,8B则说明是后者。

tr-x5

如果是前者,接下来我们参考(情况A)再发起4张订票就能挤出F座,如果是后者,就取消这两张订票,再按(情况A)发起4张也就能挤出F座了。

  • 情况D:

如果这1张订票是7D,那么分配前的位置要么是A,B,C,_,_,要么是A,B,C,_,F。

tr-x6

接下来我们再发起1张订票,如果是前者你会直接得到F座,如果是后者,那么取消订单之后再按(情况A)发起4张也就能挤出F座了。

  • 情况F:

如果这1张订票是7F,那么,恭喜你,一次成功。

– – – – – 我是分割线 – – – – –

但是,上面的招数不一定每次都成功,因为还有一种例外情况,就是后续位置中有用户退票导致的零星空窗,这样的话,单独的1张订票就很可能被塞到后面去,这种情况就只能单独用一个帐号来填充这个空位了。

由于坐火车的人太多,没有那么多和我们一样无聊的人,所以,基本上多试几次,就能订到F了。不说了,我要去订车票去了…




在下方发表关于本文的评论...