由铁路售票想起

候车的时候想了个问题.

其实列车售票是一个segment的allocation问题.

给定一条线路{s_0,s_1,...,s_n}.
一个从A->B的请求实际上是某个{[s_i,s_j]; 0<=i 且每一个s_i有对应的一个quota,q_i表示可allocate的数量.

那么一个naive的approach就是做一个atomic的能rollback的transaction,做一个decrease.
这样的话,在q_i <<< concurrent_request,远小于并发请求数的时候.
在给定collision分布的情况下,某些q_i就不停地<0导致transaction rollback,从而造成一个failed allocation.

考虑一个稍微简单的定义.
给定一个sequence或者whatever,{s_i;s_i=0 or s_i=1}
也就是这个离散连续区间的值为0或者1.
或者说,这条线路各站余票只有0或者1两种情况.

对于一个allocation request,a_i_j,则要求的是.
sum_i_j s_i = j-i+1,即使i,j区间均为1.

而一组concurrent request则可以认为给定一组a,求一个satisfied的allocation subset.

这个有点类似有冲突的广告bid.
或者所谓的背包算法还是什么?

考虑optimized的目标是让是个subset尽可能地大.
或者说有尽可能多的request被满足.

那么这个最优解怎么求呢.

从最大或者最小的span开始allocate是不行的.
因为很容易构造一个反例,使人如果这个最优解存在,这种策略是不work的.

考虑对non-overlay的span一次allocation.
这是一个not necessary optimal的solution.
因为没有conflict.

考虑这个allocation set中的某个请求r,存在另一个range conflict的请求r_c.

当r_c的span是r的一个子集的时候,用r_c替换r是可以improve的.
因为此时r_c release原来r range的某些slot.
这使得这些slot有可能被更多的请求allocate到,从而增大了allocation set.

如果反过来的r_c是r的一个super set的话,那么同理,是不能improve的.

考虑只是partial overlay的情况.

令L_r为r的长度,L_r_c为r_c的长度.

那么在把r剔除之后的空出来的长度L至少会是L_r + L_r_c - 1.
不然的话,r和r_c能够同时fill整个range,不会有overlay.

于是对于r的improve就递归为这个L区间的optimal solution了.

则当最终converge的时候,也就是对于当前solution的所有r,都找不到任何improve的时候.

这个是最优解么?
还是说只是一个local minimal?

应该说只是一个local minimal.
因为本质上这是个step one的back search.
存在且容易构造如果回退两步能fill 3个request的情况.

而回退两步能产生更优解的原因应该是在于有了更多的continual的space.

所以可能first fill的时候,应该以保持尽可地避免fragment?

于是理想的做法应该是优先给予线路两侧的短途?