带权随机算法在游戏开发中应用广泛,最近在做商店随机商品又遇到这种问题,重新思考并总结了一下带权随机的做法.

带权随机其实很好理解
比如我们希望抽到A的抽到的比重是10,B的比重是5,C的比重是1,如下图
044TM313

权重和计算

常规做法是计算权重总和sum,然后在1到sum之间随机选择一个数R,之后遍历整个集合,统计遍历的项的权重之和,如果大于等于R,就停止遍历,选择遇到的项
好处:没有额外的空间占用,算法也比较简单。
坏处:选取的时候要遍历集合,时间复杂度是O(n)。

常规做法

math.randomseed(os.time())
function pick(rules, count)
local ret = {}
local total_weight = 0
for _, v in ipairs(rules) do
total_weight = total_weight + v.weight
end
for i=1, count do
local rd = math.random(total_weight)
for _, rule in ipairs(rules) do
if rd <= rule.weight then
table.insert(ret, rule.item)
break
else
rd = rd - rule.weight
end
end
end
return ret
end
function weight_unique_pick_one(rules, count)
local ret = {}
local function get_total_weight( rules )
local total_weight = 0
for _, v in ipairs(rules) do
total_weight = total_weight + v.weight
end
return total_weight
end
local total_weight =get_total_weight(rules)
for i=1, count do
local rd = math.random(total_weight)
for index, rule in ipairs(rules) do
if rd <= rule.weight then
table.insert(ret, rule.item)
table.remove(rules, index)
total_weight =get_total_weight(rules)
break
else
rd = rd - rule.weight
end
end
end
return ret
end
--test
local ret = weight_unique_pick_one({{item=1,weight=1},{item=2,weight=50},{item=3,weight=4},{item=4,weight=4},{item=5,weight=4},{item=6,weight=4},{item=7,weight=50},{item=8,weight=4}},4)
print("------------------")
for i,v in ipairs(ret) do
print(i,v)
end

按照权重排序优化

对项目集按照权重排序。这样遍历的时候,概率高的项排在前面,减少遍历的项。
比较{A:5,B:2,C:2,D:1}和{B:2,C:2,A:5,D:1}
前者遍历步数的期望是5/101+2/102+2/103+1/104而后者是2/101+2/102+5/103+1/104。
好处:提高了平均选取速度。
坏处:需要进行排序,并且不易添加删除修改项。

实现很简单将上面的weight_unique_pick_one方法中rules按字段weight做一个高到低排序就可以了

function weight_unique_pick_one(rules, count)
local ret = {}
table.sort(rules,function(a, b) return b.weight < a.weight end )
...
end

折半查找改进版本

折半查找的改进方法是将所有项的区间定义头尾,构造一个已排序的区间,然后用二分法加快查找random的区间

实现如下:

local function binsearch( t,value )
local i_start,i_end,i_mid = 1,#t,0
while i_start <= i_end do
i_mid = math.floor( (i_start+i_end)/2 )
local value2 = t[i_mid]
if value == value2 then
return i_mid
elseif value > value2 then
i_end = i_mid - 1
else
i_start = i_mid + 1
end
end
end
local function bisect_left( t,value )
local i_start,i_end,i_mid = 1,#t,0
while i_start < i_end do
i_mid = math.floor( (i_start+i_end)/2 )
local value2 = t[i_mid]
if value2 < value then
i_start = i_mid + 1
else
i_end = i_mid
end
end
return i_start
end
local function get_weight_interval( rules )
local total_weight = 0
local weight_interval = {}
for _, v in ipairs(rules) do
total_weight = total_weight + v.weight
table.insert(weight_interval,total_weight)
end
return total_weight,weight_interval
end
function weight_unique_pick(rules, count)
local ret = {}
local total_weight,weight_interval =get_weight_interval(rules)
for i=1, count do
local rd = math.random(total_weight)
local b_index = bisect_left(weight_interval,rd)
local item = rules[b_index]
table.insert(ret, item.item)
table.remove(rules, b_index)
total_weight,weight_interval =get_weight_interval(rules)
end
return ret
end
--test
local ret = weight_unique_pick({{item=1,weight=1},{item=2,weight=100},{item=3,weight=4},{item=4,weight=4},{item=5,weight=50}},3)
print("------------------")
for i,v in ipairs(ret) do
print(i,v)
end

纯算法实现

算法来源:
http://utopia.duth.gr/~pefraimi/research/data/2007EncOfAlg.pdf
参考:
http://kanglinxm.blogspot.jp/2013/10/blog-post.html

纯算法实现的关键实现:

for _,item in ipairs(rules) do
local u = math.random();
local w_i = 1 / item.weight;
local k = math.pow(u, w_i);
end

随机一个0-1之间的小数作为底数,将1/权重作为幂,权重越大,随机数相同时结果越大.将k由大到小排序取前count个即为要随机的个数.这种算法缺点是必须随机所有的项得到随机结果集.

完整实现:

function weight_unique_math(rules, count)
local ret = {}
local all_random_weight = {}
for _,item in ipairs(rules) do
local u = math.random();
local w_i = 1 / item.weight;
local k = math.pow(u, w_i);
table.insert(all_random_weight,{item =item.item,random_weight = k})
end
table.sort(all_random_weight,function(a, b) return b.random_weight < a.random_weight end )
for i=1,count do
local item = all_random_weight[i].item
table.insert(ret,item)
end
return ret
end
local items = {{item=1,weight=1},{item=2,weight=50},{item=3,weight=4},{item=4,weight=4},{item=5,weight=4},{item=6,weight=4},{item=7,weight=50},{item=8,weight=4}}
local ret = weight_unique_math(items,3)
for i,v in ipairs(ret) do
print(i,v)
end