Exponential Algorithms for Finding Hamiltonian Cycles and Paths¶
In this section, we will examine 4 algorithms along with their implementations. These 4 algorithms are very similar to each other but have subtle differences that require careful attention to these distinctions and the fundamental idea behind each one.
Hamiltonian Path¶
Hamiltonian Path Algorithms¶
def hamiltonian_path(graph, start, path=[]):
# Hamiltonian algorithm implementation goes here
path = path + [start]
if len(path) == len(graph.nodes):
return path
for node in graph.neighbors(start):
if node not in path:
new_path = hamiltonian_path(graph, node, path)
if new_path:
return new_path
return None
Algorithms for finding Hamiltonian paths attempt to discover a path that visits every vertex in a graph exactly once. One common approach is using backtracking with pruning which systematically explores potential paths while eliminating impossible branches early.
توجه
The Hamiltonian path problem is NP-Complete, meaning for large graphs, finding an exact solution can be computationally prohibitive. In such cases, heuristic approaches or approximations are often used.
Algorithm 1¶
From previous sections, we understood that there is no necessary and sufficient condition for finding Hamiltonian cycles and paths. In other words, this is an NP problem, and no polynomial-time algorithm exists for it. Now we attempt to present an exponential algorithm.
Using dynamic programming, we define \(dp_{mask, a, b}\) as a boolean array indicating whether there exists a Hamiltonian path using vertices in the set \(mask\), starting from vertex \(a\) and ending at vertex \(b\).
To update this function, it suffices to enumerate over the vertex preceding \(b\). Let this vertex be \(c\). It is necessary for \(c\) to be a member of the set \(mask\), and there must be an edge between \(b\) and \(c\). Finally, to determine the existence of a Hamiltonian path, we can check all \(dp_{2^n-1,i,j}\) values for all possible \(i\) and \(j\).
Thus, the algorithm implementation will be as follows:
#define bit(n,k) (((n)>>(k))&1)
const int maxn = 16;
bool dp[1<<maxn][maxn][maxn];
bool adj[maxn][maxn];
int main(){
// voroodi gereftan graph
int n;
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin >> adj[i][j];
// mohasebe dp
for(int mask = 1; mask < (1<<n); mask++){
if(__builtin_popcount(mask) == 1){
dp[mask][__builtin_ctz(mask)][__builtin_ctz(mask)] = 1;
continue;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j || bit(mask, i) == 0 || bit(mask, j) == 0)
continue;
for(int k = 0; k < n; k++){
if(k == j || bit(mask, k) == 0 || adj[k][j] == 0)
continue;
dp[mask][i][j] |= dp[mask ^ (1<<j)][i][k];
}
}
}
}
bool ans = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
ans |= dp[(1<<n)-1][i][j];
if(ans)
cout << "YES\n";
else
cout << "NO\n";
return 0;
}
As you can see, we presented an algorithm with time complexity \(O(2^n * n^3)\).
Algorithm 2¶
Now, we aim to present a better algorithm by modifying the definition of the recursive function.
Assume that \(dp_{mask,u}\) equals a subset of vertices such as \(mask2\) where for each member \(v\) in it, there exists a Hamiltonian path from \(u\) to \(v\) within the subset of vertices \(mask\).
To update this recursive function, we must perform state branching based on the vertex that comes after \(u\). Ultimately, to find the solution to the problem, we need to check \(dp_{2^n-1,u}\) for all possible \(u\).
#define bit(n,k) (((n)>>(k))&1)
const int maxn = 16;
int dp[1<<maxn][maxn];
bool adj[maxn][maxn];
int main(){
// voroodi gereftan graph
int n;
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin >> adj[i][j];
// mohasebe dp
for(int mask = 1; mask < (1<<n); mask++){
if(__builtin_popcount(mask) == 1){
dp[mask][__builtin_ctz(mask)] = mask;
continue;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j || bit(mask, i) == 0 || bit(mask, j) == 0 || adj[i][j] == 0){
continue;
}
dp[mask][i] |= dp[mask ^ (1<<i)][j];
}
}
}
bool ans = 0;
for(int i = 0; i < n; i++)
if(dp[(1<<n)-1][i] != 0){
ans = 1;
if(ans)
cout << "YES\n";
else
cout << "NO\n";
return 0;
}
# تابعی برای پیدا کردن زیرگراف کامل
def find_complete_subgraph(graph):
# لیست تمام رأسها
vertices = list(graph.keys())
n = len(vertices)
# بررسی تمام زیرمجموعههای ممکن
for i in range(1, 2**n):
subset = [vertices[j] for j in range(n) if (i >> j) & 1]
# بررسی کامل بودن زیرگراف
is_complete = True
for v in subset:
for u in subset:
if v != u and u not in graph[v]:
is_complete = False
break
if not is_complete:
break
if is_complete:
print(f"Complete subgraph found: {subset}")
Therefore, we succeeded in reducing the algorithm's time complexity to \(O(2^n \times n^2)\).
Hamiltonian Cycle¶
A Hamiltonian cycle is a cycle in a graph that visits every vertex exactly once and returns to the starting vertex. This concept is named after the mathematician William Rowan Hamilton. Determining whether a Hamiltonian cycle exists in a graph is a classic NP-complete problem.
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# Define the graph using a dictionary
def hamiltonian_cycle(graph, start, current, visited, path):
if len(visited) == len(graph):
if start in graph[current]:
return path + [start]
else:
return None
for neighbor in graph[current]:
if neighbor not in visited:
result = hamiltonian_cycle(graph, start, neighbor, visited | {neighbor}, path + [current])
if result:
return result
return None
The code above demonstrates a recursive approach to find a Hamiltonian cycle in a graph represented as a dictionary. The algorithm uses backtracking to explore all possible paths and checks if a valid cycle exists.
### Key Notes: - If a graph contains a Hamiltonian cycle, it is called a Hamiltonian graph. - Unlike Eulerian cycles, there is no simple necessary and sufficient condition for the existence of a Hamiltonian cycle. - Practical applications include optimization problems in logistics, circuit design, and DNA sequencing.
Algorithm 1¶
To check whether a graph contains a Hamiltonian cycle, it suffices to choose an arbitrary vertex like \(a\). Then for all neighbors of vertex \(a\), such as \(b\), we determine whether there exists a Hamiltonian path from \(a\) to \(b\). (If such a path exists, first traverse the Hamiltonian path then traverse the edge \(ab\)).
This can be implemented using the recursive function we described in Algorithm 1 of the previous section.
Now we try to improve the algorithm. Since vertex \(a\) was chosen arbitrarily, we conjecture that by redefining the recursive function, we can achieve an algorithm with better time complexity.
We define \(dp_{mask,u}\) as a boolean array indicating whether starting from vertex \(u\), we can visit all vertices in set \(mask\) and finally reach the smallest member of set \(mask\).
The difference from the previous definition is that now the endpoint of the Hamiltonian path is determined by \(mask\), eliminating the need to add an extra dimension to the state.
For updates, you can perform case analysis on the vertex following \(u\).
#include<bits/stdc++.h>
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
const int maxn = 16;
bool dp[1<<maxn][maxn];
bool adj[maxn][maxn];
int main(){
// voroodi gereftan graph
int n;
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin >> adj[i][j];
// mohasebe dp
for(int mask = 1; mask < (1<<n); mask++){
if(__builtin_popcount(mask) == 1){
dp[mask][__builtin_ctz(mask)] = 1;
continue;
}
int low_bit = __builtin_ctz(mask);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j || bit(mask, i) == 0 || bit(mask, j) == 0 || i == low_bit || adj[i][j] == 0)
continue;
dp[mask][i] |= dp[mask ^ (1<<i)][j];
}
}
}
bool ans = 0;
for(int i = 1; i < n; i++){ // i != 0
if(dp[(1<<n)-1][i] && adj[0][i])
ans = 1;
}
if(ans)
cout << "YES\n";
else
cout << "NO\n";
return 0;
}
So we arrived at an algorithm with time complexity \(O(2^n * n^2)\).
Algorithm 2¶
Now, inspired by Algorithm 2 from the previous section, we improve the time complexity of the solution.
We define \(dp_{mask}\) as a subset of vertices (like \(mask2\)) where from every vertex \(u\) in \(mask2\), we can start, visit all vertices in the \(mask\) set, and finally reach the smallest member of \(mask\).
To update, we can perform state transitions based on the starting vertex of the Hamiltonian path.
Note the following code. The array \(adj\_mask_u\) represents the set of vertices adjacent to vertex \(u\).
#define bit(n,k) (((n)>>(k))&1)
const int maxn = 16;
int dp[1<<maxn];
int adj_mask[maxn];
int main(){
// voroodi gereftan graph
int n;
cin >> n;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
bool x;
cin >> x;
if(x){
adj_mask[i] |= 1<<j;
}
}
}
// mohasebe dp
for(int mask = 1; mask < (1<<n); mask++){
if(__builtin_popcount(mask) == 1){
dp[mask] = mask;
continue;
}
int low_bit = __builtin_ctz(mask);
for(int i = 0; i < n; i++){
if(bit(mask, i) == 0 || i == low_bit)
continue;
if(dp[mask ^ (1<<i)] & adj_mask[i])
dp[mask] |= 1<<i;
}
}
bool ans = 0;
if(dp[(1<<n)-1] != 0)
ans = 1;
if(ans)
cout << "YES\n";
else
cout << "NO\n";
return 0;
}
مسئله فروشنده دورهگرد (الگوریتم پویا)¶
در فصل قبل دیدیم که چگونه میتوان مسئله TSP را با استفاده از برنامهنویسی پویا حل کرد. در این بخش میخواهیم پیادهسازی و تحلیل این الگوریتم را دقیقتر بررسی کنیم.
کد زیر پیادهسازی الگوریتم برنامهنویسی پویا برای مسئله TSP است:
def tsp_dp(graph):
n = len(graph)
# To generate all possible subsets that include node 0
all_sets = [[]] * (2 ** n)
all_sets[0] = [0]
# Initialize memoization table
memo = {}
for i in range(1, n):
memo[(frozenset([0, i]), i)] = graph[0][i]
# Fill memo table using DP
for size in range(2, n):
for subset in combinations(range(1, n), size):
subset = frozenset(subset | {0})
for j in subset:
if j == 0:
continue
# Find minimum path through all nodes in subset ending at j
memo[(subset, j)] = min(
memo[(subset - {j}, k)] + graph[k][j]
for k in subset if k != j
)
# Return minimum Hamiltonian cycle
return min(
memo[(frozenset(range(n)), j)] + graph[j][0]
for j in range(1, n)
)
نمایش گرافی از مسئله TSP با ۴ شهر¶
تحلیل پیچیدگی: تعداد زیرمجموعههای ممکن \(2^{n-1}\) است و برای هر زیرمجموعه حداکثر n گره مقصد داریم. بنابراین پیچیدگی زمانی کل الگوریتم \(O(n^2 * 2^n)\) خواهد بود. با بهینهسازیهای انجامشده (مانند استفاده از بیتماسکها و حافظه پویا) در عمل به \(O(2^n * n)\) میرسیم.
نکته مهم: این الگوریتم برای n ≤ 20 عملی است، اما برای اندازههای بزرگتر نیاز به روشهای تقریبی یا مکاشفهای داریم.
توجه
در پیادهسازی فوق از ترکیب مجموعههای یخزده (frozenset) و دیکشنری برای ذخیرهسازی حالتها استفاده شده است. این تکنیک امکان استفاده از ساختارهای غیرقابل تغییر را بهعنوان کلید در جدول ممویزاسیون فراهم میکند.
Therefore, we arrived at an algorithm with a time complexity of \(O(2^n * n)\).
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at آوریل 19, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
