algorithm - 加权项目算法

Question

我想学习如何选择加权项。例如:我想从题库中取题，但如果有人不能给出正确的答案，这会导致这个问题的权重增加一倍，并增加以后再次被选中的可能性。

Answer 1

有一个类将 item:weight 对 (key=item:value=weight) 保存在哈希表中。

该类还应维护一个 total_weight变量，它是哈希表中所有权重的总和。类的方法 add_item , remove_item , 和 update_weight对于一个项目应该保持 total_weight 更新。这避免了为每个选择重新计算总数。

要选择一个项目: 使用一个随机数使得 1<=random_number<=total_weight . 遍历哈希表中的 item:weight 对，对权重求和，直到随机数 <= 运行总和。当发生这种情况时，您所在的配对的 key 就是所选项目。

这就像掷一个假想的骰子，其大小是所有重量的总和。对于每一卷，每个项目在骰子上都有自己的数字范围，每个范围的大小等于其项目的重量。如果掷骰结果落在某个项目的范围内，则该项目就是所选项目。

编辑以在下面评论中的请求后添加以下示例代码。使用 Python 2.5.2 对此进行了测试:

from random import randint  # Import randint function from random module.

class WeightedCollection(object):
    def __init__(self):
        self.total_weight = 0
        self.items = {}  # This is a python dictionary == a hash table
    def add_item(self, item, weight):
        self.items[item] = weight
        self.total_weight += weight
    def remove_item(self, item):
        self.total_weight -= self.items[item]  # Subtracts the weight.
        del(self.items[item])
    def update_weight(self, item, new_weight):
        self.total_weight += (new_weight - self.items[item])
        self.items[item] = new_weight
    def get_random_item(self):
        ''' Returns random selection but weighted by item weights. '''
        # Result of call below is 1 <= random_number <= self.total_weight...
        random_number = randint(1, self.total_weight)
        sum_so_far = 0
        # For every item and its weight...
        for item, weight in self.items.iteritems():
            sum_so_far += weight
            if random_number <= sum_so_far:
                return item

# Usage demo...

questions = WeightedCollection()

questions.add_item('What is your name?', 1)
questions.add_item('What is your favorite color?', 50)
questions.add_item('What is the meaning to life?', 100)

print 'Here is what the dictionary looks like:'
print questions.items
print ''
print "Total weight:", questions.total_weight
print ''
print 'Some sample random picks...'
for i in range(5):
    print questions.get_random_item()

这是输出:

Here is what the dictionary looks like:
{'What is the meaning to life?': 100, 'What is your name?': 1, 'What is your favorite color?': 50}

Total weight: 151

Some sample random picks...
What is your favorite color?
What is the meaning to life?
What is the meaning to life?
What is your favorite color?
What is the meaning to life?