內(nèi)容概要：
- Hamilton路徑崔步、回路算法
- 基于位運(yùn)算的狀態(tài)壓縮優(yōu)化
- 記憶化搜索
- Hamilton圖的應(yīng)用
哈密頓圖
問題來源：1859年稳吮，愛爾蘭數(shù)學(xué)家、天文學(xué)家哈密頓提出的一個(gè)在正十二面體的二十個(gè)頂點(diǎn)上周游世界的游戲井濒。
基本概念：
哈密頓路徑：通過圖中所有頂點(diǎn)一次且僅一次的路徑稱為哈密頓(Hamilton)路徑盖高；
哈密頓回路：通過圖中所有頂點(diǎn)一次且僅一次的回路稱為哈密頓回路；
哈密頓圖：具有哈密頓回路的圖稱為哈密頓圖眼虱；
半哈密頓圖：具有哈密頓路徑而沒有哈密頓回路的圖稱為半哈密頓圖。
尋找哈密頓回路和哈密頓路徑是一個(gè)NPC問題席纽。到目前為止捏悬，還沒有找到一個(gè)簡(jiǎn)明的條件來作為判定哈密頓圖的充要條件，研究哈密頓圖要比歐拉圖難得多润梯。
哈密頓回路和哈密頓通路有一些充分條件和必要條件过牙，由于不是充要條件編程中使用的少，這里不對(duì)它的拓?fù)湫再|(zhì)做過多討論纺铭。
我們可以通過回溯搜索按照定義判定一個(gè)圖是否是哈密頓圖寇钉。
與哈密頓回路問題比較類似的一個(gè)算法問題是旅行推銷員問題(Travelling Salesman Problem,TSP)：給定一系列城市和每隊(duì)城市之間的距離，求解訪問每座城市一次并回到起始城市的最短回路舶赔，不過這是在一個(gè)有權(quán)完全圖中尋找最短的哈密頓回路扫倡。
尋找哈密頓回路算法
最直觀的方案就是將所有頂點(diǎn)的排列序做一一檢驗(yàn)來暴力求解，比如判斷下圖中是否有哈密頓回路：
我們可以依次檢驗(yàn)頂點(diǎn)訪問序列(共24種排列)是否是一個(gè)回路：
- 0-1-2-3竟纳，0-1-3-2撵溃，0-2-1-3，0-2-3-1锥累，0-3-1-2缘挑，0-3-2-1，1-0-2-3
...
如果在圖中用回溯法進(jìn)行求解桶略，由于有些頂點(diǎn)是不相鄰的语淘，一旦這樣的情況出現(xiàn)會(huì)停止本輪回溯，相當(dāng)于進(jìn)行了剪枝际歼，如序列2-3-0-1惶翻，在檢測(cè)到2與3不相鄰時(shí)就不會(huì)再繼續(xù)本輪回溯了。
另外鹅心，由于哈密頓回路是一個(gè)回路维贺，所以判定哈密頓圖可以只從一個(gè)頂點(diǎn)開始即可，并不需要搜索頂點(diǎn)序的全排列n!種情況巴帮。如果從某個(gè)點(diǎn)開始找不到哈密頓回路溯泣，那么整張圖就一定不存在哈密頓回路了虐秋。但這只是暴力求解的一點(diǎn)優(yōu)化，求解哈密頓回路最壞的時(shí)間復(fù)雜度仍然是垃沦。
回溯法求解哈密頓回路
import java.util.ArrayList;
import java.util.Collections;
// 無向無權(quán)圖
public class HamiltonLoop {
private Graph G;
private boolean[] visited;
private int []pre;
private int end; // 回路的最后頂點(diǎn), 初始為 -1客给，如果大于0意味著存在哈密頓回路
public HamiltonLoop(Graph G){
this.G = G;
visited = new boolean[G.V()];
pre = new int[G.V()];
end = -1;
dfs(0, 0);
}
private boolean dfs(int v, int parent){
// 是否有哈密頓回路
visited[v] = true;
pre[v] = parent;
for(int w: G.adj(v)) {
if (!visited[w]) {
if(dfs(w, v)) return true;
} else if (w == 0 && allVisited()) {// 回到初始點(diǎn)并且所有頂點(diǎn)都被訪問過
end = v;
return true;
}
}
visited[v] = false;// 從v出發(fā)尋找哈密頓回路失敗,回溯
return false;
}
private boolean allVisited(){
// 所有頂點(diǎn)是否都被訪問過
for(int v = 0; v < G.V(); v ++)
if(!visited[v]) return false;
return true;
}
public ArrayList<Integer> result(){
ArrayList<Integer> res = new ArrayList<>();
if(end == -1) // 沒有哈密頓回路
return res;
int cur = end;
while(cur != 0){
res.add(cur);
cur = pre[cur];
}
res.add(0);
Collections.reverse(res);
return res;
}
public static void main(String args[]){
Graph g = new Graph("g.txt");
HamiltonLoop hp = new HamiltonLoop(g);
System.out.println(hp.result());
}
}
上述代碼可以再維護(hù)一個(gè)當(dāng)前訪問多少個(gè)頂點(diǎn)的計(jì)數(shù)，如果等于頂點(diǎn)數(shù)目說明都被訪問過肢簿，從而避免多次判斷allVisited()的時(shí)間開銷靶剑。另外遞歸終止邏輯也可以放到進(jìn)入函數(shù)時(shí)，優(yōu)化后的代碼：
import java.util.ArrayList;
import java.util.Collections;
// 無向無權(quán)圖
public class HL {
private Graph G;
private boolean[] visited;
private int []pre;
private int end; // 回路的最后頂點(diǎn), 初始為 -1池充，如果大于0意味著存在哈密頓回路
public HL(Graph G){
this.G = G;
visited = new boolean[G.V()];
pre = new int[G.V()];
end = -1;
dfs(0, 0, G.V());
}
private boolean dfs(int v, int parent, int left){// left表示剩下幾個(gè)頂點(diǎn)未訪問
// 是否有哈密頓回路
visited[v] = true;
pre[v] = parent;
left --;
if(left == 0 && G.hasEdge(v, 0)) {// 所有頂點(diǎn)都被訪問過
end = v;
return true;
}
for(int w: G.adj(v))
if (!visited[w])
if(dfs(w, v, left)) return true;
visited[v] = false;// 從v出發(fā)尋找哈密頓回路失敗,回溯
left ++; // 可以不寫,寫了也沒意義桩引，因?yàn)閘eft是函數(shù)中傳入的參數(shù)，返回上層函數(shù)后使用的仍然是上層的left
// 但是如果left是成員變量收夸，這里為了回溯就必須寫 left ++;
return false;
}
private boolean allVisited(){
// 所有頂點(diǎn)是否都被訪問過
for(int v = 0; v < G.V(); v ++)
if(!visited[v]) return false;
return true;
}
public ArrayList<Integer> result(){
ArrayList<Integer> res = new ArrayList<>();
if(end == -1) // 沒有哈密頓回路
return res;
int cur = end;
while(cur != 0){
res.add(cur);
cur = pre[cur];
}
res.add(0);
Collections.reverse(res);
return res;
}
public static void main(String args[]){
Graph g = new Graph("g.txt");
HL hp = new HL(g);
System.out.println(hp.result());
}
}
求解哈密頓路徑
由哈密頓回路的求解過程坑匠，稍加修改不難得到求解哈密頓路徑算法，不過由于哈密頓路徑依賴初始點(diǎn)
如上圖中從1開始不存在哈密頓路徑卧惜。
所以求解哈密頓路徑應(yīng)當(dāng)判斷從某點(diǎn)開始是否有哈密頓路徑厘灼，而且遞歸終止條件應(yīng)有所不同，不需要終點(diǎn)和源點(diǎn)之間有邊咽瓷。
import java.util.ArrayList;
import java.util.Collections;
// 無向無權(quán)圖
public class HLpath {
private Graph G;
private int s; // 源點(diǎn)
private boolean[] visited;
private int []pre;
private int end; // 回路的最后頂點(diǎn), 初始為 -1设凹，如果大于0意味著存在哈密頓路徑
public HLpath(Graph G, int s){
this.G = G;
this.s = s;
visited = new boolean[G.V()];
pre = new int[G.V()];
end = -1;
dfs(s, 0, G.V());
}
private boolean dfs(int v, int parent, int left){// left表示剩下幾個(gè)頂點(diǎn)未訪問
// 是否有哈密頓路徑
visited[v] = true;
pre[v] = parent;
left --;
if(left == 0) {// 所有頂點(diǎn)都被訪問過
end = v;
return true;
}
for(int w: G.adj(v))
if (!visited[w])
if(dfs(w, v, left)) return true;
visited[v] = false;// 從v出發(fā)尋找哈密頓路徑失敗,回溯
left ++; // 可以不寫,寫了也沒意義，因?yàn)閘eft是函數(shù)中傳入的參數(shù)茅姜，返回上層函數(shù)后使用的仍然是上層的left
// 但是如果left是成員變量闪朱，這里為了回溯就必須寫 left ++;
return false;
}
private boolean allVisited(){
// 所有頂點(diǎn)是否都被訪問過
for(int v = 0; v < G.V(); v ++)
if(!visited[v]) return false;
return true;
}
public ArrayList<Integer> result(){
ArrayList<Integer> res = new ArrayList<>();
if(end == -1) // 沒有哈密頓路徑
return res;
int cur = end;
while(cur != s){
res.add(cur);
cur = pre[cur];
}
res.add(cur);
Collections.reverse(res);
return res;
}
public static void main(String args[]){
Graph g = new Graph("g.txt");
HLpath hp = new HLpath(g,3);
System.out.println(hp.result());
}
}
狀態(tài)壓縮
在上面的求解哈密頓回路和哈密頓路徑的代碼中，如果圖中頂點(diǎn)很多钻洒，那么單是訪問標(biāo)記數(shù)組visited就會(huì)占用很多空間监透，而且有時(shí)我們希望把訪問標(biāo)記數(shù)組整體當(dāng)做一個(gè)狀態(tài)來使用，即visited數(shù)組的一組取值航唆，對(duì)應(yīng)某個(gè)問題的一個(gè)解胀蛮，為此引入狀態(tài)壓縮。由于visited數(shù)組元素的取值只有true和false糯钙，對(duì)應(yīng)二進(jìn)制的1和0粪狼，可以用二進(jìn)制數(shù)來表示，而二進(jìn)制數(shù)又與十進(jìn)制數(shù)一一對(duì)應(yīng)任岸，所以最終用整數(shù)就能表示頂點(diǎn)的訪問情況再榄，也就是一個(gè)整數(shù)就表示了一個(gè)集合，這就是狀態(tài)壓縮享潜。
但是整型數(shù)據(jù)位數(shù)是有限的困鸥，int型32位，去掉符號(hào)位只有31位，這樣只能表示31個(gè)頂點(diǎn)的訪問狀態(tài)澜术。不過對(duì)于尋找哈密頓路徑算法來說猬腰，它本身就是指數(shù)級(jí)別的算法，問題規(guī)模不會(huì)太大姑荷，所以31位一般足夠了盒延，實(shí)在不夠還可以用long long有64位。
由十進(jìn)制整型查看頂點(diǎn)的訪問狀態(tài)和修改頂點(diǎn)的訪問狀態(tài)也非常簡(jiǎn)單：
即如果要通過十進(jìn)制數(shù)的查看第
位是否為0添寺，只需要數(shù)
和
（1左移
位后的數(shù)）做相應(yīng)的與運(yùn)算：
進(jìn)而如果要把某一位設(shè)置為0或1懈费，只需要做加法（減法）即可：
即如果要通過十進(jìn)制數(shù)的修改第
位计露，只需要數(shù)
和
（1左移
位后的數(shù)）加減運(yùn)算：
注意：位運(yùn)算符的優(yōu)先級(jí)一般比較低楞捂，編程時(shí)要留心加括號(hào)趋厉。
基于狀態(tài)壓縮的哈密頓回路求解算法
import java.util.ArrayList;
import java.util.Collections;
// 無向無權(quán)圖
public class HL_StateCompress {
private Graph G;
private int []pre;
private int end; // 回路的最后頂點(diǎn), 初始為 -1，如果大于0意味著存在哈密頓回路
public HL_SC_MemorySearch(Graph G){
this.G = G;
pre = new int[G.V()];
end = -1;
int visited = 0;
dfs(visited, 0, 0, G.V());
}
private boolean dfs(int visited, int v, int parent, int left){// left表示剩下幾個(gè)頂點(diǎn)未訪問
// 在當(dāng)前訪問狀態(tài)下繁堡，從v開始是否有哈密頓回路
visited += (1 << v);
pre[v] = parent;
left --;
if(left == 0 && G.hasEdge(v, 0)) {// 所有頂點(diǎn)都被訪問過
end = v;
return true;
}
for(int w: G.adj(v))
if ((visited & (1 << w)) == 0)// 是否訪問過w
if(dfs(visited, w, v, left)) return true;
visited -= (1 << v);// visited 不是全局變量了,由于值傳遞乡数，可刪除這個(gè)語句
left ++; // 可以不寫,寫了也沒意義净赴，因?yàn)閘eft是函數(shù)中傳入的參數(shù)，返回上層函數(shù)后使用的仍然是上層的left
// 但是如果left是全局成員變量翼馆，這里為了回溯就必須寫 left ++;
// 但是記憶化搜索需要用到visited金度，此時(shí)就不能刪了
return false;
}
public ArrayList<Integer> result(){
ArrayList<Integer> res = new ArrayList<>();
if(end == -1) // 沒有哈密頓回路
return res;
int cur = end;
while(cur != 0){
res.add(cur);
cur = pre[cur];
}
res.add(0);
Collections.reverse(res);
return res;
}
public static void main(String args[]){
Graph g = new Graph("g.txt");
HL_StateCompress hp = new HL_StateCompress(g);
System.out.println(hp.result());
}
}
記憶化搜索
假設(shè)求解下圖的哈密頓回路：
顯然該圖中是不存在哈密頓回路的猜极，但是算法還要進(jìn)行回溯搜索，搜索序列0-1-2-3-...丢胚，0-2-1-3-...，...奥溺，但是從頂點(diǎn)3開始的右邊部分在搜索序列0-1-2-3-...時(shí)已經(jīng)搜索過了骨宠，我們相當(dāng)于進(jìn)行了重復(fù)的搜索。當(dāng)問題規(guī)模比較大時(shí)桦卒，很多的時(shí)間被浪費(fèi)在重復(fù)搜索中方灾，所以有必要記錄搜索的狀態(tài)碌更，避免重復(fù)搜索。在上圖的例子中嘿棘，0-1-2-3-...和0-2-1-3-...搜索序列在來到頂點(diǎn)3時(shí)旭绒，二者的visited值都是0b00001111，此時(shí)繼續(xù)進(jìn)行dfs二者傳入的參數(shù)完全一樣重父，求解的結(jié)果也會(huì)完全一樣房午，但是由于二者前面搜索序列的不同丹允，回溯求解時(shí)仍然會(huì)分別求解從3開始的結(jié)果，實(shí)際沒必要求解多次沪曙。
解決辦法：記憶化搜索
新增數(shù)組memo萎羔，用于記錄visited和v的不同組合狀態(tài)的求解結(jié)果，這樣如果已經(jīng)求解過缘眶，就不再進(jìn)行搜索巷懈，直接使用記錄的結(jié)果〈毡＃空間大小需要（2個(gè)頂點(diǎn)的訪問組合有00,01,10,11涌攻，需要4×2個(gè)空間；3個(gè)頂點(diǎn)需要8×3個(gè)空間芝此，以此類推。）基于記憶化搜索的優(yōu)化可以把哈密頓回路求解的時(shí)間復(fù)雜度優(yōu)化到
（最壞情況相當(dāng)于每種狀態(tài)都要計(jì)算一次，也就是memo數(shù)組的大辛尕ぁ）。
需要指出的是用僧，記憶化搜索相比于回溯算法其實(shí)并沒有優(yōu)化太多赞咙，而且記憶化搜索由于需要很多額外的內(nèi)存空間糟港、對(duì)空間進(jìn)行初始化以及尋址訪問秸抚，這些時(shí)間開銷也是不小的，綜合起來一些情況下相比回溯甚至更慢颠放，具體使用時(shí)還要看情況吭敢。
但是記憶化搜索在很多其它問題上有著非常棒的表現(xiàn)，這個(gè)思想還是有必要掌握的欲低。
哈密頓路徑問題實(shí)例
LeetCode980號(hào)問題：
這個(gè)問題可以抽象為一個(gè)哈密頓路徑問題砾莱，1就是源點(diǎn)，2就是終點(diǎn)聚假，每個(gè)無障礙方格0都要通過一次扫步，相當(dāng)于每個(gè)存在的頂點(diǎn)都要遍歷一次河胎。
解題思路：遍歷找到源點(diǎn)和終點(diǎn)的位置，然后從源點(diǎn)開始用回溯法求解哈密頓路徑個(gè)數(shù)政敢。
class Solution {
int m ,n;
private int start, end;
private int d[][] = {{0,1},{0,-1},{1,0},{-1,0}};
public int uniquePathsIII(int[][] grid) {
m = grid.length;
n = grid[0].length;
int left = m * n;// 剩余沒有被訪問的頂點(diǎn)個(gè)數(shù)
for(int i = 0; i < m; i ++)
for(int j = 0; j < n; j ++) {
if (grid[i][j] == 1) {
start = i * n + j;
grid[i][j] = 0;// 起始點(diǎn)也是可以通過的點(diǎn)
}else if(grid[i][j] == 2){
end = i * n + j;
grid[i][j] = 0;
}else if(grid[i][j] == -1)
left --;
}
return dfs(start, left, grid);
}
private boolean inArea(int x, int y){
return x >= 0 && x < m && y >= 0 && y < n;
}
private int dfs(int v, int left, int grid[][]) {
// 從v出發(fā)到end的哈密頓路徑數(shù)量
int x = v / n, y = v % n;
grid[x][y] = -1;
left--;
if (left == 0 && v == end) {
grid[x][y] = 0;//回溯
return 1;
}
int res = 0;
for (int i = 0; i < 4; i++) {
int nx = x + d[i][0];
int ny = y + d[i][1];
if (inArea(nx, ny) && grid[nx][ny] == 0) {
res += dfs(nx * n + ny, left, grid);
}
}
grid[x][y] = 0;
return res;
}
}
在上面的代碼中喷户，grid數(shù)組不只存儲(chǔ)圖的頂點(diǎn)連通信息褪尝，而且標(biāo)識(shí)頂點(diǎn)是否被訪問過期犬，這是很好的一個(gè)方案。不過我們也可以使用狀態(tài)壓縮來解決：
class Solution {
private int [][]grid;
int m ,n;
private int start, end;
private int d[][] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
public int uniquePathsIII(int[][] grid) {
this.grid = grid;
m = grid.length;
n = grid[0].length;
int left = m * n;// 剩余沒有被訪問的頂點(diǎn)個(gè)數(shù)
for(int i = 0; i < m; i ++)
for(int j = 0; j < n; j ++) {
if (grid[i][j] == 1) {
start = i * n + j;
grid[i][j] = 0;// 起始點(diǎn)也是可以通過的點(diǎn)
}else if(grid[i][j] == 2){
end = i * n + j;
grid[i][j] = 0;
}else if(grid[i][j] == -1)
left --;
}
int visited = 0;
return dfs(visited, start, left);
}
private boolean inArea(int x, int y){
return x >= 0 && x < m && y >= 0 && y < n;
}
private int dfs(int visited, int v, int left){
visited += (1 << v);
left --;
if(left == 0 && v == end) return 1;
int res = 0;
int x = v / n, y = v % n;
for(int i = 0; i < 4; i ++){
int nx = x + d[i][0];
int ny = y + d[i][1];
int next = nx * n + ny;
if(inArea(nx,ny) && grid[nx][ny] == 0 && (visited &(1 << next)) == 0)
res += dfs(visited,nx * n + ny, left);
}
return res;
}
}
