程序跑出來是22

來源: dynamic 於 2009-08-20 21:21:05 [] [舊帖] [給我悄悄話] 本文已被閱讀： 次 (5750 bytes)
本文內容已被 [ dynamic ] 在 2009-09-12 14:59:09 編輯過。如有問題，請報告版主或論壇管理刪除.
手算的話狀態太多了，估計會算崩潰。。。

程序的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 < n; i++) if (g[x][i] || g[i][x]) dfs(g, i, k);
}

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 << 50;
if (currentmask >= minmask) return;
if (m == k) {
minmask = currentmask;
return;
}
for (i = 0; i < m; i++) if (((left >> i) & 1) && !((neighbors[i] >> 10) & left)) canput |= 1 << i;
for (i = 0; i < m; i++) if (canput >> i & 1) {
newmask = currentmask;
for (j = 0; j < k; j++) {
if (g[i][mapping[j]]) newmask |= (1LL << (m * (m - 1) / 2) - (k * (k - 1) / 2) - j - 1);
}
if (newmask < tmpmin) tmpmin = newmask;
}
for (i = 0; i < m; i++) if (canput >> i & 1) {
newmask = currentmask;
for (j = 0; j < i; j++) if ((canput >> j & 1) && neighbors[i] == neighbors[j]) break;
if (j < i) continue;
for (j = 0; j < k; j++) {
if (g[i][mapping[j]]) newmask |= (1LL << (m * (m - 1) / 2) - (k * (k - 1) / 2) - j - 1);
}
if (newmask > tmpmin) continue;
mapping[k] = i;
graph_minimal_representation(g, m, k + 1, left ^ (1 << i), newmask, minmask);
}
}

long long graph_compress(char g[][10]) {
int i, j, k = 0, t, m;
memset(flag, 0xff, sizeof(flag));
vector< pair > a;
for (i = 0; i < n; i++) if (flag[i] == -1) {
nodes.clear();
dfs(g, i, k++);
m = nodes.size();
for (j = 0; j < m; j++) {
for (t = 0; t < m; t++) {
gsub[j][t] = g[nodes[j]][nodes[t]];
}
}
for (j = 0; j < m; j++) {
neighbors[j] = 0;
for (t = 0; t < m; t++) {
if (gsub[t][j]) neighbors[j] |= 1 << t;
if (gsub[j][t]) neighbors[j] |= 1 << t + 10;
}
}
long long tmp = 1LL << 50;
graph_minimal_representation(gsub, m, 0, (1 << m) - 1, 0, tmp);
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 < a.size(); i++) {
m = a[i].first;
for (k = 0; k < m; k++) {
for (j = 0; j < k; 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 < n; i++) {
for (j = i + 1; j < n; j++) {
if (gsub[j][i]) ret |= (1LL << k);
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 < n; i++) {
for (j = i + 1; j < n; j++) {
g[j][i] = (mask >> k++) & 1;
}
}
long long subp;
for (i = 0; i < n; i++) {
for (j = i + 1; j < n; j++) if (!g[i][j] && !g[j][i]){
memcpy(ng, g, sizeof(g));
for (k = 0; k < n; k++) if (ng[k][i] || k == i) {
for (t = 0; t < n; t++) if (ng[j][t] || t == j) {
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 < n; k++) if (ng[k][j] || k == j) {
for (t = 0; t < n; t++) if (ng[i][t] || t == i) {
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 << n * (n - 1) / 2) - 1;
f[goal] = 0;
fac[0] = 1;
for (int i = 1; i <= 10; i++) fac[i] = fac[i - 1] * i;
printf("%d\n", dp(0));
return 0;
}

所有跟帖： 

• NIU!!! -idiot94- ♂ 給 idiot94 發送悄悄話 idiot94 的博客首頁 (0 bytes) () 08/21/2009 postreply 07:55:36

• 很牛。花多久弄出來的？ -gushen- ♂ 給 gushen 發送悄悄話 (0 bytes) () 08/22/2009 postreply 09:23:40

• 程序不難寫，但花了幾個小時優化。 -dynamic- ♂ 給 dynamic 發送悄悄話 (0 bytes) () 08/22/2009 postreply 16:21:42

• 厲害！ -說了就走- ♂ 給 說了就走 發送悄悄話 說了就走 的博客首頁 (38 bytes) () 08/22/2009 postreply 09:44:49

• 回複：厲害！ -dynamic- ♂ 給 dynamic 發送悄悄話 (327 bytes) () 08/22/2009 postreply 16:26:13

• 問的是最複雜的情況 -說了就走- ♂ 給 說了就走 發送悄悄話 說了就走 的博客首頁 (45 bytes) () 08/23/2009 postreply 18:09:42

請您先登陸，再發跟帖！

發現Adblock插件

如要繼續瀏覽
請支持本站 請務必在本站關閉/移除任何Adblock

關閉Adblock後 請點擊

請參考如何關閉Adblock/Adblock plus

安裝Adblock plus用戶請點擊瀏覽器圖標
選擇“Disable on www.wenxuecity.com”

安裝Adblock用戶請點擊圖標
選擇“don't run on pages on this domain”