加权随机算法：按权重控制的概率选择机制

如何让稀有物品掉落率低、普通物品掉落率高？加权随机算法提供了完美的概率控制方案。

问题背景

在很多应用场景中，我们需要按照预设的概率分布来进行随机选择，而不是简单的均匀随机：

• 游戏开发：稀有装备1%概率，普通装备50%概率
• 推荐系统：热门商品推荐概率高，冷门商品概率低
• 负载均衡：高性能服务器分配更多请求
• 广告投放：高价值广告展示频率更高
• 抽奖活动：一等奖概率0.1%，参与奖概率90%

简单随机选择无法满足这些需求，而加权随机(Weighted Random) 算法提供了完美的解决方案。

算法原理

加权随机核心思想是：根据权重构建概率区间，随机数落在哪个区间就选择对应的元素。

基本概念

假设我们有三个物品和对应的权重：

物品A: 权重 5
物品B: 权重 3  
物品C: 权重 2

总权重 = 5 + 3 + 2 = 10

每个物品的概率分布：

物品A: 5/10 = 50%
物品B: 3/10 = 30%
物品C: 2/10 = 20%

实现方法

方法一：线性扫描（简单直观）

<?php

class WeightedRandom {
    
    /**
     * 线性扫描实现加权随机
     * 
     * @param array $items 格式：['物品A' => 权重, '物品B' => 权重, ...]
     * @return mixed 随机选中的物品
     */
    public static function linearSelect($items) {
        // 计算总权重
        $totalWeight = array_sum($items);
        
        // 生成随机数
        $random = mt_rand(1, $totalWeight);
        
        // 线性扫描找到对应的物品
        $current = 0;
        foreach ($items as $item => $weight) {
            $current += $weight;
            if ($random <= $current) {
                return $item;
            }
        }
        
        return null; // 理论上不会执行到这里
    }
}

// 使用示例：游戏物品掉落
$lootTable = [
    '普通药水' => 50,   // 50% 概率
    '稀有装备' => 30,   // 30% 概率  
    '传奇武器' => 15,   // 15% 概率
    '神器'     => 5     // 5% 概率
];

echo "=== 游戏物品掉落模拟 ===\n";
for ($i = 0; $i < 10; $i++) {
    $loot = WeightedRandom::linearSelect($lootTable);
    echo "第 " . ($i + 1) . " 次掉落: " . $loot . "\n";
}

?>

方法二：别名方法（高效算法）

对于需要频繁抽样的大规模场景，可以使用更高效的别名方法：

<?php

class AliasMethod {
    private $prob;
    private $alias;
    private $n;
    
    /**
     * 初始化别名表
     * 
     * @param array $weights 权重数组
     */
    public function __construct($weights) {
        $this->n = count($weights);
        $this->prob = array_fill(0, $this->n, 0);
        $this->alias = array_fill(0, $this->n, 0);
        
        $this->buildAliasTable($weights);
    }
    
    /**
     * 构建别名表
     */
    private function buildAliasTable($weights) {
        $total = array_sum($weights);
        $prob = array_map(function($w) use ($total) {
            return $w * $this->n / $total;
        }, $weights);
        
        $small = [];
        $large = [];
        
        // 分类
        for ($i = 0; $i < $this->n; $i++) {
            if ($prob[$i] < 1) {
                $small[] = $i;
            } else {
                $large[] = $i;
            }
        }
        
        // 构建别名表
        while (!empty($small) && !empty($large)) {
            $s = array_pop($small);
            $l = array_pop($large);
            
            $this->prob[$s] = $prob[$s];
            $this->alias[$s] = $l;
            
            $prob[$l] = ($prob[$l] + $prob[$s]) - 1;
            
            if ($prob[$l] < 1) {
                $small[] = $l;
            } else {
                $large[] = $l;
            }
        }
        
        // 处理剩余项
        while (!empty($large)) {
            $l = array_pop($large);
            $this->prob[$l] = 1;
        }
        
        while (!empty($small)) {
            $s = array_pop($small);
            $this->prob[$s] = 1;
        }
    }
    
