机票分享第三篇 机票计算过程及时间复杂度(国际篇)

  1. 云栖社区>
  2. 博客>
  3. 正文

机票分享第三篇 机票计算过程及时间复杂度(国际篇)

詹姆 2018-07-15 13:14:56 浏览878
展开阅读全文

延续上篇国内机票计算的话题,依然聚焦机票计算层,扩大范畴到国际。国际机票的区别在于会做更多的拼接,若所有数据全部参与计算则耗时过长,需要挑选一部分,还要保证挑选的部分恰好对应最低的价格。国际机票的有趣之处在于决定怎么挑。


一、国际机票单程

1、由于多数情形需要中转,不再适用运价*座位*规则的笛卡尔积

座位对应的航班组合比较多,如果沿用笛卡尔积,则花费时间的放大倍数与平均航班组合数相当

24b09bfdcda08e80b5983038f19dbd292a5b22cd

示例:两段的中转

2、挑选部分规则来降低匹配次数

(1)、将运价与航班组合按运价分组

3e53cb620172c377f3070bcc4a8348afbcadd009

(2)、用运价与规则匹配并计算价格,从而对规则排序

3918270061e5cbf8bc6cc3309fe311ac2510feff

(3)、将运价与航班组合,从排序后的规则里挑选部分,来生成票价

0ac0046fecf8af318610ff2a37d6c3084338ee5b

注:stop条件并非实际场景,eg.算出一个便stop;一个商家只算一个价格


二、国际机票往返

1、与国内不同,两个运价拼接往返运价的模式为常态

c6b0ac76e0d1e94476bb8bb4dc50893f84bc3e0a

国内的往返运价通常是已经组合好的,而国际的场景是设置一个运价是否适用于去程/回程,并动态去组合的。

2、拼接将时间复杂度放大到n2

国内往返运价、规则是拼好的,仅航班需要拼接,延用笛卡尔积方式还能接受

国际运价、航班、规则都需要拼接,都放大为n2,很可怕

3、挑选部分运价、航班、规则来降低匹配次数

(1)、对运价的挑选:只保留低于同航司运价组合价格的混航司运价组合;对航班的初筛:至少与一个去程运价匹配的航班才放入去程航班集合,至少与一个返程运价匹配的航班才放入返程航班集合

(2)、从排序后的运价、排序后的航班里挑选一些匹配生成运价与航班组合

e91b35fb8d069f703ae1d2c4749d67764a958076

注:图例的stop条件为算出一个航班便停止,实际模型更复杂一些

(3)、挑选部分规则与运价航班组合匹配(和国际单程类似,不再赘述)


三、国际机票多程

1、两程采用和往返同样的计算方式

2、大于两程,则采取多次查询两程的计算结果,并拼接


四、解决时间复杂度放大问题的思路

1、预筛选,来降低数量

2、分组,用匹配分组取代匹配单个元素,从而降维

3、排序,便于后面的挑选

4、按顺序做匹配,达到一定条件就stop


网友评论

登录后评论
0/500
评论
詹姆
+ 关注