tsp_u1.cpp

使用到的参数跟谈到弹性网络的那一章里头所讲的是一样的

/*
  Version History
  ver 1.00 Dec  9, 1997 Official Release
  ver 1.01 Dec 10, 1997 Add a write button


  Flags:

  TForm1->tsp_started : if a valid instance ready
  TSP->loaded         : if a TSP file loaded
*/
//---------------------------------------------------------------------------
#include <vcl\vcl.h>
#pragma hdrstop
#include "math.h"
#include "tsp_u1.h"

#define PI 3.14159
//---------------------------------------------------------------------------
#pragma link "titlebar"
#pragma resource "*.dfm"
TForm1 *Form1;

TSP::TSP(int cnum, int wnum, int max, double a, double b, double k, double ke) {
    itmax = max; citynum = cnum; waynum = wnum;
    para = a; parb = b; park_st = k; parke = 2*ke;
	loaded = false;
    city      = new double*[citynum];
    way       = new double*[waynum];
    phiArr    = new double*[citynum];
    city_norm = new double[citynum];
    best_solution = new int[citynum];

	for(int i = 0; i < citynum; i++) {
      city[i] = new double[2];
      phiArr[i]  = new double[waynum];
    }
    for(int i = 0; i < waynum; i++)
      way[i] = new double[2];
}

TSP::~TSP() {
  for(int i = 0; i < citynum; i++) {
    delete city[i];
    delete phiArr[i];
  }
  for(int i = 0; i < waynum; i++)
    delete way[i];
  delete city, way, phiArr, city_norm, best_solution;
}

//------------------- Salesman calculation's --------
void TSP::newpoint() {
  double delta = 2.* PI / waynum;
  double c = Form1->Edit_central->Text.ToDouble(),
  		 r = Form1->Edit_radius->Text.ToDouble();
  for(int i=0; i<waynum; i++) {
    way[i][x] = c + r * cos(delta*i);
    way[i][y] = c + r * sin(delta*i);
  }
}

void TSP::newcity() {
  if (Form1->CheckBox_random->Checked) {
    unsigned int tt = GetTickCount();
    char line[80];
    itoa(tt, line, 10);
    Form1->Edit_seed->Text = line;
    srand(tt);
  } else
    srand(Form1->Edit_seed->Text.ToInt());
  for(int i=0; i<citynum; i++) {
    city[i][x] = (rand() % 10000) / 10000.0;
    city[i][y] = (rand() % 10000) / 10000.0;
  }
  newpoint();
}


double TSP::phi(double d) {
  return (d<70.) ? exp(-d/(2.*park*park)) : 0.;
}

double TSP::fcity(int ip, int id) {
  double res = 0.;
  for(int i=0; i<citynum; i++)
    res += (city[i][id]-way[ip][id])
        * phiArr[i][ip]/city_norm[i];
  return res;
}

void TSP::load_city_map(AnsiString pf, AnsiString tf) {
  file_loaded = pf;
  loaded = true;

  // open the city points file
  char line[81];
  FILE * f = fopen(pf.c_str(), "rt");
  // skip the number of cities
  fgets(line, 80, f);
  double x1, y1;
  for(int i = 0; i < citynum; i++) {
    fgets(line, 80, f);
    sscanf(line, "%lf %lf", &x1, &y1);
    city[i][0] = x1;
    city[i][1] = y1;
  }
  fclose(f);

  // get the optimal solution
  optimal_solution = new int[citynum];
  f = fopen(tf.c_str(), "rt");
  for(int i = 0; i < citynum; i++) {
    fgets(line, 80, f);
    sscanf(line, "%d", &optimal_solution[i]);
    optimal_solution[i]--; // start with city(1) rather than (0)
  }
  fclose(f);

  // calculate the optimal length
  optimal_length = 0;
  for(int i = 0; i < citynum - 1; i++) {
    optimal_length +=
      sqrt(
      (city[ optimal_solution[i] ][0] - city[ optimal_solution[i+1] ][0]) *
      (city[ optimal_solution[i] ][0] - city[ optimal_solution[i+1] ][0]) +
	  (city[ optimal_solution[i] ][1] - city[ optimal_solution[i+1] ][1]) *
	  (city[ optimal_solution[i] ][1] - city[ optimal_solution[i+1] ][1])
      );
  }
  optimal_length +=
    sqrt(
    (city[ optimal_solution[citynum-1] ][0] - city[ optimal_solution[0] ][0]) *
    (city[ optimal_solution[citynum-1] ][0] - city[ optimal_solution[0] ][0]) +
	(city[ optimal_solution[citynum-1] ][1] - city[ optimal_solution[0] ][1]) *
	(city[ optimal_solution[citynum-1] ][1] - city[ optimal_solution[0] ][1])
    );
}