    /**
     * 生成随机选择
     */
    public function next() {
        $i = mt_rand(0, $this->n - 1);
        if (mt_rand() / mt_getrandmax() < $this->prob[$i]) {
            return $i;
        } else {
            return $this->alias[$i];
        }
    }
}

// 使用别名方法的加权随机类
class EfficientWeightedRandom {
    
    /**
     * 使用别名方法实现高效加权随机
     */
    public static function aliasSelect($items) {
        static $aliasMethods = [];
        
        $key = md5(serialize($items));
        if (!isset($aliasMethods[$key])) {
            $aliasMethods[$key] = new AliasMethod(array_values($items));
        }
        
        $index = $aliasMethods[$key]->next();
        $itemNames = array_keys($items);
        return $itemNames[$index];
    }
}

?>

方法三：二分查找（性能均衡）

<?php

class BinarySearchWeightedRandom {
    private $prefixSums;
    private $items;
    private $totalWeight;
    
    /**
     * 预处理前缀和数组
     */
    public function __construct($items) {
        $this->items = array_keys($items);
        $this->totalWeight = array_sum($items);
        
        // 构建前缀和数组
        $this->prefixSums = [];
        $sum = 0;
        foreach ($items as $weight) {
            $sum += $weight;
            $this->prefixSums[] = $sum;
        }
    }
    
    /**
     * 二分查找实现快速选择
     */
    public function select() {
        $target = mt_rand(1, $this->totalWeight);
        
        // 二分查找
        $left = 0;
        $right = count($this->prefixSums) - 1;
        
        while ($left < $right) {
            $mid = $left + intval(($right - $left) / 2);
            
            if ($this->prefixSums[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid;
            }
        }
        
        return $this->items[$left];
    }
}

?>

完整应用示例

<?php

// 完整的加权随机应用示例
class WeightedRandomApplication {
    
    /**
     * 游戏掉落系统
     */
    public static function gameLootSystem() {
        echo "=== 游戏掉落系统 ===\n";
        
        $monsterLootTable = [
            '金币' => 400,
            '普通装备' => 300,
            '稀有装备' => 200,
            '史诗装备' => 80,
            '传奇装备' => 18,
            '神器' => 2
        ];
        
        // 模拟击杀怪物掉落
        $drops = [];
        for ($i = 0; $i < 1000; $i++) {
            $loot = WeightedRandom::linearSelect($monsterLootTable);
            if (!isset($drops[$loot])) {
                $drops[$loot] = 0;
            }
            $drops[$loot]++;
        }
        
        // 统计结果
        echo "1000次击杀掉落统计:\n";
        foreach ($drops as $item => $count) {
            $rate = ($count / 1000) * 100;
            $expected = ($monsterLootTable[$item] / array_sum($monsterLootTable)) * 100;
            echo sprintf("%-10s: 实际%.2f%% (预期%.2f%%)\n", 
                $item, $rate, $expected);
        }
    }
    
    /**
     * 推荐系统
     */
    public static function recommendationSystem() {
        echo "\n=== 商品推荐系统 ===\n";
        
        $products = [
            '热门商品A' => 100,
            '热门商品B' => 80,
            '普通商品C' => 30,
            '普通商品D' => 25,
            '冷门商品E' => 10,
            '新品F' => 5
        ];
        
        echo "今日推荐商品:\n";
        for ($i = 0; $i < 5; $i++) {
            $recommended = WeightedRandom::linearSelect($products);
            echo "推荐位 " . ($i + 1) . ": " . $recommended . "\n";
        }
    }
    
    /**
     * 抽奖活动
     */
    public static function lotterySystem() {
        echo "\n=== 抽奖活动系统 ===\n";
        
        $prizes = [
            '一等奖：iPhone' => 1,
            '二等奖：AirPods' => 5, 
            '三等奖：优惠券' => 50,
            '参与奖：谢谢参与' => 944
        ];
        
        echo "抽奖结果:\n";
        $results = [];
        for ($i = 0; $i < 100; $i++) {
            $prize = WeightedRandom::linearSelect($prizes);
            if (!isset($results[$prize])) {
                $results[$prize] = 0;
            }
            $results[$prize]++;
        }
        
        foreach ($results as $prize => $count) {
            echo $prize . ": " . $count . "次\n";
        }
    }
    
