哈密顿图

作者: Ice_spring | 来源:发表于2020-04-08 19:41 被阅读0次

内容概要：

Hamilton路径、回路算法
基于位运算的状态压缩优化
记忆化搜索
Hamilton图的应用

哈密顿图

问题来源：1859年，爱尔兰数学家、天文学家哈密顿提出的一个在正十二面体的二十个顶点上周游世界的游戏。
基本概念：
哈密顿路径：通过图中所有顶点一次且仅一次的路径称为哈密顿(Hamilton)路径；
哈密顿回路：通过图中所有顶点一次且仅一次的回路称为哈密顿回路；
哈密顿图：具有哈密顿回路的图称为哈密顿图；
半哈密顿图：具有哈密顿路径而没有哈密顿回路的图称为半哈密顿图。

寻找哈密顿回路和哈密顿路径是一个NPC问题。到目前为止，还没有找到一个简明的条件来作为判定哈密顿图的充要条件，研究哈密顿图要比欧拉图难得多。
哈密顿回路和哈密顿通路有一些充分条件和必要条件，由于不是充要条件编程中使用的少，这里不对它的拓扑性质做过多讨论。
我们可以通过回溯搜索按照定义判定一个图是否是哈密顿图。
与哈密顿回路问题比较类似的一个算法问题是旅行推销员问题(Travelling Salesman Problem,TSP)：给定一系列城市和每队城市之间的距离，求解访问每座城市一次并回到起始城市的最短回路，不过这是在一个有权完全图中寻找最短的哈密顿回路。
寻找哈密顿回路算法
最直观的方案就是将所有顶点的排列序做一一检验来暴力求解，比如判断下图中是否有哈密顿回路：

哈密顿

我们可以依次检验顶点访问序列(共24种排列)是否是一个回路：

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
...

如果在图中用回溯法进行求解，由于有些顶点是不相邻的，一旦这样的情况出现会停止本轮回溯，相当于进行了剪枝，如序列2-3-0-1，在检测到2与3不相邻时就不会再继续本轮回溯了。
另外，由于哈密顿回路是一个回路，所以判定哈密顿图可以只从一个顶点开始即可，并不需要搜索顶点序的全排列n!种情况。如果从某个点开始找不到哈密顿回路，那么整张图就一定不存在哈密顿回路了。但这只是暴力求解的一点优化，求解哈密顿回路最坏的时间复杂度仍然是 $O(n!)$ 。
回溯法求解哈密顿回路

import java.util.ArrayList;
import java.util.Collections;
// 无向无权图
public class HamiltonLoop {

    private Graph G;
    private boolean[] visited;
    private int []pre;
    private int end; // 回路的最后顶点, 初始为 -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()) {// 回到初始点并且所有顶点都被访问过
                end = v;
                return true;
            }
        }
        visited[v] = false;// 从v出发寻找哈密顿回路失败,回溯
        return false;
    }

    private boolean allVisited(){
        // 所有顶点是否都被访问过
        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());
    }
}

上述代码可以再维护一个当前访问多少个顶点的计数，如果等于顶点数目说明都被访问过，从而避免多次判断allVisited()的 $O(V)$ 时间开销。另外递归终止逻辑也可以放到进入函数时，优化后的代码：

import java.util.ArrayList;
import java.util.Collections;
// 无向无权图
public class HL {

    private Graph G;
    private boolean[] visited;
    private int []pre;
    private int end; // 回路的最后顶点, 初始为 -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表示剩下几个顶点未访问
        // 是否有哈密顿回路
        visited[v] = true;
        pre[v] = parent;
        left --;

        if(left == 0 && G.hasEdge(v, 0)) {// 所有顶点都被访问过
            end = v;
            return true;
        }
        for(int w: G.adj(v))
            if (!visited[w])
                if(dfs(w, v, left)) return true;


        visited[v] = false;// 从v出发寻找哈密顿回路失败,回溯
        left ++; // 可以不写,写了也没意义，因为left是函数中传入的参数，返回上层函数后使用的仍然是上层的left
        // 但是如果left是成员变量，这里为了回溯就必须写 left ++;
        return false;
    }

    private boolean allVisited(){
        // 所有顶点是否都被访问过
        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());
    }
}

求解哈密顿路径
由哈密顿回路的求解过程，稍加修改不难得到求解哈密顿路径算法，不过由于哈密顿路径依赖初始点

哈密顿路径

如上图中从1开始不存在哈密顿路径。
所以求解哈密顿路径应当判断从某点开始是否有哈密顿路径，而且递归终止条件应有所不同，不需要终点和源点之间有边。

import java.util.ArrayList;
import java.util.Collections;
// 无向无权图
public class HLpath {

    private Graph G;
    private int s; // 源点
    private boolean[] visited;
    private int []pre;
    private int end; // 回路的最后顶点, 初始为 -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表示剩下几个顶点未访问
        // 是否有哈密顿路径
        visited[v] = true;
        pre[v] = parent;
        left --;

        if(left == 0) {// 所有顶点都被访问过
            end = v;
            return true;
        }
        for(int w: G.adj(v))
            if (!visited[w])
                if(dfs(w, v, left)) return true;


