Question

Special productions are made in the aluminum profile factory. Aluminum profile orders for 10 different customers have been produced and ready for distribution. All of the prepared orders can be loaded into a vehicle and distributed. The employee who will distribute the profiles prepared at the factory will load them into the vehicle and return to the factory after delivering the orders to all the customers. To meet the demand of all customers, write the C code that operates the steps of the “nearest neighbor algorithm” to find the tour to follow. Note: randomly determine the distance between customers.

Answer 1

We can solve this problem by using Dynamic progaraming .

For this problem we create cost matrix by using the distances.

like shown below.

to do this problem we can go throw the following formula:

T (i , s) = min ( ( i , j) + T ( j , S – { j }) ) ; S!= Ø   ; j € S ;

S is set that contains non visited vertices

= ( i, 1 ) ; S=Ø, This is base condition for this recursive equation.

Here,

T (i, S) means We are travelling from a vertex “i” and have to visit set of non-visited vertices “S” and have to go back to vertex 1 (let we started from vertex 1).

( i, j ) means cost of path from node i to node j

If we observe the first recursive equation from a node we are finding cost to all other nodes (i,j) and from that node to remaining using recursion ( T (j , {S-j}))

But it is not guarantee that every vertex is connected to other vertex then we take that cost as infinity. After that we are taking minimum among all so the path which is not connected get infinity in calculation and won’t be consider.

If S is empty that means we visited all nodes, we take distance from that last visited node to node 1 (first node). Because after visiting all he has to go back to initial node.

PROGRAM:

#include<stdio.h>
 
int ary[10][10],completed[10],n=10,cost=0;
 
void takeInput()   //This function is to take distance between factory to evrery costomers and every costomer to other costomer
{
        int i,j;

 
        printf("\nEnter the Cost Matrix\n");  //We generally take input as cost matrix
 
        for(i=0;i < n;i++)
        {
                printf("\nEnter Elements of Row: %d\n",i+1);
 
                for( j=0;j < n;j++)
                        scanf("%d",&ary[i][j]);
 
                completed[i]=0;
        }
 
        printf("\n\nThe cost list is:");
 
        for( i=0;i < n;i++)
        {
                printf("\n");
 
                for(j=0;j < n;j++)
                        printf("\t%d",ary[i][j]);
        }
}
int least(int c)
{
        int i,nc=999;
        int min=999,kmin;
 
        for(i=0;i < n;i++)
        {
                if((ary[c][i]!=0)&&(completed[i]==0))
                        if(ary[c][i]+ary[i][c] < min)
                        {
                                min=ary[i][0]+ary[c][i];
                                kmin=ary[c][i];
                                nc=i;
                        }
        }
 
        if(min!=999)
                cost+=kmin;
 
        return nc;
}
 
 
void nearestneighbor(int city)
{
        int i,ncity;
 
        completed[city]=1;
 
        printf("%d--->",city+1);
        ncity=least(city);
 
        if(ncity==999)
        {
                ncity=0;
                printf("%d",ncity+1);
                cost+=ary[city][ncity];
 
                return;
        }
 
        nearestneighbor(ncity);
}
 

int main()
{
        takeInput();
 
        printf("\n\nThe Path is:\n");
        nearestneighbor(0); //passing 0 because starting vertex
 
        printf("\n\nMinimum distance is %d\n ",cost);
 
        return 0;
}

Sample Output:

Enter the Cost Matrix

Enter Elements of Row: 1
0 1 2 1 3 4 5 6 4 1

Enter Elements of Row: 2
2 0  4 1 5 3 6 2 7 1

Enter Elements of Row: 3
4 1 0 4 5 4 1 5 3 4 1

Enter Elements of Row: 4
2 4 4 0 4 6 3 1 8 4 2

Enter Elements of Row: 5
5 4 1 2 0 4 3 2 6 1 4

Enter Elements of Row: 6
4 1 5 2 4 0 1 2 3 6 4

Enter Elements of Row: 7
4 1 6 2 4 6 0 4 9 5 1

Enter Elements of Row: 8
1 4 3 1 2 6 4 0 4 2 3

Enter Elements of Row: 9
4 2 3 6 5 1 4 2 3 0 4

Enter Elements of Row: 10
4 5 1 2 3 4 2 4 2 4 0


The cost list is:
        0       1       2       1       3       4       5       6       4       1
        2       0       4       1       5       3       6       2       7       1
        4       1       0       4       5       4       1       5       3       4
        1       2       4       4       0       4       6       3       1       8
        4       2       5       4       1       2       0       4       3       2
        6       1       4       4       1       5       2       4       0       1
        2       3       6       4       4       1       6       2       4       6
        0       4       9       5       1       1       4       3       1       2
        6       4       0       4       2       3       4       2       3       6
        5       1       4       2       3       0       4       4       5       1

The Path is:
1--->4--->2--->8--->10--->5--->9--->7--->6--->3--->1

Minimum distance is 26