Loading...
Menu

Vastu Moolak Ganit

Input to the algorithm is a table consisting of two columns, namely, an edge and its weight or distance between two cities as vertices of the edge. Now for ‘n’ cities, we have total n*(n-1) edges, considering two directions for each edge as separate edge. This table (we may call as ‘edge table’) is sorted in ascending order of the weights/distances of edges. We represent an edge in the edge table as city1.city2, where city1 and city2 are the vertices of a particular edge. This representation helps us later on in the algorithm. Now for each of the edges of this edge table, we perform following steps:

 

1. tour := nil

 

2. firstEdge := selectedEdge

 

3. Repeat the following steps  for each of the first ‘(n-1)’ edges of a tour/Hamiltonian cycle:

 

a) Scan the edge table linearly from the top, looking for  the earliest match to ‘selectedEdge’ with the constraints that city1 of ‘matchedEdge’ must match with city2 of ‘selectedEdge’ and city2 of ‘matchedEdge’ must not match with city1 of ‘selectedEdge’ as well as any other city present in ‘tour’ so far.

 

b) tour := matchedEdge + tour

 

c) selectedEdge :=  matchedEdge

 

4. Scan the edge table linearly from the top, looking for the match to ‘selectedEdge’ with the condition that city1 of ‘matchedEdge’ must match with city2 of ‘selectedEdge’ and city2 of the ‘matchedEdge’ must also match with the city1 of ‘firstEdge’.

 

5. Length of the Hamiltonian cycle = sum of weights of edges stored in ‘tour’ + weight of last edge found in step 4.

 

Length of all n*(n-1) Hamiltonian cycles are found as above and optimal Hamiltonian cycle is minimum of these lengths.

 


Vastu Moolak Ganit

It is about a new type of mathematics. It is based on a new Indian philosophy. It promises to solve all the unsolved problems of computer science and mathematics.

  • ISBN: 9781370653713
  • Author: Alok Chauhan
  • Published: 2016-09-11 20:40:29
  • Words: 276
Vastu Moolak Ganit Vastu Moolak Ganit