This is touropt.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"
extern setUpScaling(TwoDView *);
extern setUpDrawing(TwoDView *);
/************************************************************************/
/* This function implements a (2-Opt) Tour Optimization Algorithm for the
Travelling Salesperson Algorithm. It provides an approximate optimal
value rather than the optimal value.
Reference: Salkin & Mathur, Foundations Of Integer Programming, 1989
North-Holland, p 690-93.
*/
/************************************************************************/
/* 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 TourOptimization(float *Distance,int *Tour,float OptimalValue,
int NumberOfCities) {
#else
float TourOptimization(TwoDView *self,float *data,float *Distance,int *Tour,
float OptimalValue, int NumberOfCities) {
#endif
int i,CurrentEdge,CurrentFrom,CurrentTo,NumberOfExchanges,
NextEdge,NextFrom,NextTo,Exchanges,ExchangeEdge1,ExchangeEdge2,
NewFrom1,NewFrom2,NewTo1,NewTo2;
float OnTourDistance1,OnTourDistance2,NotOnTourDistance1,NotOnTourDistance2,
BestExchange,Gain,NewOptimalValue;
char msg[256];
#ifndef MYDIR /* code to set up drawing enviromment */
self->displayFlag = DISP_PTS_ONLY;
[self display];
[self lockFocus];
setUpScaling(self);
NXSetColor([self->highColorWell color]);
setUpDrawing(self);
PSsetinstance(YES);
PSnewinstance();
for (i=0;i<2*(NumberOfCities);i+=2) {
int x,y;
x = Tour[i];
y = Tour[i+1];
[self drawEdge:X(x):Y(x):X(y):Y(y)];
}
NXPing();
#endif
NewOptimalValue = OptimalValue;
Exchanges = 1;
NumberOfExchanges = 0;
/* while at least 1 edge exchange has ocurred, we must look and see if
this change might make others possible. */
while (Exchanges) {
Exchanges = 0;
BestExchange = 0;
CurrentEdge = 0;
/* for all edges on the tour, and look at all possible edge
exchanges. */
while (CurrentEdge < NumberOfCities) {
#ifdef DEBUGMYDIR
printf("comparing edge %d with all other edges \n",CurrentEdge);
#else
sprintf(msg,"comparing edge %d with all other edges \n",CurrentEdge);
STATUS(msg);
#endif
CurrentFrom = Tour[2*CurrentEdge];
CurrentTo = Tour[2*CurrentEdge+1];
OnTourDistance1 = Distance[kfrom(CurrentFrom,CurrentTo,NumberOfCities)];
NextEdge = CurrentEdge + 1;
/* look at all edges on the tour that we might be able to make an
exchange with CurrentEdge. */
while (NextEdge < NumberOfCities) {
NextFrom = Tour[2*NextEdge];
NextTo = Tour[2*NextEdge+1];
/* we can't look at edges that involve CurrentFrom or CurrentTo.*/
if ((NextFrom != CurrentFrom) &
(NextFrom != CurrentTo)) {
if ((NextTo != CurrentFrom) &
(NextTo != CurrentTo)) {
/* Get distance between NextFrom and NextTo. */
OnTourDistance2 = Distance[kfrom(NextFrom,NextTo,NumberOfCities)];
/* first look at exchanging CurrentFrom to CurrentTo and
NextFrom to NextTo with CurrentFrom to NextFrom and
CurrentTo to NextTo. */
NotOnTourDistance1 =
Distance[kfrom(CurrentFrom,NextFrom,NumberOfCities)];
NotOnTourDistance2 =
Distance[kfrom(CurrentTo,NextTo,NumberOfCities)];
Gain = (NotOnTourDistance1 + NotOnTourDistance2) -
(OnTourDistance1 + OnTourDistance2);
/* If there is a negative gain, this is a candidate for the
best exchange in this iteration. */
if (Gain < BestExchange) {
if (ValidTour(Tour,CurrentEdge,NextEdge,0,NumberOfCities)) {
#ifdef DEBUGMYDIR
printf("Changing BestExchange from %f to %f \n",BestExchange,Gain);
#endif
BestExchange = Gain;
ExchangeEdge1 = CurrentEdge;
ExchangeEdge2 = NextEdge;
#ifdef DEBUGMYDIR
printf("Changing NewFrom1 from %d to %d \n",NewFrom1,CurrentFrom);
printf("Changing NewTo1 from %d to %d \n",NewTo1,NextFrom);
printf("Changing NewFrom2 from %d to %d \n",NewFrom2,CurrentTo);
printf("Changing NewTo2 from %d to %d \n",NewTo2,NextTo);
#endif
NewFrom1 = CurrentFrom;
NewTo1 = NextFrom;
NewFrom2 = CurrentTo;
NewTo2 = NextTo;
}
}
/* next look at exchanging CurrentFrom to CurrentTo and
NextFrom to NextTo with CurrentFrom to NextTo and
CurrentTo to NextFrom. */
NotOnTourDistance1 =
Distance[kfrom(CurrentFrom,NextTo,NumberOfCities)];
NotOnTourDistance2 =
Distance[kfrom(CurrentTo,NextFrom,NumberOfCities)];
Gain = (NotOnTourDistance1 + NotOnTourDistance2) -
(OnTourDistance1 + OnTourDistance2);
/* If there is a negative gain, this is a candidate for the
best exchange in this iteration. */
if (Gain < BestExchange) {
if (ValidTour(Tour,CurrentEdge,NextEdge,1,NumberOfCities)) {
#ifdef DEBUGMYDIR
printf("Changing BestExchange from %f to %f \n",BestExchange,Gain);
#endif
BestExchange = Gain;
ExchangeEdge1 = CurrentEdge;
ExchangeEdge2 = NextEdge;
#ifdef DEBUGMYDIR
printf("Changing NewFrom1 from %d to %d \n",NewFrom1,CurrentFrom);
printf("Changing NewTo1 from %d to %d \n",NewTo1,NextTo);
printf("Changing NewFrom2 from %d to %d \n",NewFrom2,CurrentTo);
printf("Changing NewTo2 from %d to %d \n",NewTo2,NextFrom);
#endif
NewFrom1 = CurrentFrom;
NewTo1 = NextTo;
NewFrom2 = CurrentTo;
NewTo2 = NextFrom;
}
}
}
}
/* get ready to look at the next edge on the tour. */
NextEdge+=1;
/* perhaps we have looked at all exchanges for this edge...*/
if (NextEdge == NumberOfCities) {
#ifdef DEBUGMYDIR
printf("done looking at edge %d \n",CurrentEdge);
#else
sprintf(msg,"done looking at edge %d \n",CurrentEdge);
STATUS(msg);
#endif
}
}
/* Now look at the next city on the tour. */
CurrentEdge+=1;
}
/* we've looked at all possible exchanges. now, if BestExchange is
greater than 0, we have a valid exchange that will lead to a
better tour. */
if (BestExchange < 0) {
#ifdef DEBUGMYDIR
printf("Found an exchange \n");
printf("ExchangeEdge1 %d ExchangeEdge2 %d \n",ExchangeEdge1,ExchangeEdge2);
#else
sprintf(msg,"exchanging edges %d and %d \n",
ExchangeEdge1,ExchangeEdge2);
STATUS(msg);
#endif
Tour[2*ExchangeEdge1] = NewFrom1;
Tour[2*ExchangeEdge1+1] = NewTo1;
Tour[2*ExchangeEdge2] = NewFrom2;
Tour[2*ExchangeEdge2+1] = NewTo2;
NewOptimalValue+= BestExchange;
Exchanges = 1;
NumberOfExchanges+=1;
BestExchange = 0;
#ifndef MYDIR
/* draw the intermediate tour */
PSnewinstance();
for (i=0;i<2*(NumberOfCities);i+=2) {
int x,y;
x = Tour[i];
y = Tour[i+1];
[self drawEdge:X(x):Y(x):X(y):Y(y)];
}
sprintf(msg,"number of exchanges: %d \n",NumberOfExchanges);
STATUS(msg);
NXPing();
[self->optimalValueField setFloatValue: NewOptimalValue at: 0];
usleep(self->drawTime);
#endif
}
#ifdef DEBUGMYDIR
/* print out current subtour */
printf("number of exchanges: %d \n",NumberOfExchanges);
for (i=0;i<2*(NumberOfCities);i+=2) {
printf("i %d from city %d to city %d \n",i,Tour[i],Tour[i+1]);
}
#endif
}
#ifndef MYDIR
PSsetinstance(NO);
[self unlockFocus];
self->displayFlag = DISP_PTS_RESULTS;
[self display];
#endif
/* return the optimal value */
return(NewOptimalValue);
}
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.