Looking for a Tutor Near You?

Post Learning Requirement »
x

Choose Country Code

x

Direction

x

Ask a Question

x

x
x
For better view click here
x
Hire a Tutor
DISCOVER

Hamiltonian Paths

Loading...

Published in: Computer Science
1,184 Views

Algorithms To Solve Hamiltonian Graphs Also Known As Travelling Salesman Problem. 

Gaurav / Delhi

7 years of teaching experience

Qualification: B.Tech/B.E. (GGSIPU - 2007)

Teaches: Algebra, Computer Science, Mathematics, Physics, BCA Tuition, Electronics, IT, Computer, Electrical, Counting Skills, Writing Skills, Basic Computer, Coding & Programming, Science Projects, BCA Subjects, Networking

Contact this Tutor
  1. Hamiltonian cycle of minimum length in a given complete weighted graph G=(V,E) with weights cij=distance from node i to node j. Tour = a Hamiltonian cycle, a cycle that includes every vertex exactly once In graph G = (V,E): n=lVl, number of vertices; The graph may a directed multigraph (two arcs in opposite directions between every pair of nodes) or an undirected graph in which the distances may be symmetric: cij = cji, or not: cij cji for some. If the solution gives a total length 00, a Hamiltonian cycle does not exist in the given incomplete graph. The feasible solutions, the Hamiltonian cycles correspond to cyclic permutations of the vertex set. A divide-and-conquer-strategy. • The problem is handled is smaller parts in a sequential way so that small sub problems are solved first and their solutions are stored for future reference. •Larger sub problems are solved by a recursion formula from the smaller ones. • The next stage is calculated from the previous stage in a bottom-up fashion. • Finally, back-tracking through the table to obtain the complete solution. Algorithm: Input: Number of vertices n, nxn matrix C (Clj) 1. 2. 3. For i = 2 to n, set g(iO) = Fork = 1 to n-2 For all subset S CV {l} containing k vertices For all i S, min {cy + go, S—li})} jes := value of j that gave the Immmum (successor if vertex i in set S) Length of optimum TSP-tour: min {10})} value of j that gave the mimmum (successor of vertex 1), The array p has n rows for all the vertices and columns for all subsets of V—{l}, p(i,S) = the first vertex after i on a shortest path from i to 1 that passes through all the vertices of S exactly once. The optimal tour from the array p: The first vertex after 1: p(l, V—{l}) = k The second: p(k, V—{l,k}) etc. Complexity = number of operations: T(n) = O(n2 2 n ) Memory used in storing the arrays: M(n) = O(n2n ).

Need a Tutor or Coaching Class?

Post an enquiry and get instant responses from qualified and experienced tutors.

Post Requirement

Related Study Notes

Upload Study Notes

If you have your own Study Notes which you think can benefit others, please upload on LearnPick. For each approved Study Note you will get 100 Credit Points and 100 Activity Score which will increase your profile visibility.

Upload Now
Home > Study Notes > Hamiltonian Paths