Задача следующая. Есть M клиентов, готовых платить бабло за каждый показ на рекламной площадке. Рекламная площадка представляет из себя список мест от 1 до k>=5. Чем больше клиент платит за показ, тем выше его вероятность оказаться на первом месте.
Требуется расписать клиенту таблицу вероятностей для первых 5 мест. В первой строчке информация о самом клиенте с его ставкой, далее идут 4 строки с конкурентами по убыванию вероятностей для первого места и далее строка со "всеми остальными". Поскольку мест для расчета немного, решил для каждого места реализовать свой алгоритм.
Для первого места все просто: P1(x) = x / sum(Xi), где i = 1..M
Для второго места сложнее: P2(x) = Sum( P1(Xi) * (x / sum(Xj)) ), где i = 1..M, кроме позиции x; j = 1..M при j != i.
Иначе говоря, суммируем произведения вероятностей показа каждого объекта на первом месте, кроме x и вероятностей показа на втором месте без учета уже показанного на первом (звучит ужасно!).
Для третьего места еще сложнее: P3(x) = Sum ( P1(Xi)*P2(Xj)* (x / sum(Xk)) ), где i=1..M, кроме позиции x; j = 1..M, кроме позиции x и j != i; k = 1..M, при k != i и k != j.
Далее я расписал на бумаге подробные формулы для 4, 5 и 6 объектов, упростил их и реализовал соответствующие алгоритмы. Считаю алгоритмы работающими, если, как минимум, возвращаемые ими вероятности для данного места в сумме дают 1.
Для первого и второго случая все работает корректно, а в третьем стабильно не хватает до единицы от 0.2 до 0.3.
Вот готовая программа на PHP:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
#!/usr/bin/php
<?php
error_reporting(E_ALL);
$in_out[ 0 ] = array(
5 , 10 , 15 , 20
);
TV1(&$in_out);
TV2(&$in_out);
TV3(&$in_out);
//print_r($in_out);
function TV1 (&$in_out)
{
$sum = array_sum($in_out[ 0 ]);
foreach ($in_out[ 0 ] as $k => $v)
$in_out[ 1 ][$k] = $v / $sum;
}
function TV2(&$in_out)
{
// Init divisors once
$divs = array();
$cnt = count($in_out[ 0 ]);
for ($i = 0 ; $i < $cnt; $i++)
{
$buf = $in_out[ 0 ];
array_splice(&$buf, $i, 1 );
$divs[$i] = array_sum($buf);
}
// Calculates chances
for ($i = 0 ; $i < $cnt; $i++)
{
$in_out[ 2 ][$i] = 0 ;
foreach ($in_out[ 0 ] as $k => $v) {
if ($k == $i)
continue;
$in_out[ 2 ][$i] += $in_out[ 1 ][$k] * $in_out[ 0 ][$i] / $divs[$k];
}
}
}
function TV3(&$in_out)
{
// Init factors once
$factors = array();
$cnt = count($in_out[ 0 ]);
for ($i = 0 ; $i < $cnt - 1 ; $i++)
{
for ($j = $i + 1 ; $j < $cnt; $j++)
{
$buf = $in_out[ 0 ];
// Keep this order - first $j, next $i!
array_splice(&$buf, $j, 1 );
array_splice(&$buf, $i, 1 );
$factors[$i.$j] = ($in_out[ 1 ][$i]*$in_out[ 2 ][$j] + $in_out[ 1 ][$j]*$in_out[ 2 ][$i]) / array_sum($buf);
echo "$i$j\n";
}
}
$keys = array_keys($factors);
for ($i = 0 ; $i < $cnt; $i++)
{
$sum = 0 ;
foreach ($keys as $v) {
$v = (string) $v;
if ($v{ 0 } == $i || $v{ 1 } == $i)
continue;
$sum += $factors[$v];
echo 'a';
}
$in_out[ 3 ][$i] = $in_out[ 0 ][$i] * $sum;
echo "\n";
}
}
?>
Алгоритм много раз трассировал на соответствие математическим выкладкам - все работает корректно.
