c - 蛮力算法的优化还是替代？

Question

我有一个简单的(强力)递归求解器算法，它需要花费大量时间来获得更大的 OpxCnt 变量值。对于较小的 OpxCnt 值，没问题，效果很好。随着 OpxCnt 变量变大，算法变得非常慢。这是意料之中的，但任何优化或不同的算法？

我的最终目标是::我想通过读取 map 数组中的所有 True 值执行一些具有最少操作的读取操作成本。这与读取操作的最小数量不同。在函数完成时，不应有未读的 True 值。

map 数组由一些外部函数填充，任何成员可以是 1 或 0。

---

例如::

map [4] = 1; map [8] = 1;

Adr=4,Cnt=5 的 1 个读操作成本最低 (35)

鉴于

具有 Adr=4,Cnt=1 和 Adr=8,Cnt=1 的 2 个读取操作成本 (27+27=54)

---

#include <string.h>

typedef unsigned int    Ui32;

#define cntof(x)    (sizeof(x) / sizeof((x)[0]))

#define ZERO(x)     do{memset(&(x), 0, sizeof(x));}while(0)

typedef struct _S_MB_oper{

    Ui32    Adr;
    Ui32    Cnt;

}S_MB_oper;

typedef struct _S_MB_code{

    Ui32        OpxCnt;
    S_MB_oper   OpxLst[20];
    Ui32        OpxPay;

}S_MB_code;

char map[65536] = {0};

static int opx_ListOkey(S_MB_code *px_kod, char *pi_map)
{
    int  cost = 0;
    char map[65536];

    memcpy(map, pi_map, sizeof(map));

    for(Ui32 o = 0; o < px_kod->OpxCnt; o++)
    {
        for(Ui32 i = 0; i < px_kod->OpxLst[o].Cnt; i++)
        {
            Ui32 adr = px_kod->OpxLst[o].Adr + i;
            // ...
            if(adr < cntof(map)){map[adr] = 0x0;}
        }
    }

    for(Ui32 i = 0; i < cntof(map); i++)
    {
        if(map[i] > 0x0){return -1;}
    }

    // calculate COST...

    for(Ui32 o = 0; o < px_kod->OpxCnt; o++)
    {
        cost += 12;
        cost += 13;
        cost += (2 * px_kod->OpxLst[o].Cnt);
    }

    px_kod->OpxPay = (Ui32)cost; return cost;
}

static int opx_FindNext(char *map, int pi_idx)
{
    int i;

    if(pi_idx < 0){pi_idx = 0;}

    for(i = pi_idx; i < 65536; i++)
    {
        if(map[i] > 0x0){return i;}
    }

    return -1;
}

static int opx_FindZero(char *map, int pi_idx)
{
    int i;

    if(pi_idx < 0){pi_idx = 0;}

    for(i = pi_idx; i < 65536; i++)
    {
        if(map[i] < 0x1){return i;}
    }

    return -1;
}

static int opx_Resolver(S_MB_code *po_bst, S_MB_code *px_wrk, char *pi_map, Ui32 *px_idx, int _min, int _max)
{
    int pay, kmax, kmin = 1;

    if(*px_idx >= px_wrk->OpxCnt)
    {
        return opx_ListOkey(px_wrk, pi_map);
    }

    _min = opx_FindNext(pi_map, _min);
    // ...
    if(_min < 0){return -1;}

    kmax = (_max - _min) + 1;
    // must be less than 127 !
    if(kmax > 127){kmax = 127;}

    // is this recursion the last one ?
    if(*px_idx >= (px_wrk->OpxCnt - 1))
    {
        kmin = kmax;
    }
    else
    {
        int zero = opx_FindZero(pi_map, _min);
        // ...
        if(zero > 0)
        {
            kmin = zero - _min;
            // enforce kmax limit !?
            if(kmin > kmax){kmin = kmax;}
        }
    }

    for(int _cnt = kmin; _cnt <= kmax; _cnt++)
    {
        px_wrk->OpxLst[*px_idx].Adr = (Ui32)_min;
        px_wrk->OpxLst[*px_idx].Cnt = (Ui32)_cnt;

        (*px_idx)++;
        pay = opx_Resolver(po_bst, px_wrk, pi_map, px_idx, (_min + _cnt), _max);
        (*px_idx)--;

        if(pay > 0)
        {
            if((Ui32)pay < po_bst->OpxPay)
            {
                memcpy(po_bst, px_wrk, sizeof(*po_bst));
            }
        }
    }

    return (int)po_bst->OpxPay;
}

