Homework Sourse1 Implement the verification algorithm for the Traveling Sal
1. Implement the verification algorithm for the Traveling Salesperson Decision problem discussed in class on your system, and study its polynomial-time performance. 2. Write a polynomial-time problem verification algorithm for the Clique Decision problem. 3. Write all instances of the CNF-Satisfiability problem have exactly three literal per clause, it is called the 2-Satisfiability problem. Knowing that the 3-Satisfiability problem is NP-complete, show that the Graph 3-Coloring problem is also NP-complete. 4. Write a detailed algorithm of the approximation algorithm for the Bin-Packing problem discussed in class and show that its time complexity is in O(n2).
Solution
Travelling Salesman Problem (TSP):
Basically,In TSP there is a selesman and a set of cities.The constrait is that ,selesman start from a city and treverse all the cities presented in the set and return back to starting city but condition is that he has to minimize his time taken in complete trip.
The problem of TSPis a well known NP hard problem. So,There is no polynomial time solution present for this problem till now.
There are several approach and algoritm to sovle TSP such as-
§ Naïve Solution
§ Backtracking Algorithm
§ Branch and Bound Algorithm
§ Dynamic Programming
Let us take naive algorithimic solution of TSP
1Consider city 1 as the initial and final points of the selesman.
2) Generate all Permutations (n-1)! of cities.
3) Calculate cost associated with each permutation and processed towards minimum cost.
4) Return the permutation which provide with the minimum cost.
Now, following is the implementation of tsp problem in c it is an easy code just go through the code -
#include<stdio.h>
int m[25][25],citiesvisited[10], p, cost_factor = 0;
int trevellingsellsmenproblem(int a)
{
int c, city_near = 999;
int min = 999, temprory;
for(c = 0; c < p; ct++)
{
if((m[a][c] != 0) && (citiesvisited[c] == 0))
{
if(m[a][c] < min)
{
min = m[a][0] + m[a][c];
}
temprory = matrix[a][c];
city_near = c;
}
}
if(min!= 999)
{
Cost_factor = cost_factor + temprory;
}
return city_near;
}
void min_cost(int city)
{
int city_near;
citiesvisited[city] = 1;
printf(\"%d \", city + 1);
city_near = trevellingsellsmenproblem(city);
if(city_near == 999)
{
city_near = 0;
printf(\"%d\", city_near + 1);
cost_factor = cost_factor + m[city][city_near];
return;
}
min_cost(city_near);
}
int main()
{
int q , r;
printf(\"Enter the number of sitiesyouwant to enter\\t\");
scanf(\"%d\", &p);
printf(\"\ Please Enter the Cost Matrix\ \");
for(q = 0; q < p; q++)
{
printf(\"\ Enter %d Elements in Row[%d]\ \", p, q+ 1);
for(r = 0; r < p; r++)
{
scanf(\"%d\", &m[q][r]);
}
citiesvisited[q] = 0;
}
printf(\"\ Entered Cost Matrix\ \");
for(q = 0; q < p; q++)
{
printf(\"\ \");
for(r = 0; r < p; r++)
{
printf(\"%d \", m[q][r]);
}
}
printf(\"\ \ Path:\\t\");
min_cost(0);
printf(\"\ \ Minimum Cost: \\t\");
printf(\"%d\ \", cost_factor);
return 0;
}
For other questions solutions please provide the questions seprately!
Thankyou
