This is add.m in view mode; [Download] [Up]
#include <stdlib.h>
#ifdef MYDIR
#else
#include "TwoDView.h"
#include "TwoDTSP.h"
#include <appkit/graphics.h>
#endif
#include <math.h>
#include <limits.h>
#include <stdio.h>
#include "tspheaders.h"
#include "prototypes.h"
/************************************************************************/
/* This function implements the Nearest Addition Algorithm for the
Travelling Salesperson Algorithm. It provides an approximate optimal
value rather than the optimal value.
Reference: Lawler, Lenstra, et. al., The Traveling Salesman [sic] Problem,
1985, Wiley and Sons, p 157.
*/
/************************************************************************/
/* Parameters: TwoDView *self: Ye Old Drawing Object
float *Data: Pointer to the list of points.
Used to draw intermediate graph.
float *Distance: Pointer to area that contains the
Distances Between Each Pair of Cities
int *Tour: Pointer to area that will contain the
indices of the n arcs that are selected
to be a part of the tour
int NumberOfCities: Number of cities in the problem
*/
/************************************************************************/
/************************************************************************/
#ifdef MYDIR
float NearestAddition(float *Distance,int *Tour,int NumberOfCities) {
#else
float NearestAddition(TwoDView *self,float *data,float *Distance,int *Tour,
int NumberOfCities) {
#endif
int i,j,k,m,x,y,I,J,
From,To,BaseCity,ArcEnd,ReplaceIndex,CurrentCity,
SubTourEnd,TourIndex,NewCity,NotFound;
int *OnTour, *TourCities;
float NewDistance,OptimalValue;
/* allocate space for OnTour and TourCities */
OnTour = (int *)malloc(NumberOfCities*sizeof(int));
TourCities = (int *)malloc(NumberOfCities*sizeof(int));
if (OnTour == (int *) 0)
printf("Malloc for OnTour failed. \n");
if (TourCities == (int *) 0)
printf("Malloc for OnTour failed. \n");
for (i=0;i<NumberOfCities;i++) {
OnTour[i] = 0;
}
for (i=0;i<NumberOfCities;i++) {
TourCities[i] = 0;
}
#ifdef DEBUGMYDIR
for (i=0;i<(NumberOfCities-1)*NumberOfCities/2;i++) {
printf("Distance[%d] = %f; \n",i,Distance[i]);
}
#endif
/* find the two cities with the minimum distance */
/* these two cities make up the initial subtour */
NewDistance = ClosestCities(Distance,&From,&To,NumberOfCities);
/* if NewDistance doesn't change, there is a problem ... */
if (NewDistance == INT_MAX) {
printf("Error no initial subtour found. \n");
}
#ifdef DEBUGMYDIR
else {
printf("initial subtour \n");
printf("from %d to %d distance %f \n",From,To,NewDistance);
}
#endif
/* OnTour is a list of cities on the tour already. */
Tour[0] = Tour[3] = From;
Tour[1] = Tour[2] = To;
OnTour[From] = OnTour[To] = 1;
TourCities[0] = From;
TourCities[1] = To;
OptimalValue = 2*NewDistance;
SubTourEnd = 1;
TourIndex = -1;
NewCity = NumberOfCities;
NewDistance = INT_MAX;
/* keep adding cities until you include all NumberOfCities of them */
while (SubTourEnd < NumberOfCities-1) {
#ifdef DEBUGMYDIR
printf("Start of Iteration with %d cities in tour \n",SubTourEnd+1);
#endif
/* at the end of this while loop, there will be a new city to insert */
while (TourIndex < SubTourEnd) {
/* look at the next city already on the tour */
TourIndex+=1;
CurrentCity = TourCities[TourIndex];
#ifdef DEBUGMYDIR
printf("Looking at city %d \n",CurrentCity);
#endif
/* look at all arcs starting at CurrentCity */
I = ArcIndex(CurrentCity,NumberOfCities);
J = ArcIndex((CurrentCity+1),NumberOfCities);
for (i=I;i<J;i++) {
/* j = terminating end of this arc */
j = i-I+CurrentCity+1;
/* if the city at the other end isn't already on the tour ...*/
if (!OnTour[j]) {
/* Is the arc a new candidate for insertion? */
k = kfrom(CurrentCity,j,NumberOfCities);
if (Distance[k] < NewDistance) {
#ifdef DEBUGMYDIR
printf("Changing cities from %d to %d \n",NewCity,j);
printf("Looking at city %d \n",CurrentCity);
#endif
NewDistance = Distance[k];
NewCity = j;
BaseCity = CurrentCity;
}
}
}
/* look at all arcs ending at CurrentCity */
for (m=0;m<CurrentCity;m++) {
/* if the starting city isn't already on the tour ...*/
if (!OnTour[m]) {
/* Is this arc a new candidate for insertion? */
k = kfrom(m,CurrentCity,NumberOfCities);
if (Distance[k] < NewDistance) {
#ifdef DEBUGMYDIR
printf("Changing cities from %d to %d \n",NewCity,m);
#endif
NewDistance = Distance[k];
NewCity = m;
BaseCity = CurrentCity;
}
}
}
}
if (NewCity >= NumberOfCities) {
printf("Error: new city has not been found for tour. \n");
CurrentCity = SubTourEnd = NumberOfCities;
OptimalValue = -1;
}
else {
/* find an arc connected to BaseCity, and replace it with
the new arc. */
k = 0;
NotFound = 1;
while ((k < SubTourEnd) && (NotFound)) {
if (Tour[2*k] == BaseCity) {
ArcEnd = Tour[2*k+1];
ReplaceIndex = k;
NotFound = 0;
}
if (Tour[2*k+1] == BaseCity) {
ArcEnd = Tour[2*k];
ReplaceIndex = k;
NotFound = 0;
}
k+=1;
}
if (NotFound) {
printf("Error: Haven't found arc on Tour Ending at %d \n",BaseCity);
CurrentCity = SubTourEnd = NumberOfCities;
OptimalValue = -1;
}
else {
/* arc between BaseCity and ArcEnd is replaced by arc
between NewCity and ArcEnd. */
#ifdef DEBUGMYDIR
printf("replacing arc from %d to %d with %d to %d \n",
BaseCity,ArcEnd,NewCity,ArcEnd);
#endif
Tour[2*ReplaceIndex] = NewCity;
Tour[2*ReplaceIndex+1] = ArcEnd;
/* update the Optimal Value */
OptimalValue+=Distance[kfrom(NewCity,ArcEnd,NumberOfCities)] -
Distance[kfrom(BaseCity,ArcEnd,NumberOfCities)];
/* add the new arc going from NewCity to BaseCity */
#ifdef DEBUGMYDIR
printf("adding arc from %d to %d \n",NewCity,BaseCity);
#endif
SubTourEnd+=1;
Tour[2*SubTourEnd] = NewCity;
Tour[2*SubTourEnd+1] = BaseCity;
OnTour[NewCity] = 1;
TourCities[SubTourEnd] = NewCity;
/* update the Optimal Value */
OptimalValue+=NewDistance;
#ifdef DEBUGMYDIR
printf("addding %f to Opval to get %f \n",NewDistance,OptimalValue);
#endif
}
/* get ready to start at the top of the list again */
TourIndex = -1;
NewDistance = INT_MAX;
NewCity = NumberOfCities;
#ifdef DEBUGMYDIR
/* print out current subtour */
for (i=0;i<2*(SubTourEnd+1);i++) {
printf("i tour %d %d \n",i,Tour[i]);
}
#endif
#ifdef MYDIR
#else
/* draw the intermediate tour */
PSnewinstance();
for(i=0;i<2*(SubTourEnd+1);i+=2) {
x = Tour[i];
y = Tour[i+1];
[self drawEdge:X(x):Y(x):X(y):Y(y)];
}
NXPing();
[self->optimalValueField setFloatValue: OptimalValue at: 0];
usleep(self->drawTime);
#endif
}
}
/* clean up */
free(OnTour);
/* return the optimal value */
return(OptimalValue);
}
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.