程序跑出来是22

dynamic 2009-08-20 21:21:05 ( reads)

手算的话状态太多了，估计会算崩溃。。。

程序的idea很简单，枚举+动态规划，每次找两个还不确定大小关系的数比较，然后算两个分支各自还需要多少步，取较大的那个。难点就在于状态的判重。对于每个状态，先求出大小关系的transitive closure，然后10个点的DAG最多有45条边，用一个long long的bitmask就可以表示。但是2^45的state space显然不能接受，所以要判重。DAG的graph isomorphism是NP hard的，所以没有什么好办法hashing。一种办法是求DAG的最小表示，也就是考虑所有可能的topological order，算出所有这些order下最小的那个bitmask，作为该DAG所对应的数。最坏情况下要枚举接近10!种order，所以会非常慢。一个改进的办法是对于每个弱连通分支分别求最小表示，然后排序后连起来。总之，在扩展了接近2,500,000个unique state之后，算出来是22。我的程序加了很多优化，在一般的机器上不到半个小时可以跑出来。

我也写了另一种基于剪枝的算法，就是算出当前的关系下valid的topological order的数目x，然后用log_2(x)作为一个lower bound来剪枝。这样做会出现一些其它问题，程序跑起来也没快多少，不过扩展的states少了，有大约1,000,000个。

如果要算n=11的话这个程序应该也没问题，找一台内存大一点的机器跑个一两天应该能出解。如果n再大的话，就需要更好的算法和更好的剪枝了。

下面把第一种算法的程序贴出来，有兴趣的话不妨去运行一下。不过可惜程序写得很乱，也没加注释，可读性很差。

#include
#include
#include
#include
#include
#include
#include

using namespace std;

int n, ct = 0, fac[11];
int p[10], flag[10], mapping[10];
char gsub[10][10];
vector nodes;
int neighbors[10];
long long goal;

map f;

void dfs(char g[][10], int x, int k) {
if (flag[x] >= 0) return;
flag[x] = k;
nodes.push_back(x);
for (int i = 0; i }

void graph_minimal_representation(char g[][10], int m, int k, int left, long long currentmask, long long &minmask) {
int i, j, canput = 0;
long long newmask, tmpmin = 1LL if (currentmask >= minmask) return;
if (m == k) {
minmask = currentmask;
return;
}
for (i = 0; i > i) & 1) && !((neighbors[i] >> 10) & left)) canput |= 1 for (i = 0; i > i & 1) {
newmask = currentmask;
for (j = 0; j if (g[i][mapping[j]]) newmask |= (1LL }
if (newmask }
for (i = 0; i > i & 1) {
newmask = currentmask;
for (j = 0; j > j & 1) && neighbors[i] == neighbors[j]) break;
if (j for (j = 0; j if (g[i][mapping[j]]) newmask |= (1LL }
if (newmask > tmpmin) continue;
mapping[k] = i;
graph_minimal_representation(g, m, k + 1, left ^ (1 }
}

long long graph_compress(char g[][10]) {
int i, j, k = 0, t, m;
memset(flag, 0xff, sizeof(flag));
vector > a;
for (i = 0; i nodes.clear();
dfs(g, i, k++);
m = nodes.size();
for (j = 0; j for (t = 0; t gsub[j][t] = g[nodes[j]][nodes[t]];
}
}
for (j = 0; j neighbors[j] = 0;
for (t = 0; t if (gsub[t][j]) neighbors[j] |= 1 if (gsub[j][t]) neighbors[j] |= 1 }
}
long long tmp = 1LL graph_minimal_representation(gsub, m, 0, (1 a.push_back(make_pair(m, tmp));
}
sort(a.begin(), a.end());
long long ret = 0;
t = 0;
memset(gsub, 0, sizeof(gsub));
for (i = 0; i m = a[i].first;
for (k = 0; k for (j = 0; j if (((a[i].second >> (m * (m - 1) / 2) - (k * (k - 1) / 2) - j - 1)) & 1) {
gsub[k + t][j + t] = 1;
}
}
}
t += m;
}
k = 0;
for (i = 0; i for (j = i + 1; j if (gsub[j][i]) ret |= (1LL k++;
}
}
return ret;
}

int dp(long long mask) {
if (f.find(mask) != f.end()) return f[mask];
int &ret = f[mask];
ret = 100;
ct++;
if (ct % 10000 == 0) printf("%d\n", ct);
int i, j, k = 0, t, r1, r2;
char g[10][10], ng[10][10];
memset(g, 0, sizeof(g));
for (i = 0; i for (j = i + 1; j g[j][i] = (mask >> k++) & 1;
}
}
long long subp;
for (i = 0; i for (j = i + 1; j memcpy(ng, g, sizeof(g));
for (k = 0; k for (t = 0; t ng[k][t] = 1;
}
}
subp = graph_compress(ng);
r1 = dp(subp);
if (r1 + 1 >= ret) continue;
memcpy(ng, g, sizeof(g));
for (k = 0; k for (t = 0; t ng[k][t] = 1;
}
}
subp = graph_compress(ng);
r2 = dp(subp);
if (r2 > r1) r1 = r2;
if (ret > r1 + 1) ret = r1 + 1;
}
}
return ret;
}

int main(int agrc, char **argv) {
sscanf(argv[1], "%d", &n);
goal = (1LL f[goal] = 0;
fac[0] = 1;
for (int i = 1; i printf("%d\n", dp(0));
return 0;
}

程序跑出来是22

跟帖(6)

idiot94

gushen

dynamic

说了就走

dynamic

说了就走