All the JNTUH Pool: BSAR University

Convocation Photos of ME CSE BS Abdur Rahman Crescent University

Imraan Professor(Hyderabad MIT)

Raja Professor(Chennai)

Renjith Professor(Chennai)

Dinesh Asst. Professor(Chennai)

Giri Professor(Chennai)

it's classic traveling salesman problem using dynamic programming.
the peseudocode is given :
Inputs: a weighted, directed graph, and n, the number of vertices in the graph. The graph is represented by a two-dimensional array W, which has both its rows and columns indexed from 1 to n, where W [i] [j] is the weight on the edge from ith vertex to the jth vertex.

Outputs: a variable minlength, whose value is the length of an optimal tour, and a two-dimensional array P from which an optimal tour can be constructed. P has its rows indexed from 1 to n and its columns indexed by all subsets of V − {v1}. P [i] [A] is the index of the first vertex after vi on a shortest path from vi to v1 that passes through all the vertices in A exactly once.
void travel (int n,
 const number W [] [],
 index P [] [],
 number & minlength)
{
 index i, j, k;
 number D [1 .. n] [subset of V - {v1}];

 for (i = 2; i <= n; i++)
 D [i] [⊘] = W[i] [1];
 for (k = 1; k <= n - 2; k++)
 for (all subsets A ⊆ V - {v1} containing k vertices)
 for (i such that i ≠ 1 and vi is not in A){
 D [i] [A] = minimum (W [i] [j] + D [j] [A - {vj}]);
 j: [vj ∊ A
 P[i] [A] = value of j that gave the minimum;
 }
 D [1] [V - {v1}] = minimum (W[1] [j] + D[j] [V - {v1, vj}]);
 2 ≤ j ≤ n
 P[1] [V - {v1}] = value of j that gave the minimum;
 minlength = D[1] [V - {v1}];
}//Concept

Program

#include <iostream>
#include <cmath>

using namespace std;

int** C; // Optimums-Matrix
int** d; // Distanzen zwischen den Städten
int iN; // Anzahl Städte

int NumberOfSetBits(int i); // Zählt die gesetzten Bits in einem Integer

int main()
{
 /** Anzahl Städte einlesen **/
 scanf("%i",&iN);

 /** Initialisieren **/
 C = new int*[iN+1]; // n Zahlen ohne 0 -> iN+1
 for(int i=1; i <= iN; i++) // Bis und mit iN ohne 0
 C[i] = new int[(1<<iN)]; // 2^iN ohne 0, jedoch ist 2^iN bereits der komplette Weg (7 = 111 oder 15 = 1111); 1<<x = 2^x

 d = new int*[iN+1]; // n Zahlen ohne 0
 for(int i=1; i <= iN; i++) // Bis und mit iN ohne 0
 d[i] = new int[iN+1]; // n Zahlen ohne 0

 /** Eingabe **/
 for(int i=1; i <= iN; i++) // Bis und mit iN ohne 0
 for(int j=1; j <= iN; j++) // Bis und mit iN ohne 0
 {
 scanf("%i", &d[i][j]); // Distanzen einlesen
 }

 /*********************************************
 * Algorithmus *
 *********************************************/

 for(int k=2; k <= iN; k++) // Ohne 0 & 1 für k, bis und mit iN
 {
 for(int c=2; c <= iN; c++)
 C[c][1+(1<<(k-1))] = d[1][k]; // Stadt 1 + Stadt k
 }

 for(int s=3; s <= iN; s++) // ohne 0,1,2
 {
 for(int S=(1<<(s-2)); S < (1<<iN); S++) // Beginne bei 2^(s-2), ende bei 2^iN
 if(NumberOfSetBits(S) == s) // Menge mit der Mächtigkeitszahl s
 for(int k=2; k <= iN; k++) // Alle Städte durchgehen
 if((S&(1<<(k-1))) > 0) // Wenn Stadt k in Menge S vorkommt... && S >= (1<<(k-1))
 {
 C[k][S]=9999999;
 for(int m=2; m <= iN; m++) // Zweite Verbindungsstadt finden
 {
 if(m == k || (S&(1<<(m-1))) == 0)
 continue;
[k][S] = min([m][S-(1<<(k-1))]+d[m][k], [k][S]); //
 break;
 }
 }
 }

 /** Optimum berechnen **/
 int opt = 9999999;
 for(int k=2; k <= iN; k++)
 {
 opt = min(C[k][(1<<(iN))-1]+d[1][k], opt);
 }

 printf("%i\n",opt);

 // Pausieren
 //system("pause");

 /** // Auskommentieren um die Optimums-Matrix auszugeben
 for(int i=1; i <= iN; i++)
 {
 for(int j=1; j < (1<<iN); j++)
 {
 printf("%i ",(C[i][j]<0?0:C[i][j]));
 }
 printf("\n\n");
 }**/

 return 0;
}

/** Bit-Zähler nach dem 'parallel'-Algorithmus (oder 'variable-precision SWAR'-Algorithmus) **/
int NumberOfSetBits(int i)
{
 i = i - ((i >> 1) & 0x55555555);
 i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
 return ((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

## This project is for Travelling Salesman problem using dynamic programming for 1st year BTECH

#include<stdio.h>
#include<conio.h>
#include
#define max 100
#define infinity 999
int tspdp(int c[][max],int tour[],int star,int n);
int main()
{
int n;
int i,j,c[max][max];
int tour[max],cost;
cout<<"Travelling Salesman Problem Using Dynamic Programming\n";
cout<<"\nEnter number of cities to traverse";
cin>>n;
cout<<"Enter cost matrix\n"<

for(i=0;i
for(j=0;j
{

cin>>c[i][j];
if(c[i][j]==0)
c[i][j]=999;
}

for(i=0;i<j;i++)
tour[i]=i;
cost=tspdp(c,tour,0,n);
cout<<"Minimum Cost:"<<
cout<<"Tour:\n";
for(i=0;i<=j;i++)
cout<<<"-";
cout<<"1\n";
getch();
return 0;
}

int tspdp(int c[][max],int tour[],int start,int n)
{
int i,j,temp[max],mintour[max];
int mincost,ccost;

if(start==n-2)
return c[tour[n-2]][tour[n-1]]+c[tour[n-1]][0];
mincost=infinity;
for(i=start+1;i
{
for(j=0;j
temp[j]=tour[j];
temp[start+1]=tour[i];
temp[i]=tour[start+1];
if(c[tour[start]][tour[i]]+(ccost=tspdp(c,temp,start+1,n))
{
mincost=c[tour[start]][tour[i]]+cost;
for(k=0;k
mintour[k]=temp[k];
}
}
for(i=o;i
tour[i]=mintour[i];
return mincost;
}

Introduction

Hereby, I am giving a program to find a solution to a Traveling Salesman Problem using Hamiltonian circuit, the efficiency is O (n^4) and I think it gives the optimal solution. Though I have provided enough comments in the code itself so that one can understand the algorithm that I m following, here I give the pseudocode.

Problem Statement

Find the order of cities in which a salesman should travel in order to start from a city, reaching back the same city by visiting all rest of the cities each only once and traveling minimum distance for the same.

ALT statement: Find a Hamiltonian circuit with minimum circuit length for the given graph.

Notations

G: Symmetric weighted undirectional graph with,

Number of vertices = No. of cities
Number of links = Number of paths
Weight of the link = Distance of the path.

Algorithm

Collapse

MIN_CKT_LENGTH=INFINITY
for each vertex V in the graph G
  for each vertex V_N in the graph G such that V and V_N are different
   mark all vertices unvisited
   mark V as visited 
     for staring vertex as V and succeeding vertex as V_N, find circuit 
          such that path staring from V_N in that circut yeilds minimum 
          pathlength from V_N for all unvisited vertices by 
          visiting each vertex.( this path is obtained by greedy method).
       if currently obtained circuit length <= MIN_CKT_LENGTH then
         set MIN_CKT_LENGTH=newly obtained value
         copy the new circuit as hamiltonion circuit
       end if
     end for V_N
   end for V

code segment:

Collapse

//for each vertex, S_V as a staring node


for(int S_V_id=0;S_V_id<n;S_V_id++)

{ 
      //for each and non start vertex as i

      for(i=0;i<n;i++)
      { 
          //set all to unvisited

          set_visited(ALL,FALSE);
          // set staring vertex as visited

          set_visited(S_V_id,TRUE);
          //reset/init minimum circuit

          reset_min_circuit(S_V_id);
          // obtain circuit for combination of S_V and i

          new_circuit_length=get_valid_circuit(S_V_id,i);
          // if newer length is less than the previously

          //calculated min then set it as min and set the

          //current circuit in hamiltonion circuit

          if(new_circuit_length<=min_circuit_length)
                SET_HAM_CKT(min_circuit_length=new_circuit_length);
       }

}

Example

Inputs

Collapse

infinity: 999
no. of cities: 4
no. of paths: 6

 S D Dist
path0: 0 1 2
path1: 0 2 4
path2: 0 3 3
path3: 1 2 3
path4: 1 3 6
path5: 2 3 1

Algorithm proceeds as follows:

V	V_N	V_N-path	ckt_length, ckt (started with INFI,-)	MIN_CKT_LENGTH, HAM_CKT (started with INFI,-)
0	1	1-2-3	9,0-1-2-3-0*	9,0-1-2-3-0
	2	2-3-1	13,0-2-3-1-0	9,0-1-2-3-0
	3	3-2-1	9,0-3-2-1-0*	9,0-3-2-1-0
1	0	0-3-2	9,1-0-3-2-1*	9,1-0-3-2-1
	2	2-3-0	9,1-2-3-0-1*	9,1-2-3-0-1
	3	3-2-0	13,1-3-2-0-1	9,1-2-3-0-1
2	0	0-1-3	13,2-0-1-3-2	9,1-2-3-0-1
	1	1-0-3	9,2-1-0-3-2*	9,2-1-0-3-2
	3	3-0-1	9,2-3-0-1-2*	9,2-3-0-1-2
3	0	0-1-2	9,3-0-1-2-3*	9,3-0-1-2-3
	1	1-0-2	13,3-1-0-2-3	9,3-0-1-2-3
	2	2-1-0	9,3-2-1-0-3*	9,3-2-1-0-3

Comments

This might be the overrun for lower values of vertex count but for large values of n, it's surely less than the exhaustive search as n increases n^4 < n! for n>6.

The optimality is the issue with this problem and as far as I am concerned, I think this algorithm yields the optimal Hamiltonian circuit if it exists at all.

Hereby I ask you people to evaluate my algorithm for different sets of test cases. In case of failure, please inform me with the set of input values, answer found by my code and the actual optimal answer.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

About the Author

Imraan DAA Book

What is Branch and Bound Algorithm?

http://www.fileserve.com/file/YakYdqu

These notes follow the discussion of branch and bound algorithms in Computer Algorithms by E. Horowitz, S. Sahni and S. Rajasekaran.

Here we describe a mathematical model of the process of choosing the next node to expand. This model also includes a function for deciding when to abandon a search path before reaching the end of the path. Abandoning searches early attempts to minimize computational efforts to find the minimal solution.

The basis of branch and bound algorithms is a ranking function. The ranking function assigns a value to each node in the graph. At each step, a branch and bound algorithm uses the ranking function to decide which node to expand next. In contrast, the usual DFS (Depth First Search) and BFS( Breadth First Search) exploration algorithms perform a blind search of the graph. Ideally, the ranking function, c(x), ranks nodes based on the cost of a minimal solution reachable from node x. The problem with this ranking function is that the minimal solution must be known ahead of time. Instead, the ranking function uses an estimate, g(x), of the cost of a minimal solution reachable from node x. Using g(x) to rank nodes may require exploring unnecessary nodes in the graph?particularly if g(x) is not a good estimate.The final element of the ranking function measures the cost of reaching a node from the root. As the searches gets farther from the root node, the node falls in the ranking.

The function h(x) measures the cost of reaching node x from the root node. After including a function of h(x), the ranking function c(x) is

c(x) = f(h(x)) + g(x)

in which f determines how much significant to give the cost of reaching node x. If f(h(x))= 0 then the algorithm makes long, deep searches of the graph. If f(h(x))> 0 then the algorithm considers nodes close to the root before making long potentially fruitless forays into the graph. A node is live if its subgraph might contain a minimal solution. Live nodes are potentialcandidates for exploration. A node is dead if its subgraph can not contain a minimal solution. If the estimated cost of a minimal solution reachable from x is less than the actual minimal solution reachable from x then a node can be killed when the estimated cost is greater than the least upper bound on a solution. In symbols, if c(x)>= upper then an optimal solutionis not reachable from x (assuming upper is the least upper bound on a solution).It should come as no surprise that tuning cby adjusting f and g requires empirical studies of representative data sets.

Traveling Salesperson Problem

Two branch and bound solutions to the TSP are described in this section. Each solution estimates the cost of a minimal tour using a reduced cost matrix. In the first solution, the nodes in a path through the search tree represent cities on a tour. In the second solution, nodes in the search tree represent the inclusion or exclusion of an edge between two cities in the optimal tour. Suppose the distances between n cities are given in an nxn matrix. A row (or column) in this matrix is reduced if at least one entry in the row is 0 while the others are all positive. A matrix is reduced if all of its rows are reduced.

For a non-leaf node S with parent R, the cost of a tour including a trip from R to S can be estimated by a reduced cost matrix A. Matrix A is constructed by:

set all entries of row R and column S to 1 to avoid making a second visit to R or S in an optimal tour.
set A(S, 1) to ∞ to prevent making a premature trip from S to 1.

For each row or column that does not contain all 1, subtract each entry in each row by the smallest value in each row. Subtract each entry in each column by the smallest value in each column.The estimated length of the shortest tour including a trip from R to S is given by: c(S) = f(h(R) + 1) + c(R) + A(R, S) + r

where r is the total value subtracted in step 3. The optimal values of f and h are determined empirically.

In its solution, trees were built by deciding which node to visit next. For example, the nodes in the ith level of the graph are the options for the ith city in a tour. Another solution can be built by deciding whether or not to include a trip between a particular pair of cities in each step. In this solution, the 2 root node might represent the decision to include or non-include a trip between cities 6 and 8. The left child represents the inclusion this trip and the right child represents the exclusion of this trip. The same distance cost estimate function c is used in this solution. The efficient implementation of this algorithm requires a policy for choosing which trip between cities to consider next in the search. A good policy is to choose cities R, S such that a trip between R and S has a high probability of being included in the optimal tour. One way of choosing R and S is to choose cities which result in the highest approximate cost for not including a trip between R and S in the tour.

C# Sample Program:

The algorithm is coded in C# using the Data adapters and data sets for accessing databases for reading and writing sales person's visited cities and their costs with different problem IDs. There is a set of modules that are designed to implement the Branch and Bound algorithm. The program is designed so that it takes input from a database named "tsp.mdf" with the path "C:/tsp.mdf". The "tProblems" table contains the problem information and the "tMatrics" table contains the matrices that contain the cost of traveling between each pair of cities. The tables have the following structure:

tProblems

field	type	comments
key	number
problemID	integer	Identifier for this problem in the tMatrices and tSolutions tables
cities	integer	Number of cities in this problem
timeBound	float	How many seconds allowed for solving this problem

tMatrices

field	type	comments
key	number
problem	integer	Identifier for this problem, matches problemID in tPRoblems
row	integer	Which row of the cost matrix is this row of the table?
contents	string	Space-separated list of costs.

Implementation

The branch and bound algorithm is implemented to solve the tsp problem within the given time bound. If time expires before the algorithm finds a solution, then the program returns the best solution found so far and exit.

Output

The output is written to a table called tSolutions. This table has the following fields:

tSolutions

field	type	comments
key	number	This is automatically updated, you can ignore it
problem	integer	Identifier for this problem, matches problemID in tPRoblems
cost	integer	Cost of your solution
path	string	Order in which you visited the cities in your solution. Start with the city in the first row. Name the cities A, B, C, ... Z, a, b, ... z where the city in the first row is A, the city in the second row is B and so forth
exactSolution	boolean	Was your solution exact?
timeSpent	float	Amount of time your algorithm spent solving this problem. If you run out of time, it is ok for this value to be slightly larger than the time bound (because you probably won't check the time between every pair of instructions and you will need a little time to turn off your timer and output the solution).

All the JNTUH Pool

Pages

BSAR University

Introduction

Problem Statement

Notations

Algorithm

code segment:

Example

Inputs

Algorithm proceeds as follows:

Comments

License

About the Author

What is Branch and Bound Algorithm?

Traveling Salesperson Problem

C# Sample Program:

tProblems

tMatrices

Implementation

Output

tSolutions

Blog Archive

Labels