哈密尔顿回路与哈密尔顿路径

哈密尔顿回路

1859年，爱尔兰数学家哈密尔顿（Hamilton）提出下列周游世界的游戏：在正十二面体的二十个顶点上依次标记伦敦、巴黎、莫斯科等世界著名大城市，正十二面体的棱表示连接这些城市的路线。试问能否在图中做一次旅行，从顶点到顶点，沿着边行走，经过每个城市恰好一次之后再回到出发点。

将上面的问题抽象为一个图论问题：如果我们能从图的某点出发，经过所有的节点有且仅有一次，并且回到原点，那么我们就说图中存在哈密尔顿回路。

哈密尔顿回路在数学上并没有找到充分必要条件，所谓充分必要条件指的是，如果图满足什么性质它就有哈密尔顿回路以及一旦图有哈密尔顿回路这个图就满足什么性质。所以我们判断判断某个图是否是哈密尔顿图，办法就是暴力搜索，使用回溯法去搜索图。

import java.util.ArrayList;
import java.util.Collections;

public class HamiltonCycle {
    private Graph graph;
    private boolean[] visited;
    // 还有多少个节点未访问，当 left == 0 时表示所有节点都被访问过
    private int left;
    // 当前节点的前一个节点，已获得路径
    private int[] pre;
    // 最后一个被访问的节点
    private int end;

    public HamiltonCycle(Graph graph) {
        this.graph = graph;
        this.visited = new boolean[graph.V()];
        this.left = graph.V();
        this.pre = new int[graph.V()];
        this.end = -1;

        pre[0] = 0;
        dfs(0);
    }

    // dfs 设有返回值，当找到哈密尔顿回路时，提前终止
    private boolean dfs(int v) {
        visited[v] = true;

        left--;

        if (left == 0 && graph.hasEdge(v, 0)) {
            end = v;
            return true;
        }

        for (int w: graph.adj(v)) {
            if (!visited[w]) {
                pre[w] = v;
                if (dfs(w)) return true;
            }
        }
        visited[v] = false;
        left++;
        return false;
    }

    public Iterable<Integer> result() {
        ArrayList result = new ArrayList();

        if (end == -1) {
            return result;
        }

        int cur = end;
        while (cur != 0) {
            result.add(cur);
            cur = pre[cur];
        }
        result.add(0);

        Collections.reverse(result);
        return result;
    }
}

状态压缩

对图进行暴力搜索的时间复杂度是 $O(n!)$，所以暴力搜索图只适合图的规模不大的情况，当图的规模不大时，我们可以对 visited 数组进行压缩，使用一个整数来表示图中个节点的访问状态，具体就是根据这个数字的二进制位为 0 还是为 1 来表示是否被访问过。

举个例子，我们使用 int 类型来保存 visited 变量，int 类型占据 4 个字节，即 32 位，第一位是符号位，故可以认为可以表示 31 个节点访问状态，如果 visited = 1，二进制就是 00000000 00000000 00000000 00000001，从右往左数第 0 个数是 1，就表示节点 0 被访问过了，其他数字都是 0，表示其他节点没有被访问过。

观察上面的程序，我们对 visited 有三种操作：

• 判断某个节点有没有被访问过，例如判断节点 i 有没有被访问过，只要 $2^i$ 和 visited 相与即可知道，如果结果为 1，说明第 i 位为 1，即节点 i 被访问过，否则就是未被访问过
• 将节点 i 设置为被访问过(visited[i] = true)，也就是将第 i 个位置由 0 变为 1，就是将 $2^i$ 与 visited 异或即可
• 将节点 i 设置为未被访问过(visited[i] = false)，也就是将第 i 个位置由 1 变为 0，还是将 $2^i$ 与 visited 异或即可

注意 $2^i$ 可以表示为 1 << i

所以我们修改上面的程序，将 visited 数组变为一个数字

public class HamiltonCircleCompress {
    private Graph graph;
    private int visited;
    private int left;
    private int[] pre;
    private int end;

    // 不变
    public HamiltonCircleCompress(Graph graph) {
        this.graph = graph;
        this.visited = 0;
        this.left = graph.V();
        this.pre = new int[graph.V()];
        this.end = -1;

        pre[0] = 0;
        dfs(0);
    }

    private boolean dfs(int v) {
        // 设置 visited[v] 为 true
        visited = visited ^ (1 << v);
        left--;

        if (left == 0 && graph.hasEdge(v, 0)) {
            end = v;
            return true;
        }

        for (int w: graph.adj(v)) {
            // 判断 visited[w] 是否访问过
            if ((visited & (1 << w)) == 0) {
                pre[w] = v;
                if (dfs(w)) return true;
            }
        }
        
        // 设置 visited[v] 为 false
        visited = visited ^ (1 << v);
        left++;
        return false;
    }

