Scribd
Upload
12 views2 pages

Algorithm 14 Single

The document contains a C program for an approximation algorithm to solve the Traveling Salesman Problem (TSP) using the Held-Karp dynamic programming approach. It includes structures for points, a function to calculate distances between points, and a function to compute a distance matrix. The implementation is designed to handle a maximum of 100 points.

Uploaded by

raguram9024
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
12 views2 pages

Algorithm 14 Single

The document contains a C program for an approximation algorithm to solve the Traveling Salesman Problem (TSP) using the Held-Karp dynamic programming approach. It includes structures for points, a function to calculate distances between points, and a function to compute a distance matrix. The implementation is designed to handle a maximum of 100 points.

Uploaded by

raguram9024
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

[Link].

APPROXIMATION ALGORITHM-9024-RAMU

PROGRAM:

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#include <math.h>

#include <time.h>

#define MAX_POINTS 100

struct Point {

int x;

int y;

};

double distance(struct Point p1, struct Point p2)

{ return sqrt(pow(p2.x - p1.x, 2) + pow(p2.y - p1.y,

2));

void computeDistanceMatrix(struct Point points[], int num_points, double distances[][MAX_POINTS])


{

for (int i = 0; i < num_points; i++)

{ for (int j = 0; j < num_points; j++)

distances[i][j] = distance(points[i], points[j]);

}
double heldKarpTSP(int num_points, double distances[][MAX_POINTS])

{ int num_states = 1 << num_points;

double dp[num_states][MAX_POINTS];

for (int i = 0; i < num_states; i++) {

for (int j = 0; j < num_points; j++) {

dp[i][j] = -1

You might also like