Article directory
- 1 Hamiltonian circuit
- 2 Implementation of Hamiltonian cycle algorithm
-
- 2.1 Conventional backtracking algorithm
- 2.2 Introduce variables to record the number of remaining unvisited nodes
- 3 Hamiltonian path problem
- 4 state compression
-
- 4.1 Check whether the i-th bit is 1
- 4.2 Set the i-th bit to 1 or 0
- 4.3 Summary
- 4.4 Application of state compression in Hamiltonian problem
- 5 Memoized search
-
- 5.1 The difference between memorized search and recursion
- 5.2 Implementation of memorized search – Likou980
1 Hamiltonian circuit
Solving the Hamiltonian Cycle
How to find out whether a Hamiltonian cycle exists in a graph?
One of the most intuitive ideas is to solve it by brute force. The idea of violent solution is also very simple: we traverse every vertex v of the graph, and then start from vertex v to see if we can find a Hamiltonian cycle.
The cost of brute force solution is equivalent to solving the total permutation problem, and its time complexity is O ( N ! ) O(N!) O(N!), where N is the number of vertices of the graph.
So besides brute force solving of the Hamiltonian cycle problem, is there a better algorithm?
Unfortunately, we can only try to achieve more optimizations based on brute force cracking, such as backtracking pruning, memorized search, etc. However, we have not yet found a polynomial-level algorithm to solve the Hamilton problem.
Usually, this type of problem is also called NP (Non-deterministic Polynomial) hard problem.
To sum up, to solve the Hamiltonian cycle, we can use the idea of backtracking + pruning to solve it.
2 Implementation of Hamiltonian cycle algorithm
2.1 Conventional backtracking algorithm
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; //Used to represent the last traversed vertex
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 & amp; & amp; allVisited()){<!-- --> //If you return to the starting point 0 and all points have been visited, the Hamil cycle is found
end = v;
return true;
}
// traceback
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]; //Previous node
}
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 Introduce variables to record the number of remaining unvisited nodes
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;
//The process of dfs records the number of remaining unvisited nodes
dfs(0, 0, G.V());
}
private boolean dfs(int v, int parent, int left){<!-- -->
visited[v] = true;
pre[v] = parent;
left --;
//Exit: if the unvisited node is 0 and there is an edge between the current node and the initial node
if(left == 0 & amp; & amp; 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 & amp; & amp; 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 Hamiltonian path problem
Depending on the starting location, the route will be different. However, the algorithm implementation is still the same. You only need to modify the constructor and pass in the starting position.
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 Status Compression
4.1 Check whether the i-th bit is 1
4.2 Set the i-th bit to 1 or 0
4.3 Summary
4.4 Application of state compression in Hamiltonian problem
In our code, we always use the Boolean visited array to record whether each vertex in the graph has been traversed.
In algorithm interviews, for NP-hard problems like Hamiltonian cycle/path, there is usually an input limit, and generally the graph given in the solution problem will not exceed 30 vertices.
In this way, during the algorithm written test/interview, we can perform state compression on the visited array to optimize the efficiency of algorithm class execution. We know that an int number has 32 bits, and each bit is either 1 or 0, which exactly corresponds to the Boolean true and false.
Therefore, we can simplify the visited array into a number, and each bit of the number is used to represent each true or false value of the visited array.
Let’s take a look at the code for dfs in our HamiltonLoop:
public HamiltonLoop_StateCompression(Graph G){<!-- -->
this.G = G;
pre = new int[G.V()];
end = -1;
int visited = 0; //Use a number of bits to indicate whether it has been visited
dfs(visited, 0, 0, G.V());
}
private boolean dfs(int visited, int v, int parent, int left){<!-- -->
visited + = (1 << v); //The vth position is set to 1
pre[v] = parent;
left --;
if(left == 0 & amp; & amp; G.hasEdge(v, 0)){<!-- -->
end = v;
return true;
}
for(int w: G.adj(v))
if((visited & amp; (1 << w)) == 0){<!-- --> //Check whether the w-th position of the number is 0
if(dfs(visited, w, v, left)) return true;
}
visited -= (1 << v); //Backtracking, the v-th position returns to 0
return false;
}
5 Memoized search
Memoized search is an implementation of dynamic programming.
In memoized search, when an algorithm needs to compute the result of a subproblem, it first checks whether that problem has already been computed. If it has been calculated, the stored result is returned directly; otherwise, the problem is calculated and the result is stored for future use.
For example, the definition of “Fibonacci Sequence” is:
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). If we use recursive algorithm to solve the
n
n
n Fibonacci numbers, the corresponding recursive process is as follows:
As can be seen from the figure: If you use ordinary recursive algorithm, you want to calculate
f
(
5
)
f(5)
f(5), needs to be calculated first
f
(
3
)
f(3)
f(3) and
f
(
4
)
f(4)
f(4), while calculating
f
(
4
)
f(4)
f(4) still needs to be calculated
f
(
3
)
f(3)
f(3). so
f
(
3
)
f(3)
f(3) has been calculated multiple times, and similarly
f
(
0
)
f(0)
f(0),
f
(
1
)
f(1)
f(1)、
f
(
2
)
f(2)
f(2) are calculated multiple times, resulting in a double-counting problem.
In order to avoid repeated calculations, while recursing, we can use a cache (array or hash table) to save the solved
f
(
k
)
f(k)
The result of f(k). As shown in the figure above, when recursive calls are used
f
(
k
)
f(k)
When f(k), first check whether the result has been calculated before. If it has been calculated, the value is returned directly from the cache without recursion, thus avoiding the problem of repeated calculations.
5.1 The difference between memorized search and recursion
Memoized search: “Top-down” problem solving, using a natural recursive way to write the process. During the process, the solution to each sub-problem is saved (usually saved in an array or hash table) to avoid repeated calculations.
Advantages: The code is clear and easy to understand, and can effectively handle some complex state transition equations. Some state transition equations are very complex. Using memory search, complex state transition equations can be split into multiple sub-problems, which can be solved through recursive calls.
Disadvantages: Stack overflow may occur due to excessive recursion depth.
Recursion: “Bottom-up” problem solving, writing the process in a loop, avoiding repeated calculations by saving the solution to each sub-problem (usually in an array or hash table).
Advantages: Avoiding the problem of excessive depth and no stack overflow problem. The calculation sequence is relatively clear and easy to implement.
Disadvantages: Unable to handle some complex state transition equations. Some state transition equations are so complex that if they are calculated using a recursive method, it will become very difficult to implement the code.
- Memory search problem solving steps
When we use memorized search to solve problems, the basic steps are as follows:
- Write the dynamic programming “state” and “state transition equation” of the problem. Define a cache (array or hash table) to hold solutions to subproblems.
- Define a recursive function to solve the problem. In the recursive function, first check whether the result that needs to be calculated already exists in the cache. If it exists, the result will be returned directly. Otherwise, the calculation will be performed, the result will be stored in the cache, and then the result will be returned.
- In the main function, the recursive function is called and the result is returned.
5.2 Implementation of memorized search – Likou 980
memo = new int[1 << (R * C)][R * C];
-
The first dimension is twice the number of vertices, because there are two possibilities for a location – visited/unvisited.
- Assuming the number of vertices is 1, the first dimension is: 0, 1.
Assuming the number of vertices is 2, the first dimension is 4: 00, 01, 10, 11.
- Assuming the number of vertices is 1, the first dimension is: 0, 1.
-
The second dimension represents the number of vertices and records whether the vertex corresponding to the current state has been visited.
package Chapter07_HamiltonLoop_And_StateCompression_And_MemoizationSearch.Memoization_Search;
import java.util.Arrays;
// Leetcode 980
class Solution {
private int[][] dirs = {{-1, 0}, {0, 1}, {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 & amp; & amp; 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) & amp; & amp; grid[nextx][nexty] == 0 & amp; & amp; (visited & amp; (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 & amp; & amp; x < R & amp; & amp; y >= 0 & amp; & amp; y < C;
}
}