        visited[v] = false;// 从v出发寻找哈密顿路径失败,回溯
        left ++; // 可以不写,写了也没意义，因为left是函数中传入的参数，返回上层函数后使用的仍然是上层的left
        // 但是如果left是成员变量，这里为了回溯就必须写 left ++;
        return false;
    }

    private boolean allVisited(){
        // 所有顶点是否都被访问过
        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());
    }
}

状态压缩

在上面的求解哈密顿回路和哈密顿路径的代码中，如果图中顶点很多，那么单是访问标记数组visited就会占用很多空间，为此引入状态压缩。由于visited数组元素的取值只有true和false，对应二进制的1和0，可以用二进制数来表示，而二进制数又与十进制数一一对应，所以最终用整数就能表示顶点的访问情况。

状态压缩

但是整型数据位数是有限的，int型32位，去掉符号位只有31位，这样只能表示31个顶点的访问状态。不过对于寻找哈密顿路径算法来说，它本身就是指数级别的算法，问题规模不会太大，所以31位一般足够了，实在不够还可以用long long有64位。
由十进制整型查看顶点的访问状态和修改顶点的访问状态也非常简单：

与运算

即如果要通过十进制数 $n$ 的查看第 $i$ 位是否为0，只需要数 $n$ 和 $2^i$ （1左移 $i$ 位后的数）做相应的与运算：

$n \& (1<<i)==0?$

进而如果要把某一位设置为0或1，只需要做加法（减法）即可：

修改操作

即如果要通过十进制数 $n$ 的修改第 $i$ 位，只需要数 $n$ 和 $2^i$ （1左移 $i$ 位后的数）加减运算：

$第i位0修改为1：n+(1<<i) \\ 第i位1修改为0：n-(1<<i)$

注意：位运算符的优先级一般比较低，编程时要留心加括号。
基于状态压缩的哈密顿回路求解算法

import java.util.ArrayList;
import java.util.Collections;
// 无向无权图
public class HL_StateCompress {
    private Graph G;
    private int []pre;
    private int end; // 回路的最后顶点, 初始为 -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表示剩下几个顶点未访问
        // 在当前访问状态下，从v开始是否有哈密顿回路
        visited += (1 << v);
        pre[v] = parent;
        left --;

        if(left == 0 && G.hasEdge(v, 0)) {// 所有顶点都被访问过
            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 不是全局变量了,由于值传递，可删除这个语句
        left ++; // 可以不写,写了也没意义，因为left是函数中传入的参数，返回上层函数后使用的仍然是上层的left
        // 但是如果left是全局成员变量，这里为了回溯就必须写 left ++;

        // 但是记忆化搜索需要用到visited，此时就不能删了
        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());
    }

}

记忆化搜索

假设求解下图的哈密顿回路：

图

显然该图中是不存在哈密顿回路的，但是算法还要进行回溯搜索，搜索序列0-1-2-3-...，0-2-1-3-...，...，但是从顶点3开始的右边部分在搜索序列0-1-2-3-...时已经搜索过了，我们相当于进行了重复的搜索。当问题规模比较大时，很多的时间被浪费在重复搜索中，所以有必要记录搜索的状态，避免重复搜索。在上图的例子中，0-1-2-3-...和0-2-1-3-...搜索序列在来到顶点3时，二者的visited值都是0b00001111，此时继续进行dfs二者传入的参数完全一样，求解的结果也会完全一样，但是由于二者前面搜索序列的不同，回溯求解时仍然会分别求解从3开始的结果，实际没必要求解多次。
解决办法：记忆化搜索
新增数组memo，用于记录visited和v的不同组合状态的求解结果，这样如果已经求解过，就不再进行搜索，直接使用记录的结果。空间大小需要 $memo[1<<G.V()][G.V()]$ （2个顶点的访问组合有00,01,10,11，需要4×2个空间；3个顶点需要8×3个空间，以此类推。）基于记忆化搜索的优化可以把哈密顿回路求解的时间复杂度优化到 $O(n*2^n)$ （最坏情况相当于每种状态都要计算一次，也就是memo数组的大小）。
需要指出的是，记忆化搜索相比于回溯算法其实并没有优化太多，而且记忆化搜索由于需要很多额外的内存空间、对空间进行初始化以及寻址访问，这些时间开销也是不小的，综合起来一些情况下相比回溯甚至更慢，具体使用时还要看情况。
但是记忆化搜索在很多其它问题上有着非常棒的表现，这个思想还是有必要掌握的。

哈密顿路径问题实例

LeetCode980号问题：

LeetCode980

这个问题可以抽象为一个哈密顿路径问题，1就是源点，2就是终点，每个无障碍方格0都要通过一次，相当于每个存在的顶点都要遍历一次。
解题思路：遍历找到源点和终点的位置，然后从源点开始用回溯法求解哈密顿路径个数。

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;// 剩余没有被访问的顶点个数

        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;// 起始点也是可以通过的点
                }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出发到end的哈密顿路径数量
        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数组不只存储图的顶点连通信息，而且标识顶点是否被访问过，这是很好的一个方案。不过我们也可以使用状态压缩来解决：

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;// 剩余没有被访问的顶点个数

        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;// 起始点也是可以通过的点
                }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;
    }
}

哈密顿图

哈密顿图

状态压缩

记忆化搜索

哈密顿路径问题实例

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

算法

数据结构和算法分析