1

OpxCnt 変数の値が大きいほど時間がかかる単純な (ブルート フォース) 再帰ソルバー アルゴリズムがあります。OpxCnt の値が小さい場合、問題なく、魅力的に機能します。OpxCnt 変数が大きくなるにつれて、アルゴリズムは非常に遅くなります。これは予想されることですが、最適化または別のアルゴリズムですか?

私の最終的な目標は、 :: 操作コストが最小の読み取り操作をいくつか実行して、マップ配列内のすべての True 値を読み取りたいということです。これは、読み取り操作の最小数と同じではありません。関数の完了時に、未読の True 値があってはなりません。

map 配列は何らかの外部関数によって取り込まれます。どのメンバーも 1 または 0 の可能性があります。

例えば ​​：：

マップ[4] = 1; マップ[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;
}
4

1 に答える 1

2

動的計画法を使用して、 の最初の i 個の真の値をカバーする最小コストを計算できますmap[]。これを f(i) と呼びます。後で説明するように、j < i のすべての f(j) を調べることで f(i) を計算できるため、真の値の数が 2 次になるため、指数関数よりもはるかに時間がかかります。探している最終的な答えは f(n) です。ここで、n は の真の値の数ですmap[]。

最初のステップはmap[]、真の値の位置のリストに前処理することです。(未加工の配列で DP を実行することは可能map[]ですが、真の値がまばらな場合は遅くなり、高速化することはできません。)

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 を有効にする重要なプロパティ (最適な部分構造) は、i 番目の真の値をカバーする読み取りが j 番目の真の値で始まる場合、i サイズの部分問題の最適解では、先行する j-1 の真の値が(j-1) サイズの部分問題の最適解によってカバーされます。

したがって: f(i) = min(f(j) + score(pos(j+1), pos(i)), 1 <= j < i. pos(k) は位置を参照します。の k 番目の true 値のmap[]スコア (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;
            }
        }
    }
}

いくつかの選択肢があるかもしれませんが、それらすべてが最適なソリューションを生み出します。

さらなる高速化

上記のソリューションは、任意のスコアリング関数に対して機能します。スコアリング関数は単純な構造であるため、さらに高速なアルゴリズムを開発できる可能性があります。

たとえば、1 回の読み取りを 2 回の読み取りに分割することが常に有益なギャップ幅があることを証明できます。位置 xa から x までの読み取りと、位置 y から y+b までの別の読み取りがあり、y > x であるとします。これら 2 つの個別の読み取りの合計コストは、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) になります。したがって、1 回の読み取りのコストは 27 - 2 * (y - x) 少なくなります。y - x > 13 の場合、この差はゼロ未満になります。つまり、12 以上のギャップにまたがる単一の読み取りを含めることは決して最適ではありません。

このプロパティを利用するために、内部calcF()で最後の読み取りを開始位置の降順 (つまり、幅の昇順) で試行することができ、ギャップ幅が 12 を超えるとすぐに内側のループが停止しました。試行されたより広い読み取りには、この大きすぎるギャップが含まれるため、最適ではないため、試行する必要はありません。

于 2012-11-16T11:23:56.783 に答える