哈密頓回路的非暴力解法（轉(zhuǎn)自CSDN大神GDTZX）
首先說(shuō)明一下，此博文來(lái)自我在CSDN上看到的一篇哈密頓回路（有向圖中）的位運(yùn)算算法，出自GDTZX大神之手，（侵刪），雖然剛從校園畢業(yè)，但腦子已經(jīng)完全僵住了，花了許久才看懂了這個(gè)算法。
哈密頓回路，具體到本題之中即從某一個(gè)點(diǎn)開始經(jīng)過(guò)所有的點(diǎn)一次后再回到該點(diǎn)的不同路徑數(shù)。對(duì)于這個(gè)不同需要注意兩點(diǎn)：
如果我們將路徑經(jīng)過(guò)的點(diǎn)按順序?qū)懴?，比如?dāng)n=3時(shí)，若存在123和231。此時(shí)，我們認(rèn)為這兩條路徑是同一條哈密頓回路。而123和213則是不同的哈密頓回路。
若兩個(gè)點(diǎn)之間有多條邊，經(jīng)過(guò)不同的邊的路徑仍然看作同一條哈密頓回路。不同哈密頓回路只和經(jīng)過(guò)的點(diǎn)有關(guān)。因此對(duì)于多條邊的情況我們可以將其合并為一條邊來(lái)考慮。
對(duì)于哈密頓回路，一個(gè)簡(jiǎn)單的想法就是枚舉所有可能的路徑，判定這個(gè)路徑是否存在。即時(shí)間復(fù)雜度為O(n!)。而題目給定的數(shù)據(jù)范圍為：n <= 12，所以最大可能的枚舉次數(shù)為12! = 479,001,600。
極限的數(shù)據(jù)不到5億，所以我們可以考慮使用暴力來(lái)枚舉所有的哈密頓回路。直接采用DFS枚舉我們的每一步，最后判定是否走回到起點(diǎn)。
偽代碼如下：
DFS(int nowVertex, bool visitedVertex, int path, int length)
visitedVertex[ nowVertex ] = True;
If (all Vertex is visited) Then
Count = Count + 1
Else
For (u is next vertex of nowVertex)
If (not visitedVertex[ u ]) Then
path[ length ] = u
DFS(u, visitedVertex, path, length + 1)
End If
End For
End If
visitedVertex[ nowVertex ] = False
由于哈密頓回路始終會(huì)經(jīng)過(guò)每一個(gè)點(diǎn)，所以我們只以1為起點(diǎn)就一定可以找出所有的哈密頓回路。
那么這樣是否能夠解決這道題目呢？我只能說(shuō)不一定能夠解決。
雖然偽代碼相同，但是根據(jù)實(shí)現(xiàn)的方法會(huì)有不同的運(yùn)行效率，在某些實(shí)現(xiàn)方法下就能夠通過(guò)所有的數(shù)據(jù)點(diǎn)，在某些實(shí)現(xiàn)方法下就會(huì)超過(guò)時(shí)限。
這里我們介紹一種利用位運(yùn)算的實(shí)現(xiàn)，能夠使得整個(gè)程序的效率提高很多倍。
首先來(lái)看看代碼：
const int MAXN = 14;
int edge[ MAXN ];
int p[1 << MAXN];
int cnt;
void dfs(int nowVertex, int unused) {
if (!unused) {
cnt += (edge[nowVertex] & 1);
return ;
}
int rest = unused & edge[ nowVertex ];
while (rest) {
int tp = rest & (-rest);
dfs(p[ tp ], unused - tp);
rest -= tp;
}
return ;
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; ++i)
p[ 1 << i ] = i + 1;
while (m--) {
int u, v;
scanf("%d %d", &u, &v);
edge[u] |= 1 << (v - 1);
}
dfs(1, (1 << n) - 2);
printf("%dn", cnt);
return 0;
}
我們一個(gè)一個(gè)來(lái)解釋每一個(gè)變量的含義：
edge[i]表示點(diǎn)i的next節(jié)點(diǎn)情況，我們用二進(jìn)制表示edge[i]，比如當(dāng)edge[i]=01011時(shí)：
+---+---+---+---+---+
| 5 | 4 | 3 | 2 | 1 | 右起第j位
+---+---+---+---+---+
| 0 | 1 | 0 | 1 | 1 | 二進(jìn)制位的值
+---+---+---+---+---+
從右起第j位，若為1，則表示存在i到j(luò)的邊；若為0，則表示不存在i到j(luò)的邊。所以edge[i]=01011就表示節(jié)點(diǎn)i可以到達(dá)節(jié)點(diǎn)1，2，4。
p[i]是為了方便查找點(diǎn)的編號(hào)。在edge[i]中若存在01000，我們可以根據(jù)01000=8, 而p[8]=4來(lái)快速的通過(guò)二進(jìn)制位來(lái)定位節(jié)點(diǎn)編號(hào)。
所以有初始化：
for (int i = 0; i < n; ++i)
p[ 1 << i ] = i + 1;
而通過(guò)節(jié)點(diǎn)編號(hào)來(lái)找到二進(jìn)制位，則可以直接使用1 << (i - 1)實(shí)現(xiàn)。
我們?cè)谧x入數(shù)據(jù)時(shí)，通過(guò)位運(yùn)算邊可以記錄下所有點(diǎn)之間的連邊情況：
while (m--) {
int u, v;
scanf("%d %d", &u, &v);
edge[u] |= 1 << (v - 1); // 記錄u有后繼節(jié)點(diǎn)v
}
unused該二進(jìn)制數(shù)表示我們尚未訪問(wèn)的節(jié)點(diǎn)集合，同樣的右起第i位表示節(jié)點(diǎn)i，比如unused = 01100：
+---+---+---+---+---+
| 5 | 4 | 3 | 2 | 1 | 右起第i位
+---+---+---+---+---+
| 0 | 1 | 1 | 0 | 0 | 二進(jìn)制位的值
+---+---+---+---+---+
表示我們現(xiàn)在深度優(yōu)先搜索已經(jīng)經(jīng)過(guò)了節(jié)點(diǎn)1,2,5，而節(jié)點(diǎn)3,4還尚未經(jīng)過(guò)。
由于我們是以節(jié)點(diǎn)1作為起點(diǎn)，初始化的unused也就要去掉最右邊的1，所以代碼為dfs(1, (1 << n) - 2)。
接下來(lái)我們逐行解釋dfs函數(shù)：
if (!unused) {
cnt += (edge[nowVertex] & 1);
return ;
}
當(dāng)我們所有的節(jié)點(diǎn)都經(jīng)過(guò)一次之后，unused中一定不存在1，因此有!unused = true。但是此時(shí)并不一定找到了哈密頓回路，我們還需要判斷當(dāng)前節(jié)點(diǎn)是否能回到起點(diǎn)，也就是節(jié)點(diǎn)1。若nowVertex可以到達(dá)節(jié)點(diǎn)1，則edge[nowVertex]最右邊1位一定是1，那么就一定有edge[nowVertex] & 1 = 1。
int rest = unused & edge[ nowVertex ];
rest表示當(dāng)前節(jié)點(diǎn)還可以走到的未訪問(wèn)節(jié)點(diǎn)。由于&運(yùn)算的性質(zhì)，只有當(dāng)unused和edge[ nowVertex ]對(duì)應(yīng)二進(jìn)制位同時(shí)為1時(shí)，rest對(duì)應(yīng)的二進(jìn)制位才會(huì)為1。其含義就是該節(jié)點(diǎn)尚未訪問(wèn)，且節(jié)點(diǎn)nowVertex可以到達(dá)該節(jié)點(diǎn)。
while (rest) {
int tp = rest & (-rest);
dfs(p[ tp ], unused - tp);
rest -= tp;
}
該循環(huán)的作用是枚舉每一個(gè)可以到達(dá)的點(diǎn)。
int tp = rest & (-rest);
這里利用了一個(gè)性質(zhì)，即p & -p等于取出p的最右邊的一個(gè)1。舉個(gè)例子p=10110:
+---+---+---+---+---+
p | 1 | 0 | 1 | 1 | 0 |
+---+---+---+---+---+
-p | 0 | 1 | 0 | 1 | 0 |
+---+---+---+---+---+
& | 0 | 0 | 0 | 1 | 0 |
+---+---+---+---+---+
我們不斷的利用這個(gè)性質(zhì)從rest里面取出可以使用的二進(jìn)制位，進(jìn)行dfs(p[ tp ], unused - tp);。同時(shí)再枚舉完一個(gè)節(jié)點(diǎn)后，將其從rest中刪除，即rest -= tp;。
最后我們?cè)偈褂?code>printf("%dn", cnt);來(lái)輸出我們找到的方案數(shù)。
在上面DFS的基礎(chǔ)上，我們還可以進(jìn)一步優(yōu)化。
遞歸的過(guò)程中，unused很有可能會(huì)出現(xiàn)重復(fù)的情況，比如說(shuō)從1->3->2->4和從1->2->3->4，對(duì)于dfs(4, unused)來(lái)說(shuō)，此時(shí)的unused值都是相同的。因此我們可以采用記憶化搜索的方式進(jìn)一步降低復(fù)雜度。
定義數(shù)組f[n][unused]表示當(dāng)前節(jié)點(diǎn)為n，且節(jié)點(diǎn)訪問(wèn)情況為unused時(shí)的方案數(shù)量。
那么有：
f[n][unused] = sigma(f[p][unused + (1 << (n - 1))] | (unused & (1 << (n - 1)) == 0) and (p != n) and (edge[p] & (1 << (n - 1)) != 0))
這對(duì)應(yīng)的是原dfs函數(shù)中下面這段代碼的逆過(guò)程。
while (rest) {
int tp = rest & (-rest);
dfs(p[ tp ], unused - tp);
rest -= tp;
}
三個(gè)條件分別為：
(unused & (1 << (n - 1)) == 0)表示當(dāng)前狀態(tài)中右起第n位為0(p != n)表示前驅(qū)結(jié)點(diǎn)不等于n(edge[p] & (1 << (n - 1)) != 0)表示節(jié)點(diǎn)p能夠到達(dá)節(jié)點(diǎn)n在計(jì)算f[n][unused]的過(guò)程中，假設(shè)unused的二進(jìn)制表示中有i個(gè)1，則我們需要事先計(jì)算出所有i+1個(gè)1的狀態(tài)才能夠保證unused + (1 << (p - 1))是正確的結(jié)果。
因此我們?cè)诿杜e過(guò)程中，需要按照狀態(tài)中1的個(gè)數(shù)來(lái)枚舉。
其偽代碼：
For numberOfOnes = n-1 .. 0
For (the number of ones of unused equals numberOfOnes)
For nowVertex = 1 .. n
For prevVertex = 1 .. n
If (unused & (1 << (nowVertex - 1)) == 0) and (prevVertex != nowVertex) and (edge[ prevVertex ] & (1 << (nowVertex - 1)) != 0) Then
f[ nowVertex ][ unused ] = f[ nowVertex ][ unused ] + f[ prevVertex ][unused + (1 << (nowVertex - 1))]
End If
End For
End For
End For
End For
對(duì)于f[n][ unused ]數(shù)組，其初始條件為f[1][(1 << n) - 2] = 1。
最后需要將所有的f[n][0]中能夠到達(dá)節(jié)點(diǎn)1的節(jié)點(diǎn)n累加起來(lái)，即可得到所有的方案數(shù)。該算法的理論時(shí)間復(fù)雜度為O(2^n*n^2)。
該題目一共只有7名選手通過(guò)，大部分提交過(guò)該題的選手也都有一定的部分分值。
本題直接采用搜索就能夠通過(guò)，拉開差距的主要原因是對(duì)于偽代碼實(shí)現(xiàn)方式的不同，而導(dǎo)致通過(guò)的測(cè)試點(diǎn)數(shù)量不同。
另外還有一個(gè)易錯(cuò)點(diǎn)是走完所有節(jié)點(diǎn)之后一定要判斷是否可以回到起點(diǎn)。
下載文檔