double TSP::dist_max() {
  double max = 0.0;
  for(int i=0; i<citynum; i++) {
    double min = 1000.0, temp;
    for(int j=0; j<waynum; j++) {
      double dx = way[j][x]-city[i][x];
      double dy = way[j][y]-city[i][y];
      double dr = dx*dx + dy*dy;
      phiArr[i][j] = phi(dr);
	  temp = sqrt(dr);
	  if (temp < min) min = temp;
    }
	if (min > max) max = min;
  }
  return max;
}

void TSP::ini_before_iteration() {
  delta = new double*[waynum];
  for(int i = 0; i < waynum; i++)
    delta[i] = new double[2];
  park = park_st;
  //  pare = parke/Math.max(size().width, size().height);
  pare = parke/200;
  newpoint();

  //---------- Draw the cities ----------------
  TRect tr;
  tr.Left = 1;
  tr.Right = 400;
  tr.Top = 1;
  tr.Bottom = 400;
  Form1->Canvas->Brush->Color = clBlack;
  Form1->Canvas->FillRect(tr);

  Form1->Canvas->Brush->Color = clYellow;
  for(int i = 0; i < citynum; i++) {
    tr.Left = 2+city[i][0]*400;
    tr.Right = 6+city[i][0]*400;
    tr.Top = 2+city[i][1]*400;
    tr.Bottom = 6+city[i][1]*400;
  	Form1->Canvas->FillRect(tr);
  }
}

//--------- This is the main iteration procedure! -------

