SteemIt 通过回溯算法确定更好的点赞策略 (高级版)

上回说到点赞策略,但我们并不确定是否有更好的投票策略,或者说,已经有的几种方法已经是相当好的了.我们来回顾一下:

• 第一种方法:不管三七二十一,直接最开始一并点完.
• 第二种方法:在睡觉前点完(等SP能量恢复到最大值).
• 第三种方法:每次点赞间隔等时间来点.

我们通过Javascript程序模拟出收益情况发现:如果起始能量很接近格满,比如大于90%,那么选着第三种方式,否则选第二种. 那么我们这篇帖子需要看看能否搜索出最大收益的点赞方法.

由于点赞方式的搜索空间较大,所以我们缩小一下范围.我们假设:一天点4次(T=4),在N=4 小时内点完.M还是270美元(100%能量点赞的收益)

我们先定义一个点赞方案的数组, 值表示为离时间段开始的分钟偏移:

1
2
3
4

var sol = Array();
for (var i = 0; i < T; ++ i) {
    sol[i] = 0;
}

var sol = Array();
for (var i = 0; i < T; ++ i) {
    sol[i] = 0;
}

比如:

1

sol = [1, 2, 3, 4, 5, 6, 7, 8];

sol = [1, 2, 3, 4, 5, 6, 7, 8];

表示为每隔1分钟点1次,一共点8次,上面的JS代码初始方案数组为0,也就是说统统在开始点完.

然后我们需要定义两个变量,一个是找到的最大方案数,另一个是最大收益值:初始化为:

1
2

var bestSol = sol.slice(0);
var bestScore = 0;

var bestSol = sol.slice(0);
var bestScore = 0;

找到较优值后我们需要打印方案:

1
2
3
4
5
6
7

function print(sol) {
    var s = "";
    for (var i = 0; i < T; ++ i) {
        s += sol[i] + ", ";
    }
    console.log(s);
}

function print(sol) {
    var s = "";
    for (var i = 0; i < T; ++ i) {
        s += sol[i] + ", ";
    }
    console.log(s);
}

然后我们需要评估一种方案的收益情况,这时候按分钟来回能量 (每分钟回 0.005/36 能量):

1
2
3
4
5
6
7
8
9
10
11
12

function eval(sol, P, M, T, N) {
    var sp_restored = 0.005 / 36;
    P = Math.min(1, P + sp_restored * (sol[0])); // Max = 100% 
    var x = 0;
    sol[T] = sol[T - 1]; //  Avoid out of range access for sol[i+1]
    for (var i = 0; i < T; ++ i) {
        x += P * M;  // Accumulate Payout 
        P -= 0.02;    // 2% loss
        P += sp_restored * (sol[i + 1] - sol[i]); // SP restores before next vote 
    }
    return x;       
}

function eval(sol, P, M, T, N) {
    var sp_restored = 0.005 / 36;
    P = Math.min(1, P + sp_restored * (sol[0])); // Max = 100% 
    var x = 0;
    sol[T] = sol[T - 1]; //  Avoid out of range access for sol[i+1]
    for (var i = 0; i < T; ++ i) {
        x += P * M;  // Accumulate Payout 
        P -= 0.02;    // 2% loss
        P += sp_restored * (sol[i + 1] - sol[i]); // SP restores before next vote 
    }
    return x;       
}

然后最牛逼的来了,就是搜索.我们这里假设点赞间隔为15分钟(除非到达最后时间点),否则搜索空间很大,效率很低.回溯算法的精髓就是:一棵搜索树,能往下走往下走,走到最底再往树的兄弟结点扩展,扩展完退一步(回溯)到上一层,至到第一层节点访问完.

由于这里没有剪枝的优化,也就是说,我在t分钟的时候点了第一次赞,我第二次赞可以在t, t+1, t+2至到时间结束再点第二次.点赞次数T越大,搜索树的深度就越大(搜索树的深度等于T),搜索树的宽度为 N*60,因为如果每次点赞都是一个时间点,而这个时间点按分钟来划分的话一共有N*60种情况.

这样的话,穷举搜索时间复杂度就是 (N*60)^T 当 N和T都很大的时候穷举无法快速的计算得到结果.而回溯的搜索空间为:C_(N*60)^T 理解为从 60N中取出T个的组合

回溯算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

function search(sol, left, n, T, right) {
    if (n == T) { // when we reach the tree leaves
        var score = eval(sol, P, M, T, N);  // need to evaluate this solution 
        if (score > bestScore) {  // found a better solution?
                bestScore = score;
                bestSol = sol.slice(0);
            }
            return; 
    }
    for (var i = left; i <= right; ++ i) {
        sol[n] = i;  // The n-th vote is placed at time 
        search(sol, Math.min(right, i + 15), n + 1, T, right); // try next vote 
    }
}

function search(sol, left, n, T, right) {
    if (n == T) { // when we reach the tree leaves
        var score = eval(sol, P, M, T, N);  // need to evaluate this solution 
        if (score > bestScore) {  // found a better solution?
                bestScore = score;
                bestSol = sol.slice(0);
            }
            return; 
    }
    for (var i = left; i <= right; ++ i) {
        sol[n] = i;  // The n-th vote is placed at time 
        search(sol, Math.min(right, i + 15), n + 1, T, right); // try next vote 
    }
}

用 Node.Js + sublime text3 跑跑 来看看结果:

当P=0.99的时候:

calcPayout0 =  1036.8
calcPayout1 =  1047.6
calcPayout2 =  1054.8
calcPayout3 =  1066.5
72, 240, 240, 240, 

能量满的时候 第一次在第72分钟的时候点,剩下3次再最后的时间点,能比第三种方案多挣12美元!

当P=0.8的时候:

calcPayout0 =  831.5999999999999
calcPayout1 =  867.5999999999999
calcPayout2 =  849.5999999999999
calcPayout3 =  867.5999999999999
240, 240, 240, 240

能量不高的时候,最优的方案就是在最后面的时间一块点完.

当P=1 全满的时候:

calcPayout0 =  1047.6
calcPayout1 =  1047.6
calcPayout2 =  1065.6
calcPayout3 =  1074.6000000000001
0, 240, 240, 240, 

起床的时候点一次,剩下3次在睡觉前点.这种问题在计算机领域称为 NP-hard, 也就是目前除了暴力搜索+剪枝+回溯 等优化技巧并没有太有效的算法.在WIKi里这样描述NP-困难:

NP困难(NP-hard,non-deterministic polynomial-time hard)问题是计算复杂性理论中最重要的复杂性类之一.某个问题>被称作NP困难,当所有NP问题可以在多项式时间图灵归约到这个问题.
因为NP困难问题未必可以在多项式的时间内验证一个解的正确性(即不一定是NP问题),因此即使NP完全问题有多项>式时间内的解(若P=NP),NP困难问题依然可能没有多项式时间内的解.因此NP困难问题”至少与NPC问题一样难”.

好吧:这篇文章的初步结论就是:当起始能量很靠近满格的时候,不妨可以试着在最开始点第一次, 剩下的在时间最后面点完.至于这是不是最优解,很难说.因为,别忘记了,我们这里外加了一个中间点赞时间间隔15分钟的限制.

英文: A Better SteemIt Voting Strategy with Back Tracking Algorithm