我有一个简单的(强力)递归求解器算法，它需要花费大量时间来获得更大的 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;
}
最佳答案
您可以使用动态规划 来计算覆盖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。因为该读取和所有随后尝试的更宽读取将包含这个过大的间隙，因此不是最佳的，因此不需要尝试它们。
关于c - 蛮力算法的优化还是替代？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13400639/