void TSP::iteration() {
  Form1->Canvas->Pen->Color = clRed;
  Form1->Canvas->Pen->Width = 1;
  Form1->Canvas->Pen->Mode = pmNot;

  //--------- Draw the initial way ------------
  Form1->Canvas->MoveTo(way[0][0]*400, way[0][1]*400);
  for(int i = 0; i < waynum; i++)
    Form1->Canvas->LineTo(way[i][0]*400, way[i][1]*400);
  Form1->Canvas->LineTo(way[0][0]*400, way[0][1]*400);

  Screen->Cursor = crHourGlass;

  //---------- Main calculation ----------------
  for(int iter=0; (iter<itmax); ) {
    iter++;
    park*=.99;

    if(dist_max() < pare) break;

    // -------- Cities normalization -----------

    for(int i=0; i<citynum; i++) {
      city_norm[i]=0.;
      for (int j=0; j<waynum; j++)
        city_norm[i] += phiArr[i][j];
      if (city_norm[i]<1.e-80) city_norm[i]=1.;
    }

    // ------------------------------------------

    for(int j=0; j<waynum; j++) {
      int jn = (j==waynum-1)?0:j+1;
      int jp = (j!=0)?j-1:waynum-1;
      for(int k=0; k<=y; k++)
        delta[j][k] = para*fcity(j, k) + parb*park
                      *(way[jn][k] - 2.* way[j][k] + way[jp][k]);
    }

    //------------- repaint --------------------
  	Form1->Canvas->MoveTo(way[0][0]*400, way[0][1]*400);
  	for(int i = 0; i < waynum; i++)
    	Form1->Canvas->LineTo(way[i][0]*400, way[i][1]*400);
  	Form1->Canvas->LineTo(way[0][0]*400, way[0][1]*400);

    for(int j=0; j<waynum; j++)
      for(int k=0; k<=y; k++)
        way[j][k] += delta[j][k];

	//This is a place for drawing procedure
  	Form1->Canvas->MoveTo(way[0][0]*400, way[0][1]*400);
  	for(int i = 0; i < waynum; i++)
    	Form1->Canvas->LineTo(way[i][0]*400, way[i][1]*400);
  	Form1->Canvas->LineTo(way[0][0]*400, way[0][1]*400);

	// bad implementation, should use timer instead
    if (Form1->CheckBox_Step->Checked) {
      unsigned int duration = Form1->Edit_tick->Text.ToInt();
      DWORD oldt = GetTickCount();
      while ((GetTickCount() - oldt) < duration);
    }
  }

  // draw the points
  Form1->Canvas->Pen->Color = clRed;
  Form1->Canvas->Pen->Mode = pmCopy;
  Form1->Canvas->Brush->Color = clRed;

  for(int i = 0; i < waynum; i++)
    Form1->Canvas->Ellipse(way[i][0]*400 - 2, way[i][1]*400 - 2,
                           way[i][0]*400 + 2, way[i][1]*400 + 2);

  for(int i = 0; i < waynum; i++)
    delete delta[i];
  delete delta;

  // search for located cities
  int city_counter = 0;
  double dis, error = Form1->Edit_error->Text.ToDouble();
  for(int i = 0; i < waynum; i++) {
	dis = 0;
    for(int j = 0; j < citynum; j++) {
      dis = sqrt( (way[i][0] - city[j][0])*(way[i][0] - city[j][0]) +
                  (way[i][1] - city[j][1])*(way[i][1] - city[j][1]));
      if (dis < error) {
        // make sure city(j) hasn't been located yet
        bool duplicated = false;
        for(int k = 0; k < city_counter; k++)
          if (best_solution[k] == j) {
            duplicated = true;
            break;
          }
        if (!duplicated)
          best_solution[city_counter++] = j;
      }
    }
  }

  // found a valid solution
  if (city_counter == citynum) {
    best_length = 0;
    for(int i = 0; i < citynum - 1; i++) {
      best_length +=
        sqrt(
        (city[ best_solution[i] ][0] - city[ best_solution[i+1] ][0]) *
        (city[ best_solution[i] ][0] - city[ best_solution[i+1] ][0]) +
	    (city[ best_solution[i] ][1] - city[ best_solution[i+1] ][1]) *
	    (city[ best_solution[i] ][1] - city[ best_solution[i+1] ][1]));
    }
    best_length +=
      sqrt(
      (city[ best_solution[citynum-1] ][0] - city[ best_solution[0] ][0]) *
      (city[ best_solution[citynum-1] ][0] - city[ best_solution[0] ][0]) +
	  (city[ best_solution[citynum-1] ][1] - city[ best_solution[0] ][1]) *
	  (city[ best_solution[citynum-1] ][1] - city[ best_solution[0] ][1]));
      AnsiString ts = (int)(best_length*1000)/1000.0;
      ts = "B: " + ts;
      Form1->StatusBar1->Panels->Items[1]->Text = ts;
      if (loaded) {
        double tt = (best_length - optimal_length)/optimal_length;
        AnsiString ts2 = (int)(tt*1000)/10.0;
        ts2 = "D: " + ts2 + "%";
        Form1->StatusBar1->Panels->Items[2]->Text = ts2;
	  }
  } else
      Form1->StatusBar1->Panels->Items[1]->Text = "No Valid Solution!";

  Screen->Cursor = crDefault;
}

void TSP::draw_result() {
  //---------- Draw the cities ----------------
  TRect tr;
  tr.Left = 1;
  tr.Right = 400;
  tr.Top = 1;
  tr.Bottom = 400;
  Form1->Canvas->Brush->Color = clBlack;
  Form1->Canvas->FillRect(tr);

  Form1->Canvas->Brush->Color = clYellow;
  for(int i = 0; i < citynum; i++) {
    tr.Left = 2+city[i][0]*400;
    tr.Right = 6+city[i][0]*400;
    tr.Top = 2+city[i][1]*400;
    tr.Bottom = 6+city[i][1]*400;
  	Form1->Canvas->FillRect(tr);
  }

  // draw the net
  Form1->Canvas->Pen->Color = clRed;
  Form1->Canvas->Pen->Width = 1;
  Form1->Canvas->Pen->Mode = pmNot;

  Form1->Canvas->MoveTo(way[0][0]*400, way[0][1]*400);
  for(int i = 0; i < waynum; i++)
    Form1->Canvas->LineTo(way[i][0]*400, way[i][1]*400);
  Form1->Canvas->LineTo(way[0][0]*400, way[0][1]*400);

  // draw the points
  Form1->Canvas->Pen->Color = clRed;
  Form1->Canvas->Pen->Mode = pmCopy;
  Form1->Canvas->Brush->Color = clRed;

  for(int i = 0; i < waynum; i++)
    Form1->Canvas->Ellipse(way[i][0]*400 - 2, way[i][1]*400 - 2,
                           way[i][0]*400 + 2, way[i][1]*400 + 2);
}

