l*****f
发帖数: 2198 | 1 大神能否帮我看看是否合理或挑出毛病？轻拍哦
这个算法不是基于总票量，也不用管每一站，而是完全基于座位。
假如一趟列车有6个站，那么一共就有5个小段，A-B,B-C,C-D,D-E，E-F
存成矩阵形式就是 [0,0,0,0,0] (0代表目前available）。
假如一个用户买一张票，从A坐到C，那么矩阵变成[1,1,0,0,0]
假如一趟车有1000个座位（假设8节硬座，每节125个座位）
那么初始矩阵就是1000行，5列，所有元素都为0。
用户购票时，首先根据行程确定需要在哪几个站有座位。假如有一个用户需要从B买到D
，那么意味着一行矩阵的2，3列元素必须是0.于是乎，程序从第一个座位（矩阵第一行
）开始寻找哪一行的第2,3个元素均为0. 如果找得到，则售出此座位，把那行矩阵的2
，3元素变成1 （即B-C,C-D段unavailable).如果找不到，则显示无票。
这个方案也解决了中途有人下车，座位继续出售的问题。比如，上面那个例子如果先前
有个乘客从A坐到B，则系统会自动把B站以后的票卖给别人。（因为这个乘客买票的时
候，只是把第一个元素变成1，其他四段仍然available).
我目前想到的优缺点：
优点：
1.火车就那么多班次（全国大概1000个班次吧），每个班次也就一两千个座位，所以运
算量大大减轻。也最大程度节省了网络资源。
2. 快，搜索一遍1000行的矩阵几乎是一瞬间的事情
缺点：
1. 目前暂未考虑到无座票的问题。 | n****1
发帖数: 1136 | 2 首先, 这个是最直观的data model, 随便什么人来设计, 能想到的最简单的就是这个了.
其次, 你的data model里面, 不同车次的矩阵长度不一样,可能会带来麻烦. 譬如G1从
武汉到北京, G2从广州到北京, 乘客要买武汉到石家庄的, 这样就要去(G1, G2, ...)N
个不同长度的矩阵里查余票, 而且"武汉/石家庄"在N个矩阵里的列位还不一样. | n*****t
发帖数: 22014 | 3 所以我说这玩意要整 ASIC，一个 chip 管一个车次
了.
)N
【在 n****1 的大作中提到】
: 首先, 这个是最直观的data model, 随便什么人来设计, 能想到的最简单的就是这个了.
: 其次, 你的data model里面, 不同车次的矩阵长度不一样,可能会带来麻烦. 譬如G1从
: 武汉到北京, G2从广州到北京, 乘客要买武汉到石家庄的, 这样就要去(G1, G2, ...)N
: 个不同长度的矩阵里查余票, 而且"武汉/石家庄"在N个矩阵里的列位还不一样.
| b***2
发帖数: 3 | 4 我个人感觉问题是如果某一个用户买票的时候，是否需要锁住整个矩阵？
感觉算法本身挺好的。。 |
|
