首页 > 排队算法问题

排队算法问题

一个排队叫号系统中,所有的人都是竞争关系,如何保证公平,尽可能减少操作方面带来的优势(比如年龄大的人点鼠标速度比年轻人慢),但又不影响大家的竞争积极性(比如采用轮询方式一人一个)


简单讨论一下,不涉及具体的技术细节。

公平。只能做到一个尽可能接近的水平,但无法绝对公平。一般的做法,是初步分析影响公平的因子有哪些,然后将这些因子进行排序,赋以加权(一般可以采取层次分析法[AHP]),以期影响最后的排队。例如,你所谓的年龄大的人点鼠标的速度比年轻人慢这个考虑因素,实际上就可以归纳为年龄因子。至于实际上还有哪些考虑因素,这个就得靠系统设计的前期需求分析了。
竞争的积极性。一方面,只要是紧缺资源,不管你系统做的如何烂,都不太会影响积极性,例如马上进入春运后,我们的12306系统;另一方面,在某次交互长时间停滞时,需要有一个合适的手段以保证系统能够持续下去,这个目前常见的做法就是简单的丢弃。例如,你到医院排队叫号,叫到你面前,没有答应,医生就丢弃了,接着下一个呗。

综上所述,对于这类的排队算法问题,永远不要只埋头于算法的具体技术实现。往往实际的系统需求决定了算法的最终实现方案。
PS:个人觉得类似于医院排队叫号系统,在大家对公平没有一个统一的共识之前,目前已有的先来后到其实就是一种很好的公平算法了。当然,所谓的特权插队者,这是在哪个地方都有的,无解。

【热门文章】
【热门文章】