Summary of Class 13. Hamiltonian path

Success is not final, failure is not fatal: it is the courage to continue that counts.

A Hamiltonian path or traceable path is a path that visits each vertex of the graph exactly once.
A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian Path such that there is an edge (in graph) from the last vertex to the first vertex of the Hamiltonian Path. 

0. Permutation and combination

set and subset:
sequence and subsequence:
https://www.mathsisfun.com/sets/sets-introduction.html
http://www.mathsisfun.com/algebra/sequences-series.html
permutation: the act of arranging all the members of a set into some sequence or order
combination: a selection of items from a collection without order

Problem: print all the combination of "abcd".  backtracking-like method and bitmask method.
Solution: recursive, bit-mask

1. brute force (STL next_permutation)

Hamiltonian cycle search : permutation of all nodes (n!)
STL: next_permutation(begin(), end()), bidirectional iterator

int adj[MAXN][MAXN];
bool hamiltonian (int n){
    int v[n];
    for (int i=0; i<n; i++)
        v[i] =i;
    do { 
        bool valid=true;
        for(int i=0; i<v.size()-1; i++) {
            if(adj[v[i]][v[i+1]] == false){
                valid=false;
                break;
            }         
        }   

        if(valid)
            return true;
    } while(next_permutation(v, v+n));
    return false;
}

2. backtracking

void hamCycleUtil(bool graph[V][V], bool visited[V], vector<int> &path, int pos, int times)
void hamCycle(bool graph[V][V])

3. DP (I think it has little value in application)

Invented by Bellman, Held, and Karp.  Good material for learning DP.

My explanation:
For every subset S of vertices check whether there is a path that visits "EACH and ONLY" the vertices in S exactly once and ends at a vertex v.  This is the state.  I use S(X) to represent the possible hamitonian path if it exists (true).

state: dp[i][j] 
    i: the ending vertex of hamitonian path
    j: the subset of all vertices.  You can use the bitmask to represent it.

initial state:
    For every subset S(x), which only includes one vertex x, it is true, because the hamitonian path starts at x and ends at x.

state transition:
    for every vertex y, if subset S does not include it has hamitonian path, which ends at vertext x, and there is a connection betweek x and y, the subset {S(x), y} will have a hamitinian path, which ends at y.

result:
    for n vertex, 2^n-1 will have all the vertices in it.  If any of them is true, there is hamitonian path

bool check_using_dp(int adj[][MAXN], int n){
    bool dp[MAXN][1<<MAXN]={0};
    for(int i=0; i<n; i++)
        dp[i][1<<i]=true;

    for(int i=0; i<(1<<n); i++){
        for(int j=0; j<n; j++)
            if(i&(1<<j)){
                for(int k=0; k<n; k++)
                    if(i&(1<<k) && adj[k][j] && k!=j && dp[k][i^(1<<j)]){
                        dp[j][i]=true;
                        break;
                    }   
            }   
    }   

    for(int i=0; i<n; i++)
        if(dp[i][(1<<n)-1])
            return true;

    return false;
}   

Question: Why DP is faster than Brute Force method in this case?

Comments

Post a Comment

Popular posts from this blog

Summary of Class 12: Eulerian graph / Eulerian path (USACO 3.3)

The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1736 laid the foundations of graph theory and prefigured the idea of topology. Eulerian Cycle ( Eulerian circuit, closed eulerian trail/path ) Eulerian trail (or Eulerian path) is a trail in a finite graph which visits every edge exactly once.  An Eulerian circuit or Eulerian cycle is an Eulerian trail which starts and ends on the same vertex. A eulerian cycle exists on an undirected graph if and only if the graph is connected  and every vertex has an even degree. A eulerian cycle exists on a directed graph if and only if the graph is connected  and the in-degree of every vertex is equal to its out-degree. (Chinese postman problem) Eulerian Path An undirected graph has Eulerian Path if following two conditions are true. a) the graph is connected b) If zero or two vertices have odd degree and all other vertices have...
Read more

Summary of Class 15 DAG -- Topological Sorting (USACO 4.4)

“To improve is to change; to be perfect is to change often.”  ―  Winston S. Churchill Version Control (or Revision control or source control): Version Control System (VCS) Concurrent Version System (CVS) Subversion (SVN) git command:     git add . (or file)     git commit -m "msg"     git push origin <branch-name> https://services.github.com/on-demand/downloads/github-git-cheat-sheet/ Review of SCC, DFS, BFS SCC: A digraph is strongly connected if every two vertices are  mutually reachable . A strong component of a digraph G is a maximal strongly connected subdigraph of G. Equivalently, a strong component is a subdigraph induced on a maximal set of mutually reachable vertices. Graph DFS: stack-based :  (for loop with visited vertices)     tree edge,     forward edge    ...
Read more

Summary of Class 14 Strongly Connected Components (SCC)

Try not to become a man of success, but rather try to become a man of value.   - Albert Einstein 不自见故明；不自是故彰；不自伐故有功；不自矜 故长。 夫唯不争，故天下莫能与之争。 Data Structure Review (C++ STL) : array(array), dynamic array (vector) doubly linked list (list), singly linked list (forward_list) stack, queue, priority_queue (heap structure) binary tree, binary search tree (BST) graph (adjacent list, adjacent matrix, edge list) union-find data structure  A directed graph is strongly connected if there is a path between all pairs of vertices. https://en.wikipedia.org/wiki/Strongly_connected_component Kosaraju’s algorithm 1) Do DFS and push the vertex to stack S.      For each vertex u of the graph, mark u as unvisited in visited[] array. Let Stack S be empty.      For each vertex u of the graph do dfs(u, visited, S), where dfs() is the recursive subroutine:          mark u as visited:   ...
Read more