    // 不变
    public Iterable<Integer> result() {
        ArrayList result = new ArrayList();

        if (end == -1) {
            return result;
        }

        int cur = end;
        while (cur != 0) {
            result.add(cur);
            cur = pre[cur];
        }
        result.add(0);

        Collections.reverse(result);
        return result;
    }
}

哈密尔顿路径

哈密尔顿路径的定义同哈密尔顿回路相似，如果从图中的某一点出发，能够经过图中所有的节点有且仅有一次，那么这条路径就是哈密尔顿路径。需要注意的是，图中是否存在哈密尔顿回路与起始点无关，但是哈密尔顿路径与起始点有关，可能从某点出发，并不能走过每一节点，但是从另一个节点出发，却能够走过所有节点，且只经过一次。

哈密尔顿路径的代码同哈密尔顿回路的代码相似，只有两处不同：

• 需要传入起始点
• 当 left 为 0 时，不用判断最后节点是否与起始点相邻，因为哈密尔顿路径不要求回到起始点

代码如下

import java.util.ArrayList;
import java.util.Collections;

public class HamiltonPath {
    private Graph graph;
    private boolean[] visited;
    private int left;
    private int[] pre;
    private int end;
    // 起始点
    private int s;

    public HamiltonPath(Graph graph, int s) {
        this.graph = graph;
        this.s = s;
        this.visited = new boolean[graph.V()];
        this.left = graph.V();
        this.pre = new int[graph.V()];
        this.end = -1;

        pre[0] = 0;
        dfs(s);
    }

    private boolean dfs(int v) {
        visited[v] = true;
        left--;

        // 不用判断 v 是否与起始点相邻
        if (left == 0) {
            end = v;
            return true;
        }

        for (int w: graph.adj(v)) {
            if (!visited[w]) {
                pre[w] = v;
                if (dfs(w)) return true;
            }
        }
        visited[v] = false;
        left++;
        return false;
    }

    public Iterable<Integer> result() {
        ArrayList result = new ArrayList();

        if (end == -1) {
            return result;
        }

        int cur = end;
        while (cur != 0) {
            result.add(cur);
            cur = pre[cur];
        }
        result.add(0);

        Collections.reverse(result);
        return result;
    }
}

不同路径 III

这是一道 LeetCode 上的题目，它的本质就是在求哈密尔顿路径。

题目简介

在二维网格 grid 上，有 4 种类型的方格：

• 1 表示起始方格。且只有一个起始方格

• 2 表示结束方格，且只有一个结束方格

• 0 表示我们可以走过的空方格

• -1 表示我们无法跨越的障碍

返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

**提示：1 <= grid.length * grid[0].length <= 20**。

解题思路

我们可以将整个二维网格建模为一幅图，0 表示一个节点(起始点 1 和终止点 2 也是节点)，如果两个 0 上下左右相邻，就表示它们之间有一条边。现在题目要求从起始点到达终止点，必须经过每一个节点，并且有且只能经过一次，这不就是哈密尔顿路径吗? 那么题目就是在要求这个图有多少条哈密尔顿路径。

import java.util.Arrays;
import java.util.stream.Collectors;

public class Solution {
    // 状态压缩，题目给出节点数目小于等于 20
    private int visited;
    // 起始点和终止点下标
    private int[] start;
    private int[] end;
    // 网格的行数和列数
    private int rows;
    private int columns;
    // 剩余未访问节点
    private int left;
    // 网格
    private int[][] grid;

    public int uniquePathsIII(int[][] grid) {
        this.grid = grid;
        this.rows = grid.length;
        this.columns = grid[0].length;
        this.visited = 0;
        this.start = new int[2];
        this.end = new int[2];
        this.left = rows * columns;

        // 下面这个循环是为了找到起始点和终止点，并且更新 left
        for (int row = 0; row < rows; row++) {
            for (int column = 0; column < columns; column++) {
                if (grid[row][column] == 1) {
                    start[0] = row;
                    start[1] = column;
                    grid[row][column] = 0;
                } else if (grid[row][column] == 2) {
                    end[0] = row;
                    end[1] = column;
                    grid[row][column] = 0;
                } else if (grid[row][column] == -1) {
                    // -1 不是节点，需要减掉
                    left--;
                }
            }
        }

        return dfs(start);
    }