int main()
{
    int _max = -1, _cnt = 0;

    S_MB_code best = {0};
    S_MB_code work = {0};

    // SOME TEST DATA...

    map[ 4] = 1;
    map[ 8] = 1;
    /*
    map[64] = 1;
    map[72] = 1;
    map[80] = 1;
    map[88] = 1;
    map[96] = 1;
    */

    // SOME TEST DATA...

    for(int i = 0; i < cntof(map); i++)
    {
        if(map[i] > 0)
        {
            _max = i; _cnt++;
        }
    }

    // num of Opx can be as much as num of individual bit(s).
    if(_cnt > cntof(work.OpxLst)){_cnt = cntof(work.OpxLst);}

    best.OpxPay = 1000000000L; // invalid great number...

    for(int opx_cnt = 1; opx_cnt <= _cnt; opx_cnt++)
    {
        int rv;

        Ui32 x = 0;

        ZERO(work); work.OpxCnt = (Ui32)opx_cnt;

        rv = opx_Resolver(&best, &work, map, &x, -42, _max);
    }

    return 0;
}

Answer 1

您可以使用动态规划 来计算覆盖map[] 中前i 个真值的最低成本。称之为 f(i)。正如我将解释的，您可以通过查看 j < i 的所有 f(j) 来计算 f(i)，因此这将花费真值数量的二次方时间——比指数好得多。您要寻找的最终答案是 f(n)，其中 n 是 map[] 中真值的数量。

第一步是将 map[] 预处理为真值位置列表。 (可以在原始 map[] 数组上执行 DP，但如果真实值稀疏，这会更慢，而且不能更快。)

int pos[65536];    // Every position *could* be true
int nTrue = 0;

void getPosList() {
    for (int i = 0; i < 65536; ++i) {
        if (map[i]) pos[nTrue++] = i;
    }
}

当我们只查看前 i 个真值的子问题时，我们知道第 i 个真值必须被以 i 结尾的读取覆盖。这个 block 可以从任何位置开始 j <= i;我们不知道，所以我们必须测试所有这些并选择最好的。这里启用DP的关键属性(Optimal Substructure)是在任意一个i大小的子问题的最优解中，如果覆盖第i个真值的read是从第j个真值开始的，那么前面的j-1个真值(j-1) 大小的子问题的最优解必须包含这些值。

所以:f(i) = min(f(j) + score(pos(j+1), pos(i))，取最小值取全部 1 <= j < i。pos(k)指到 map[] 中第 k 个真值的位置，score(x, y) 是从位置 x 到位置 y(含)的读取得分。

int scores[65537];    // We effectively start indexing at 1
scores[0] = 0;    // Covering the first 0 true values requires 0 cost

// Calculate the minimum score that could allow the first i > 0 true values
// to be read, and store it in scores[i].
// We can assume that all lower values have already been calculated.
void calcF(int i) {
    int bestStart, bestScore = INT_MAX;
    for (int j = 0; j < i; ++j) {    // Always executes at least once
        int attemptScore = scores[j] + score(pos[j + 1], pos[i]);
        if (attemptScore < bestScore) {
            bestStart = j + 1;
            bestScore = attemptScore;
        }
    }

    scores[i] = bestScore;
}

int score(int i, int j) {
    return 25 + 2 * (j + 1 - i);
}

int main(int argc, char **argv) {
    // Set up map[] however you want
    getPosList();

    for (int i = 1; i <= nTrue; ++i) {
        calcF(i);
    }

    printf("Optimal solution has cost %d.\n", scores[nTrue]);
    return 0;
}

从分数中提取解决方案

使用此方案，您可以计算最佳解决方案的分数:它只是 f(n)，其中 n 是 map[] 中真实值的数量.为了实际构建解决方案，您需要通过 f() 分数表回读以推断做出了哪个选择:

void printSolution() {
    int i = nTrue;
    while (i) {
        for (int j = 0; j < i; ++j) {
            if (scores[i] == scores[j] + score(pos[j + 1], pos[i])) {
                // We know that a read can be made from pos[j + 1] to pos[i] in
                // an optimal solution, so let's make it.
                printf("Read from %d to %d for cost %d.\n", pos[j + 1], pos[i], score(pos[j + 1], pos[i]));
                i = j;
                break;
            }
        }
    }
}

可能有多种可能的选择，但所有选择都会产生最优解。

进一步加速

上述解决方案适用于任意评分函数。因为您的评分函数结构简单，所以可能可以开发出更快的算法。

例如，我们可以证明存在一个间隙宽度，高于该间隙宽度总是有益于将单个读取分成两个读取。假设我们有一个从位置 x-a 到 x 的读取，另一个从位置 y 到 y+b 的读取，其中 y > x。这两个单独读取的组合成本为 25 + 2 * (a + 1) + 25 + 2 * (b + 1) = 54 + 2 * (a + b)。从 x-a 延伸到 y+b 的单个读取将花费 25 + 2 * (y + b - x + a + 1) = 27 + 2 * (a + b) + 2 * (y - x)。因此，单次读取的成本减少了 27 - 2 * (y - x)。如果 y - x > 13，则此差异低于零:换句话说，包含跨越 12 或更多间隙的单个读取永远不是最佳选择。

要利用此属性，在 calcF() 中，可以按开始位置的降序(即按宽度的升序)尝试最终读取，并且内部循环会立即停止因为任何间隙宽度超过 12。因为该读取和所有随后尝试的更宽读取将包含这个过大的间隙，因此不是最佳的，因此不需要尝试它们。