//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
	: TForm(Owner)
{
  tsp_started = false;
  output_file = fopen("en.out", "at");
}

//---------------------------------------------------------------------------
void __fastcall TForm1::Go_ButtonClick(TObject *Sender) {
  tsp_started = false;
  Repaint();
  tsp = new TSP(Edit1_NofC->Text.ToInt(),
                Edit2_NofN->Text.ToInt(),
          		Edit3_imax->Text.ToInt(),
          		Edit4_a->Text.ToDouble(),
          		Edit5_b->Text.ToDouble(),
          		Edit6_k->Text.ToDouble(),
          		Edit7_ke->Text.ToDouble());
  tsp->newcity();
  tsp->ini_before_iteration();
  tsp->iteration();
  tsp_started = true;
  Go_Button->Enabled = false;
  Button_load->Enabled = false;
  Button1->Enabled = true;
  Button_write->Enabled = true;
}

//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
  if (tsp_started)
    delete tsp;
  tsp_started = false;
  Repaint();
  Go_Button->Enabled = true;
  Button_load->Enabled = true;
  StatusBar1->Panels->Items[0]->Text = "";
  StatusBar1->Panels->Items[1]->Text = "";
  StatusBar1->Panels->Items[2]->Text = "";
  Button1->Enabled = false;
  Button_write->Enabled = false;
}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button_loadClick(TObject *Sender)
{
  tsp_started = false;

  // execute OpenDialog and Get the City Points & Optimal Solution
  OpenDialog1->Title = "Open a city points file";
  OpenDialog1->Filter = "City Points|*.tsp";
  if (!OpenDialog1->Execute())
    return;
  AnsiString pf = OpenDialog1->FileName;

  OpenDialog1->Title = "Open the optimal solution file";
  OpenDialog1->Filter = "Optimal Solution|*.opt";
  OpenDialog1->FileName = "";
  if (!OpenDialog1->Execute())
    return;
  AnsiString tf = OpenDialog1->FileName;

  // Get the number of cities
  char line[81];
  FILE * f = fopen(pf.c_str(), "rt");
  fgets(line, 80, f);
  line[ strlen(line) - 1] = NULL; // eliminate the new line character
  Edit1_NofC->Text = line;
  fclose(f);

  // initialization
  Repaint();
  tsp = new TSP( Edit1_NofC->Text.ToInt(),
                 Edit2_NofN->Text.ToInt(),
          		 Edit3_imax->Text.ToInt(),
          		 Edit4_a->Text.ToDouble(),
          		 Edit5_b->Text.ToDouble(),
          		 Edit6_k->Text.ToDouble(),
          		 Edit7_ke->Text.ToDouble());
  tsp->load_city_map(pf, tf);

  // display the optimal solution
  // round off
  AnsiString ts = (int)(tsp->optimal_length*1000)/1000.0;
  ts = "Op: " + ts;
  StatusBar1->Panels->Items[0]->Text = ts;

  tsp->ini_before_iteration();
  tsp->iteration();

  tsp_started = true;
  Go_Button->Enabled = false;
  Button_load->Enabled = false;
  Button1->Enabled = true;
  Button_write->Enabled = true;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Image1Click(TObject *Sender)
{
	OKBottomDlg->ShowModal();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormPaint(TObject *Sender)
{
  if (tsp_started)
    tsp->draw_result();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::write_result(TObject *Sender)
{
  if (!tsp_started)
    return;

  char line[256];

  if (tsp->loaded)
    sprintf(line, "%3d %4d %5d %.2lf %.2lf %.2lf %.2lf - %.4lf %.4lf %15s\n",
            tsp->citynum, tsp->waynum, tsp->itmax,
            tsp->para, tsp->parb, tsp->park_st, tsp->parke,
            tsp->best_length, tsp->optimal_length, tsp->file_loaded.c_str());
  else
    sprintf(line, "%3d %4d %5d %.2lf %.2lf %.2lf %.2lf - %.4lf %.4lf R(%12s) \n",
            tsp->citynum, tsp->waynum, tsp->itmax,
            tsp->para, tsp->parb, tsp->park_st, tsp->parke,
            tsp->best_length, 0, Edit_seed->Text.c_str());

  fputs(line, output_file);
}
//---------------------------------------------------------------------------