用 Erlang 实现彩票算法

[erlang]

我们需要解决的问题是 -- 选择一个最好的客服代表为客户服务,又不失公平。

首先,我们有一个数组列出了所有的客服代表,以及他们的积分(score)。当然,该积分根据客服代表的历史表现评定的。服务越好的客户代码积分越高。

要解决该问题,有一个著名和算法称为“彩票算法”。它的基本原理是,根据每个人的积分发放彩票,积分高的人得到的彩票数量就多,如果每张彩票中奖的概率是相等的,那么在一轮选择中,显然积分越高的人会有更高的概率赢得客户(中奖),而在 N 轮选择中,积分越高的人赢得的客户就越多。

说得再具体一点,假设有三个客服代表,A1、A2和A3,他们的积分分别是 6、3、1。则第一个客户到来时,A1最有可能赢得这个客户。当然,也不一定,因为我们这里的算法是基于概率的,也可能该客户让A3获得了,称为优先级反转。不过,无法如何,如果有10个客户到来时,我们希望他们分得的客户分别是6、3、1。

算法的实现,我们把上面的例子说得再通用一点,假设A1、A2、A3分别持有彩票a1、a2、a3,那么彩票的总数就是 a1 + a2 + a3 = N,他们分别持有的彩票号码如下图:

| A1 | A2 | A3 |
| 1, 2 .. a1 | a1+1, a1 + 2 .... a1 + a2 | a1+a2+1..... a1+a2+a3=N|

那么我们如何决定谁中奖呢?首先,我们需要确定一个中奖号码,从 1 到 N 中取一个随机数,把该数作为中奖号码。具体代码如下:

who_win_the_lottery([], TotalLotterys, _LotteryNumber) -> no_winner; who_win_the_lottery([{Agent, Lotteries} | Agents], TotalLotteries, LotteryNumber) ->

% Note: List of {Agent, Lotteries} pairs already in reverse order

RestLotteries = TotalLotteries - Lotteries,
case LotteryNumber > RestLotteries of
    true -> Agent;  % congratulations! you win!
    false ->
        who_win_the_lottery(Agents, RestLotteries, LotteryNumber)
end.

思路是,给定一个列表,从最后一个客服代表开始算,如果中奖号码不在最后一个人手中,则往前查找一个,直至找到中奖号码。算法中,根据“等概率”的特性,列表中客服代表的排列顺序是无关的,但为了与上面图中给出的顺序统一,可以先将列表翻转 (lists:reverse),下面代码先生成一张中奖彩票 LotteryNumber,然后判断谁中奖。

decide_winner() ->

LotteryNumber = case TotalLotteries of
    0 -> 1;  % avoid random:uniform(0) generate exceptions
    _ -> random:uniform(TotalLotteries)
end,

io:format("LotteryNumber: ~p~n", [LotteryNumber]),

    AgentList = [{agent1, 6}, {agent2, 3}, {agent3, 1}],
    TotalLotteries = 10,

    % lists:revert(AgentList)

Winner = who_win_the_lottery(AgentList, TotalLotteries, LotteryNumber),
io:format("Winner: ~p~n", [Winner]),
Winner.

需要指出,这种基本概率的算法是不可靠的,也就是说根据上面的数据,在10次实验中我们期望获得 6、3、1,但实际可能是5、3、2。如果数据量比较大,结果就比较相近了。

七歌
微信扫一扫