    private int dfs(int[] v) {
        visited = visited ^ (1 << (v[0] * columns + v[1]));
        left--;
        if (left == 0 && (v[0] == end[0] && v[1] == end[1])) {
            visited = visited ^ (1 << (v[0] * columns + v[1]));
            left++;
            return 1;
        }

        int res = 0;
        for (int[] w: adj(v[0], v[1])) {
            if ((visited & (1 << (w[0] * columns + w[1]))) == 0 && grid[w[0]][w[1]] != -1) {
                res += dfs(w);
            }
        }

        // 回溯
        left++;
        visited = visited ^ (1 << (v[0] * columns + v[1]));
        return res;
    }

    private Iterable<int[]> adj(int row, int column) {
        int[][] dirs = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
        return Arrays.stream(dirs)
                .map(dir -> new int[]{dir[0] + row, dir[1] + column})
                .filter(item -> item[0] < rows && item[0] >= 0 && item[1] < columns && item[1] >= 0)
                .collect(Collectors.toList());
    }

    public static void main(String[] args) {
        int[][] grid = {{1,0,0,0},{0,0,0,0},{0,0,2,-1}};
        Solution solution = new Solution();
        int res = solution.uniquePathsIII(grid);
        System.out.println(res);
    }
}

记忆化搜索

考虑这么一幅图

我们将它分为两部分

我们称左边为第一部分，右边为第二部分。现在从节点 0 开始遍历，寻找有多少条哈密尔顿回路，我们发现不论是以何种方式遍历完第一部分来到第二部分，有多少条哈密尔顿路径只与第二部分有关，即这几种路径搜索多少条哈密尔顿路径的结果是一样的，无需重复遍历。

例如，我们以 $0 \rightarrow 1 \rightarrow 2 \rightarrow 3$ 的方式遍历完第一部分来到第二部分

它有多少条哈密尔顿路径只与第二部分有关，如果我们以 $0 \rightarrow 2 \rightarrow 1 \rightarrow 3$ 的方式遍历完第一部分来到第二部分

它有多少条哈密尔顿路径的结果应该与以 $0 \rightarrow 1 \rightarrow 2 \rightarrow 3$ 顺序遍历的结果相同，如果我们可以缓存这个结果，就可以避免不必要的遍历，从而提高性能。

当遍历到节点 v 时，如果此时它们的 visited 是一样的，我们就可以认为它们会有一样的结果，例如对于上图，当遍历到节点 3 时，两条路径的遍历 visited 状态是一样的，我们可以认为它们的结果是一样的。

这种搜索策略叫做记忆化搜索，基于记忆化搜索的想法，我们改造上面的程序

import java.util.Arrays;
import java.util.HashMap;
import java.util.stream.Collectors;

public class Solution {
    private int visited;
    private int[] start;
    private int[] end;
    private int rows;
    private int columns;
    private int left;
    private int[][] grid;
    private HashMap<String, Integer> memo= new HashMap<>();

    public int uniquePathsIII(int[][] grid) {
        this.grid = grid;
        this.rows = grid.length;
        this.columns = grid[0].length;
        this.visited = 0;
        this.start = new int[2];
        this.end = new int[2];
        this.left = rows * columns;

        for (int row = 0; row < rows; row++) {
            for (int column = 0; column < columns; column++) {
                if (grid[row][column] == 1) {
                    start[0] = row;
                    start[1] = column;
                    grid[row][column] = 0;
                } else if (grid[row][column] == 2) {
                    end[0] = row;
                    end[1] = column;
                    grid[row][column] = 0;
                } else if (grid[row][column] == -1) {
                    left--;
                }
            }
        }

        return dfs(start);
    }

    private int dfs(int[] v) {
        String strV = format(v);

        if (memo.containsKey(visited + strV)) {
            return memo.get(visited + strV);
        }

        visited = visited ^ (1 << (v[0] * columns + v[1]));
        left--;
        if (left == 0 && (v[0] == end[0] && v[1] == end[1])) {
            visited = visited ^ (1 << (v[0] * columns + v[1]));
            left++;
            memo.put(visited + strV, 1);
            return 1;
        }

        int res = 0;
        for (int[] w: adj(v[0], v[1])) {
            if ((visited & (1 << (w[0] * columns + w[1]))) == 0 && grid[w[0]][w[1]] != -1) {
                res += dfs(w);
            }
        }

        left++;
        visited = visited ^ (1 << (v[0] * columns + v[1]));
        memo.put(visited+strV, res);
        return res;
    }

    private Iterable<int[]> adj(int row, int column) {
        int[][] dirs = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
        return Arrays.stream(dirs)
                .map(dir -> new int[]{dir[0] + row, dir[1] + column})
                .filter(item -> item[0] < rows && item[0] >= 0 && item[1] < columns && item[1] >= 0)
                .collect(Collectors.toList());
    }

    private String format(int[] v) {
        int location = v[0] * columns + v[1];
        int first = location / 10;
        int second = location % 10;
        return "" + first + second;
    }
}