12306选座算法分析和应用

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

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

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

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

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

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

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

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

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

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

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

• 情况A：

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

• 情况B：

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

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

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

• 情况C：

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

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

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

• 情况D：

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

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

• 情况F：

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

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

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

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

---