    /**
     * 性能测试
     */
    public static function performanceTest() {
        echo "\n=== 性能测试 ===\n";
        
        // 大规模权重表
        $largeWeightTable = [];
        for ($i = 0; $i < 1000; $i++) {
            $largeWeightTable["item_$i"] = mt_rand(1, 100);
        }
        
        // 线性扫描性能
        $start = microtime(true);
        for ($i = 0; $i < 10000; $i++) {
            WeightedRandom::linearSelect($largeWeightTable);
        }
        $linearTime = microtime(true) - $start;
        
        // 二分查找性能
        $bsRandom = new BinarySearchWeightedRandom($largeWeightTable);
        $start = microtime(true);
        for ($i = 0; $i < 10000; $i++) {
            $bsRandom->select();
        }
        $binaryTime = microtime(true) - $start;
        
        echo "线性扫描: " . number_format($linearTime, 4) . " 秒\n";
        echo "二分查找: " . number_format($binaryTime, 4) . " 秒\n";
        echo "性能提升: " . number_format(($linearTime - $binaryTime) / $linearTime * 100, 2) . "%\n";
    }
}

// 运行所有示例
WeightedRandomApplication::gameLootSystem();
WeightedRandomApplication::recommendationSystem();
WeightedRandomApplication::lotterySystem();
WeightedRandomApplication::performanceTest();

?>

算法对比

方法	时间复杂度	空间复杂度	适用场景
线性扫描	O(n)	O(1)	权重项少，简单应用
二分查找	O(log n)	O(n)	权重项多，性能要求高
别名方法	O(1)	O(n)	超大规模，频繁抽样

最佳实践建议

1. 权重设计原则

// 好的权重设计
$goodWeights = [
    '常见物品' => 70,   // 70%
    '稀有物品' => 25,   // 25%  
    '史诗物品' => 4,    // 4%
    '传说物品' => 1     // 1%
];

// 避免的权重设计
$badWeights = [
    '物品A' => 0.0001,  // 概率过小，可能永远选不到
    '物品B' => 999999,  // 权重差异过大
];

2. 动态权重调整

class DynamicWeightedRandom {
    private $baseWeights;
    private $dynamicFactors;
    
    public function __construct($baseWeights) {
        $this->baseWeights = $baseWeights;
        $this->dynamicFactors = array_fill_keys(array_keys($baseWeights), 1);
    }
    
    /**
     * 根据用户行为动态调整权重
     */
    public function adjustWeight($item, $factor) {
        if (isset($this->dynamicFactors[$item])) {
            $this->dynamicFactors[$item] *= $factor;
        }
    }
    
    /**
     * 获取当前动态权重
     */
    public function getCurrentWeights() {
        $current = [];
        foreach ($this->baseWeights as $item => $weight) {
            $current[$item] = $weight * $this->dynamicFactors[$item];
        }
        return $current;
    }
    
    /**
     * 基于动态权重的选择
     */
    public function select() {
        $currentWeights = $this->getCurrentWeights();
        return WeightedRandom::linearSelect($currentWeights);
    }
}

总结

加权随机算法是概率控制的重要工具，具有以下特点：

核心优势

1. 精确控制概率：严格按照权重分配选择概率
2. 灵活配置：支持动态调整权重
3. 性能可控：多种实现满足不同性能需求
4. 应用广泛：适用于游戏、推荐、抽奖等场景

选择建议

• 小规模数据：使用线性扫描，简单直观
• 大规模数据：使用二分查找，性能均衡
• 超频繁抽样：使用别名方法，极致性能

加权随机算法让概率控制变得简单而精确，是每个开发者都应该掌握的重要算法工具。