1

我有一个简单的（强力）递归求解器算法，它需要大量时间来获取更大的 OpxCnt 变量值。对于小的 OpxCnt 值，没问题，就像一个魅力。随着 OpxCnt 变量变大，算法变得非常慢。这是意料之中的，但有任何优化或不同的算法吗？

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

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

例如 ：：

地图[4] = 1; 地图[8] = 1;

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

然而

2 次读取操作 Adr=4,Cnt=1 & Adr=8,Cnt=1 成本 (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;
}
4

1 回答 1

2

您可以使用动态规划来计算覆盖 中前 i 个真值的最低成本map[]。称之为 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 结尾的读取覆盖。这个块可以从任何位置开始 j <= i; 我们不知道，所以我们必须测试所有这些并选择最好的。这里启用DP的关键属性（Optimal Substructure）是，在任何i个大小的子问题的最优解中，如果覆盖第i个真值的读取从第j个真值开始，那么前面的j-1个真值必须是由 (j-1) 大小的子问题的最优解所覆盖。

所以：f(i) = min(f(j) + score(pos(j+1), pos(i))，取最小值取所有1 <= j < i。pos(k)指的是位置中的第 k 个真值map[]， 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;
            }
        }
    }
}

可能有几种可能的选择，但所有选择都会产生最佳解决方案。

进一步加速

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

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

为了利用这个属性，inside calcF()，最终读取可以按起始位置的降序（即宽度的递增顺序）尝试，并且一旦任何间隙宽度超过 12，内部循环就会停止。因为该读取和所有后续尝试的更广泛的读取将包含这个太大的差距，因此不是最理想的，它们不需要尝试。

于 2012-11-16T11:23:56.783 回答