1 哈密尔顿回路
求解哈密尔顿回路
如何求解一个图是否存在哈密尔顿回路呢?
一个最直观的想法就是暴力求解。暴力求解的思路也很简单:我们遍历图的每一个顶点 v,然后从顶点 v 出发,看是否能够找到一条哈密尔顿回路。
暴力求解的代价同求解全排列问题是等价的,其时间复杂度为 O ( N ! ) O(N!) O(N!),N 为图的顶点的个数。
那么除了暴力求解哈密尔顿回路问题,是否存在更好的算法?
很遗憾我们只能在暴力破解的基础上,尽量去做到更多的优化,譬如回溯剪枝,记忆化搜索等,但是,还没有找到一种多项式级别的算法来解决哈密尔顿问题。
通常,这类问题也被称为 NP(Non-deterministic Polynomial)难问题。
综上所述,求解哈密尔顿回路,我们可以采用回溯+剪枝的思想来进行求解。
2 哈密尔顿回路算法实现
2.1 常规回溯算法
package Chapter07_Hamilton_Loop_And_Path.Hamilton_Loop;
import java.util.ArrayList;
import java.util.Collections;
public class HamiltonLoop {
private Graph G;
private boolean[] visited;
private int[] pre;
private int end; //用来表示最后一个被遍历的顶点
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()){ //如果回到起始点0并且所有的点都被访问过了,则找到了哈密尔回路
end = v;
return true;
}
// 回溯
visited[v] = false;
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;
}
private boolean allVisited(){
for(int v = 0; v < G.V(); v ++)
if(!visited[v]) return false;
return true;
}
public static void main(String[] args){
Graph g = new Graph("g9.txt");
HamiltonLoop hl = new HamiltonLoop(g);
System.out.println(hl.result());
Graph g2 = new Graph("g10.txt");
HamiltonLoop hl2 = new HamiltonLoop(g2);
System.out.println(hl2.result());
}
}
2.2 引入变量记录剩余未访问的节点数量
package Chapter07_Hamilton_Loop_And_Path.Hamilton_Loop;
import java.util.ArrayList;
import java.util.Collections;
public class HamiltonLoop_Optimization {
private Graph G;
private boolean[] visited;
private int[] pre;
private int end;
public HamiltonLoop_Optimization(Graph G){
this.G = G;
visited = new boolean[G.V()];
pre = new int[G.V()];
end = -1;
//dfs的过程记录剩余未访问的节点的数量
dfs(0, 0, G.V());
}
private boolean dfs(int v, int parent, int left){
visited[v] = true;
pre[v] = parent;
left --;
//出口:如果未访问的节点是0,并且当前节点和初始节点有边
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;
}
// else if(w == 0 && left == 0){
// end = v;
// return true;
// }
visited[v] = false;
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("g9.txt");
HamiltonLoop hl = new HamiltonLoop(g);
System.out.println(hl.result());
Graph g2 = new Graph("g10.txt");
HamiltonLoop hl2 = new HamiltonLoop(g2);
System.out.println(hl2.result());
}
}
3 哈密尔顿路径问题
根据出发位置的不同,路径也会不一样。但是算法实现还是一致的,只需要修改构造函数,传入起点位置。
package Chapter07_Hamilton_Loop_And_Path.Hamilton_Loop;
import java.util.ArrayList;
import java.util.Collections;
public class HamiltonPath {
private Graph G;
private int s;
private boolean[] visited;
private int[] pre;
private int end;
public HamiltonPath(Graph G, int s){
this.G = G;
this.s = s;
visited = new boolean[G.V()];
pre = new int[G.V()];
end = -1;
dfs(s, s, G.V());
}
private boolean dfs(int v, int parent, int 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;
return false;
}
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(s);
Collections.reverse(res);
return res;
}
public static void main(String[] args){
Graph g = new Graph("g10.txt");
HamiltonPath hp = new HamiltonPath(g, 0);
System.out.println(hp.result());
HamiltonPath hp2 = new HamiltonPath(g, 1);
System.out.println(hp2.result());
}
}
4 状态压缩
4.1 查看第i位是否为1
4.2 设置第i位是为1或者0
4.3 小结
4.4 状态压缩在哈密尔顿问题中的应用
在我们的代码中,一直都使用布尔型的 visited 数组
来记录图中的每一个顶点是否有被遍历过。
在算法面试中,对于像哈密尔顿回路/路径这样的 NP 难问题,通常都会有输入限制,一般情况下,求解问题中给定的图不会超过 30 个顶点。
这样,在算法笔试/面试中,我们就可以对 visited 数组进行状态压缩来优化算法类执行的效率。我们知道一个 int 型的数字有 32 位,每一位不是 1 就是 0,这正好对应了布尔型的 true 和 false。
所以,我们可以将 visited 数组简化成一个数字
,该数字的每一个比特位
用来表示 visited 数组的每一个 true 或 false 值。
来看一下我们的 HamiltonLoop 中 dfs 的代码:
public HamiltonLoop_StateCompression(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){
visited += (1 << v); //第v位置设置为1
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个位置是否为 0
if(dfs(visited, w, v, left)) return true;
}
visited -= (1 << v); //回溯,第v位置恢复为0
return false;
}
5 记忆化搜索
记忆化搜索是动态规划的一种实现方式。
在记忆化搜索中,当算法需要计算某个子问题的结果时,它首先检查是否已经计算过该问题。如果已经计算过,则直接返回已经存储的结果;否则,计算该问题,并将结果存储下来以备将来使用。
举个例子,比如「斐波那契数列」的定义是: f ( 0 ) = 0 , f ( 1 ) = 1 , f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(0) = 0, f(1) = 1, f(n) = f(n - 1) + f(n - 2) f(0)=0,f(1)=1,f(n)=f(n−1)+f(n−2)。如果我们使用递归算法求解第 n n n 个斐波那契数,则对应的递推过程如下:
从图中可以看出:如果使用普通递归算法,想要计算
f
(
5
)
f(5)
f(5),需要先计算
f
(
3
)
f(3)
f(3) 和
f
(
4
)
f(4)
f(4),而在计算
f
(
4
)
f(4)
f(4) 时还需要计算
f
(
3
)
f(3)
f(3)。这样
f
(
3
)
f(3)
f(3) 就进行了多次计算,同理
f
(
0
)
f(0)
f(0)、
f
(
1
)
f(1)
f(1)、
f
(
2
)
f(2)
f(2) 都进行了多次计算,从而导致了重复计算问题。
为了避免重复计算,在递归的同时,我们可以使用一个缓存(数组或哈希表)来保存已经求解过的 f ( k ) f(k) f(k) 的结果。如上图所示,当递归调用用到 f ( k ) f(k) f(k) 时,先查看一下之前是否已经计算过结果,如果已经计算过,则直接从缓存中取值返回,而不用再递推下去,这样就避免了重复计算问题。
5.1 记忆化搜索与递推区别
记忆化搜索:「自顶向下」的解决问题,采用自然的递归方式编写过程,在过程中会保存每个子问题的解(通常保存在一个数组或哈希表中)来避免重复计算。
优点:代码清晰易懂,可以有效的处理一些复杂的状态转移方程。有些状态转移方程是非常复杂的,使用记忆化搜索可以将复杂的状态转移方程拆分成多个子问题,通过递归调用来解决。
缺点:可能会因为递归深度过大而导致栈溢出问题。
递推:「自底向上」的解决问题,采用循环的方式编写过程,在过程中通过保存每个子问题的解(通常保存在一个数组或哈希表中)来避免重复计算。
优点:避免了深度过大问题,不存在栈溢出问题。计算顺序比较明确,易于实现。
缺点:无法处理一些复杂的状态转移方程。有些状态转移方程非常复杂,如果使用递推方法来计算,就会导致代码实现变得非常困难。
- 记忆化搜索解题步骤
我们在使用记忆化搜索解决问题的时候,其基本步骤如下:
- 写出问题的动态规划「状态」和「状态转移方程」。 定义一个缓存(数组或哈希表),用于保存子问题的解。
- 定义一个递归函数,用于解决问题。在递归函数中,首先检查缓存中是否已经存在需要计算的结果,如果存在则直接返回结果,否则进行计算,并将结果存储到缓存中,再返回结果。
- 在主函数中,调用递归函数并返回结果。
5.2 记忆化搜索的实现 - 力扣980
memo = new int[1 << (R * C)][R * C];
-
第一个维度是顶点数量的2倍,因为一个位置有两种可能——访问过/未访问过。
- 假设顶点数量为1,则第一个维度未2: 0, 1.
假设顶点数量为2,则第一个维度未4: 00, 01, 10, 11.
- 假设顶点数量为1,则第一个维度未2: 0, 1.
-
第二个维度表示顶点数量,记录当前状态对应顶点是否被访问过。文章来源:https://www.toymoban.com/news/detail-756648.html
文章来源地址https://www.toymoban.com/news/detail-756648.html
package Chapter07_HamiltonLoop_And_StateCompression_And_MemoizationSearch.Memoization_Search;
import java.util.Arrays;
// Leetcode 980
class Solution {
private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
private int R, C;
private int[][] grid;
private int start, end;
private int[][] memo;
public int uniquePathsIII(int[][] grid) {
this.grid = grid;
R = grid.length;
C = grid[0].length;
int left = R * C;
memo = new int[1 << (R * C)][R * C];
for(int i = 0; i < memo.length; i ++)
Arrays.fill(memo[i], -1);
for(int i = 0; i < R; i ++)
for(int j = 0; j < C; j ++)
if(grid[i][j] == 1){
start = i * C + j;
grid[i][j] = 0;
}
else if(grid[i][j] == 2){
end = i * C + j;
grid[i][j] = 0;
}
else if(grid[i][j] == -1)
left --;
int visited = 0;
return dfs(visited, start, left);
}
private int dfs(int visited, int v, int left){
if(memo[visited][v] != -1) return memo[visited][v];
visited += (1 << v);
left --;
if(v == end && left == 0){
visited -= (1 << v);
memo[visited][v] = 1;
return 1;
}
int x = v / C, y = v % C;
int res = 0;
for(int d = 0; d < 4; d ++){
int nextx = x + dirs[d][0], nexty = y + dirs[d][1];
int next = nextx * C + nexty;
if(inArea(nextx, nexty) && grid[nextx][nexty] == 0 && (visited & (1 << next)) == 0)
res += dfs(visited, next, left);
}
visited -= (1 << v);
memo[visited][v] = res;
return res;
}
private boolean inArea(int x, int y){
return x >= 0 && x < R && y >= 0 && y < C;
}
}
到了这里,关于图论10-哈密尔顿回路和哈密尔顿路径+状态压缩+记忆化搜索的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!