10 Lessons About C++(2015)
Chapter 8: Application of 2-opt to the Traveling Salesman Problem
A 2-opt is a simple local search algorithm for solving 'traveling salesman' type problems. Its operation is simple: it modifies a route that crosses over itself, reordering it so there are no longer any crossovers and therefore a shorter overall route:
This can be a useful technique for finding reasonable solutions to traveling salesman problems with hundreds or even thousands of node locations.
The Mechanism by which the 2-opt swaps a given route between nodes i and k to create a new route:
1. add route[0] to route[i-1] in order to the new route
2. add route[i] to route[k] in reverse order to the new route
3. add route[k+1] to end in order to the new route;
And as applied to the example route above, following steps 1-3:
route[ 0 to 3 ] : Glasgow > Edinburgh > Manchester > Leeds where i = 1; k = 2. New route:
1. Glasgow
2. Glasgow > ( Manchester > Edinburgh )
3. Glasgow > Manchester > Edinburgh > ( Leeds )
The complete 2-opt swap heuristic making use of the above mechanism to search every possible valid combination:
While ( no further improvement made )
{
start_again:
best_distance = calculateTotalDistance(existing_route)
for (i = 0; i < number of nodes eligible to be swapped - 1; i++) {
for (k = i + 1; k < number of nodes eligible to be swapped; k++) {
new_route = 2optSwap(existing_route, i, k)
new_distance = calculateTotalDistance(new_route)
if (new_distance < best_distance) {
existing_route = new_route
goto start_again
}
}
}
}
The creation of a Visual Studio 2010 dialog-based project to implement the optimization algorithm and present the output graphically is described, together with some results from applying the program to a standard traveling salesman test problem.
Just follow these steps:
Step 1: Create a standard dialog-based application:
In Visual Studio select File > New > Project. Select MFC Application:
Uncheck all boxes and select a dialog-based application, then click Next:
Again uncheck all boxes:
Do the same for the advanced features page:
Click Next and then click Finish.
Step 2: Create the dialog controls
In the Resource View see how the basic dialog has been created:
Remove the “TODO: Place dialog controls here.” static control in the middle. Right-click the OK button and select Properties and rename its Caption property to Run. Change the ID property from IDOK to IDC_RUN Create one more button: from the Toolbox, select the Button control and drag it on to the dialog. Set its Caption property to Open and set its ID to IDC_OPEN. Reposition your three buttons so they are located in the top right part of the dialog:
From the Toolbox drag and resize two static controls on to the dialog:
Let the top static text control be captioned as “Total distance:” and set its ID property to IDC_DISTANCE. Then set the bottom static text Caption property as “Tour:” and set its ID to IDC_TOUR:
This is everything needed for creating the user interface.
Step 3: Add the additional source files
In the solution explorer, right click the project folder and select Add > New Item. Do this to create the following C++ header and source files:
1. CoordMatrix.h, CoordMatrix.cpp
2. Tour.h, Tour.cpp
3. TSPalgorithm.h, TSPalgorithm.cpp
4. MakeString.h
Your solution explorer will be updated as follows:
Insert the code for each of the source files.
Full Code Listings
CoordMatrix.h
#pragma once
#include <vector>
#include <map>
#include <fstream>
#include <tuple>
#include <string>
class CoordMatrix
{
public:
enum EDGE_WEIGHT_TYPE
{
ATT = 0
};
CoordMatrix();
~CoordMatrix();
void Initialize( std::string filepath );
int CalcPseudoEuclidDistance(
const int& x1,
const int& x2,
const int& y1,
const int& y2 );
double Distance( const int& c1, const int& c2 );
int size() const;
int GetX( const int& index ) const;
int GetY( const int& index ) const;
int GetMinX() const;
int GetMinY() const;
int GetMaxX() const;
int GetMaxY() const;
std::string GetFileTitle() const;
private:
void tokenize( std::vector<std::string>& tokens,
const std::string& text,
const std::string& delimiter );
void SetDistanceMatrix();
void Reset();
private:
std::vector< std::pair<int, int> > coords;
std::map< std::pair<int,int>, double > distMatrix;
std::string title;
int minx, miny;
int maxx, maxy;
int edge_weight_type;
};
CoordMatrix.cpp
#include "StdAfx.h"
#include "CoordMatrix.h"
#include <iostream>
#include <fstream>
#include <sstream>
#include <cmath>
const int infinity = 99999999;
#define round(n) ((int)((n)+0.5))
CoordMatrix::CoordMatrix()
{
minx = infinity; miny = infinity;
maxx = -infinity; maxy = -infinity;
edge_weight_type = ATT;
title = "";
}
CoordMatrix::~CoordMatrix() {}
// Initialise cost / distance matrix from input file
void CoordMatrix::Initialize( std::string filepath )
{
Reset();
minx = infinity;
miny = infinity;
maxx = infinity * -1;
maxy = infinity * -1;
std::vector< std::pair<int, int> >().swap( coords );
std::ifstream file;
file.open( filepath.c_str() );
if ( !file )
{
std::cout << "Error in opening text/tsp file\n";
return;
}
int line = 0;
while( !file.eof() )
{
line++;
char buf[ 255 ];
file.getline( buf, 128 );
std::vector<std::string> tokens;
std::string text( buf );
tokenize( tokens, text, " " );
if ( tokens.at( 0 ) == "NAME" )
{
title = tokens.at( 2 );
}
if ( tokens.at( 0 ) == "EDGE_WEIGHT_TYPE" )
{
if ( tokens.at( 2 ) == "ATT" )
{
edge_weight_type = ATT;
}
}
if (line < 7 || ( tokens.size() == 1 && text != "EOF"))
continue;
if ( text == "EOF" )
break;
int node = atoi( tokens.at( 0 ).c_str() );
int x = atoi( tokens.at( 1 ).c_str() );
int y = atoi( tokens.at( 2 ).c_str() );
std::pair<int,int> n( x, y );
coords.push_back( n );
if ( x > maxx ) maxx = x;
if ( y > maxy ) maxy = y;
if ( x < minx ) minx = x;
if ( y < miny ) miny = y;
}
file.close();
SetDistanceMatrix();
}
// Get Euclidean distance between two cities
double CoordMatrix::Distance( const int& c1, const int& c2 )
{
if ( c1 < c2 )
{
std::pair<int,int> p( c1, c2 );
return distMatrix[ p ];
}
else
{
std::pair<int,int> p( c2, c1 );
return distMatrix[ p ];
}
}
// Reset the distance matrix
void CoordMatrix::Reset()
{
std::vector< std::pair<int, int> >().swap( coords );
std::map< std::pair<int,int>, double >().swap( distMatrix );
}
// Tokenize the input string
void CoordMatrix::tokenize( std::vector<std::string>& tokens,
const std::string& text,
const std::string& delimiter )
{
size_t next_pos = 0;
size_t init_pos = text.find_first_not_of( delimiter, next_pos );
while ( next_pos != std::string::npos &&
init_pos != std::string::npos ) {
next_pos = text.find( delimiter, init_pos );
std::string token = text.substr( init_pos, next_pos - init_pos );
tokens.push_back( token );
init_pos = text.find_first_not_of( delimiter, next_pos );
}
}
// Get number of items contained in matrix
int CoordMatrix::size() const
{ return (int) coords.size(); }
// Get selected x coordinate
int CoordMatrix::GetX( const int& index ) const
{
std::pair<int,int> n = coords.at( index );
return n.first;
}
// Get selected y coordinate
int CoordMatrix::GetY( const int& index ) const
{
std::pair<int,int> n = coords.at( index );
return n.second;
}
// Get minimum x coordinate
int CoordMatrix::GetMinX() const
{ return minx; }
// Get minimum y coordinate
int CoordMatrix::GetMinY() const
{ return miny; }
// Get maximum x coordinate
int CoordMatrix::GetMaxX() const
{ return maxx; }
// Get maximum y coordinate
int CoordMatrix::GetMaxY() const
{ return maxy; }
// Get the file name
std::string CoordMatrix::GetFileTitle() const
{ return title; }
// Set up distance matrix between node pairs
void CoordMatrix::SetDistanceMatrix()
{
for ( int i = 0; i < (int) coords.size() - 1; i++ )
{
std::pair<int,int> p1 = coords.at( i );
int x1 = p1.first; int y1 = p1.second;
for ( int j = i + 1; j < (int) coords.size(); j++ )
{
std::pair<int,int> p2 = coords.at( j );
int x2 = p2.first; int y2 = p2.second;
double dist = 0.0;
if ( edge_weight_type == ATT )
{
dist = CalcPseudoEuclidDistance( x1, x2, y1, y2 );
}
else
{
dist = (double) sqrt( (double) ( x1 - x2 ) * ( x1 - x2 ) +
(double) ( y1 - y2 ) * ( y1 - y2 ) );
}
std::pair< int, int > p( i, j );
distMatrix[ p ] = dist;
}
}
}
// For edge weight type 'ATT'
// Pseudo Euclidean distance
int CoordMatrix::CalcPseudoEuclidDistance( const int& x1,
const int& x2,
const int& y1,
const int& y2 )
{
int dij = 0;
int xd = x1 - x2; int yd = y1 - y2;
double rij = sqrt( (xd*xd + yd*yd) / 10.0 );
int tij = round( rij );
if ( tij < rij )
dij = tij + 1;
else
dij = tij;
return dij;
}
Tour.h
#pragma once
#include "CoordMatrix.h"
#include <vector>
#include <set>
class Tour
{
public:
Tour();
Tour( const Tour& t );
Tour& operator=( const Tour& t );
~Tour();
void DoTwoOpt( const int& c1, const int& c2,
const int& c3, const int& c4 );
double TourDistance() const;
int TourSize() const;
int GetCity( const int& index );
void SetCity( const int& index, const int& value );
void SetMatrix( CoordMatrix* mat );
void CreateRandomTour();
void CreateTour();
void CreateNearestNeighbourTour();
void Reset();
void SetCities( const std::vector<int>& v );
private:
double Distance( const int& c1, const int& c2 ) const;
int GetNearestNeighbour( const int& c, std::set<int>& cset );
private:
std::vector< int > cities;
CoordMatrix* matrix;
};
Tour.cpp
#include "StdAfx.h"
#include "Tour.h"
#include <algorithm>
#include <functional>
Tour::Tour(){}
Tour::~Tour(){}
Tour::Tour( const Tour& t )
{ cities = t.cities; }
Tour& Tour::operator=( const Tour& t )
{
if ( this != &t )
cities = t.cities;
return *this;
}
void Tour::DoTwoOpt( const int& c1, const int& c2,
const int& c3, const int& c4 )
{
if ( c3 == c1 || c3 == c2 || c4 == c1 || c4 == c2 )
return;
int c1old = cities.at( c1 );
int c2old = cities.at( c2 );
int c3old = cities.at( c3 );
int c4old = cities.at( c4 );
double old_distance = TourDistance();
int tmp = cities.at( c2 );
cities[ c2 ] = cities.at( c3 );
cities[ c3 ] = tmp;
double new_distance = TourDistance();
if ( new_distance > old_distance )
{
cities[ c1 ] = c1old;
cities[ c2 ] = c2old;
cities[ c3 ] = c3old;
cities[ c4 ] = c4old;
}
}
// Get total distance of tour
double Tour::TourDistance() const
{
double dist = 0.0;
int size = (int) cities.size();
int c1, c2;
for ( int i = 0; i < size - 1; i++ ) {
c1 = cities.at( i );
c2 = cities.at( i + 1 );
dist += Distance( c1, c2 );
}
c1 = cities.at( size - 1 );
c2 = cities.at( 0 );
dist += Distance( c1, c2 );
return dist;
}
// Generate arbitrary tour
void Tour::CreateRandomTour()
{
Reset();
for ( int i = 0; i < matrix->size(); i++ )
cities.push_back( i );
random_shuffle( cities.begin() + 1, cities.end() );
}
// Generate arbitrary tour
void Tour::CreateTour()
{
Reset();
for ( int i = 0; i < matrix->size(); i++ )
cities.push_back( i );
}
// Get distance bewteen selected cities
double Tour::Distance( const int& c1,
const int& c2 ) const
{ return matrix->Distance( c1, c2 ); }
// Set pointer to cost / distance matrix object
void Tour::SetMatrix( CoordMatrix* mat )
{ matrix = mat; }
// Reset existing tour data
void Tour::Reset()
{ std::vector< int >().swap( cities ); }
// Return the number of cities in the tour
int Tour::TourSize() const
{ return (int) cities.size(); }
// Get the tour city, given the index passed to it
int Tour::GetCity( const int& index )
{
int node = cities.at( index );
return node;
}
// Get tour from the set of nearest neighbours
void Tour::CreateNearestNeighbourTour()
{
Reset();
std::set<int> city_set;
std::set<int>::iterator it;
for ( int i = 0; i < matrix->size(); i++ )
city_set.insert( i );
int city = 0;
for ( int i = 1; i <= matrix->size(); i++ )
{
cities.push_back( city );
it = city_set.find( city );
city_set.erase( it );
city = GetNearestNeighbour( city, city_set );
}
}
int Tour::GetNearestNeighbour( const int& c, std::set<int>& cset )
{
int city = 0;
double min_dist = 99999999;
std::set<int>::iterator cit;
for ( cit = cset.begin(); cit != cset.end(); cit++ ) {
int n = *cit;
if ( n == c ) continue;
double dist = Distance( c, n );
if ( dist < min_dist ) {
city = n;
min_dist = dist;
}
}
return city;
}
void Tour::SetCities( const std::vector<int>& v )
{ cities = v; }
void Tour::SetCity( const int& index, const int& value )
{ cities[ index ] = value; }
TSPalgorithm.h
#pragma once
#include "Tour.h"
#include <string>
class Observer;
class TSPalgorithm
{
public:
TSPalgorithm(void);
~TSPalgorithm(void);
void Initialize( const int& iterations, CoordMatrix* mat );
void TwoOptSwap( const int& i, const int& k );
void Run();
int GetTourCity( const int& index );
void AddObserver( Observer* ob );
void Notify( const int& dist );
private:
void TwoOpt();
private:
Tour tour, new_tour;
int iterations;
std::vector<Observer*> ob_set;
};
class Observer
{
public:
virtual void UpdateDisplay( const float& dist ) = 0;
};
TSPalgorithm.cpp
#include "StdAfx.h"
#include "TSPalgorithm.h"
TSPalgorithm::TSPalgorithm()
{}
TSPalgorithm::~TSPalgorithm()
{}
// Set up TSP problem to run
void TSPalgorithm::Initialize(
const int& iter,
CoordMatrix* mat )
{
tour.SetMatrix( mat );
new_tour.SetMatrix( mat );
iterations = iter;
}
// Run the optimization algorithm
void TSPalgorithm::Run()
{
tour.Reset();
tour.CreateNearestNeighbourTour();
TwoOpt();
}
// Get the tour node, given the index
int TSPalgorithm::GetTourCity( const int& index )
{
return tour.GetCity( index );
}
// Notify observers of changes
void TSPalgorithm::Notify( const int& dist )
{
for ( std::vector<Observer*>::iterator it = ob_set.begin();
it != ob_set.end();
it++ )
{
(*it)->UpdateDisplay( dist );
}
}
// Add observer
void TSPalgorithm::AddObserver( Observer* ob )
{
ob_set.push_back( ob );
}
// Do all 2-opt combinations
void TSPalgorithm::TwoOpt()
{
int size = tour.TourSize();
new_tour = tour;
bool improve = true;
double best_distance, new_distance;
while ( improve )
{
best_distance = tour.TourDistance();
improve = false;
for ( int i = 0; i < size - 1; i++ )
{
for ( int k = i + 1; k < size; k++)
{
TwoOptSwap( i, k );
new_distance = new_tour.TourDistance();
if ( new_distance < best_distance )
{
improve = true;
tour = new_tour;
best_distance = new_distance;
Notify( tour.TourDistance() );
i = size;
break;
}
}
}
}
}
void TSPalgorithm::TwoOptSwap( const int& i, const int& k )
{
for ( int c = 0; c <= i - 1; ++c )
{
new_tour.SetCity( c, tour.GetCity( c ) );
}
int dec = 0;
for ( int c = i; c <= k; ++c )
{
new_tour.SetCity( c, tour.GetCity( k - dec ) );
dec++;
}
for ( int c = k + 1; c < tour.TourSize(); ++c )
{
new_tour.SetCity( c, tour.GetCity( c ) );
}
}
MakeString.h
#include <fstream>
#include <sstream>
#include <string>
class make_string
{
public:
template <typename T>
make_string& operator<<( T const & datum )
{
buffer_ << datum;
return *this;
}
operator std::string () const
{ return buffer_.str(); }
private:
std::ostringstream buffer_;
};
Step 4: add the static control variables
In the Resource View, right-click the “Total Distance” static control you added and select Add Variable. Give it the variable name m_Distance:
Repeat this step for the “Tour” static control, giving it the variable name m_Tour. Notice that following this step will insert the CStatic controls in the dialog header class CTwoOptDlg.h and insert the DDX controls in CTwoOptDlg.cpp:
void CTwoOptDlg::DoDataExchange(CDataExchange* pDX)
{
CDialogEx::DoDataExchange(pDX);
DDX_Control(pDX, IDC_DISTANCE, m_Distance);
DDX_Control(pDX, IDC_TOUR, m_Tour);
}
Step 5: Implement the button event handling logic
In the Resource View, double-click the Run button to generate the event handler code in CTwoOptDlg.cpp for when this button is clicked.
Once this is generated, insert the following code inside OnBnClickedRun to invoke the algorithm and display updates:
void CTwoOptDlg::OnBnClickedRun()
{
alg.Run();
hasRun = true;
RedrawWindow( 0, 0, RDW_INVALIDATE | RDW_UPDATENOW | RDW_ERASE );
}
Do the same for the Open button: Double click the Open button to generate its event handler code, and insert the following code that will enable the user to open the desired *.tsp file:
RedrawWindow( 0, 0, RDW_INVALIDATE | RDW_UPDATENOW | RDW_ERASE );
}void CTwoOptDlg::OnBnClickedOpen()
{
CPaintDC dc(this);
CRect rect;
GetClientRect(&rect);
// Open the file opening dialog
CFileDialog fileDlg(
TRUE,
NULL,
NULL,
OFN_HIDEREADONLY | OFN_FILEMUSTEXIST,
(LPCTSTR) ".tsp Files(*.tsp)|*.tsp||",
this );
fileDlg.m_ofn.lpstrTitle = (LPCSTR)"Loading TSP Problem";
INT_PTR result = fileDlg.DoModal();
CString path = fileDlg.GetPathName();
if ( result == IDOK )
{
// Reset matrix data contents
CT2CA pszConvertedAnsiString( path );
std::string path_str( pszConvertedAnsiString );
mat.Initialize( path_str );
hasRun = false;
(AfxGetMainWnd( ))->SetWindowText(mat.GetFileTitle().c_str());
}
Step 6: Update the OnPaint method
Update OnPaint method to draw the current best solution found by the algorithm:
void CTwoOptDlg::OnPaint()
{
// device context for painting
CPaintDC dc(this);
if (IsIconic())
{
SendMessage(
WM_ICONERASEBKGND,
reinterpret_cast<WPARAM>(dc.GetSafeHdc()), 0);
// Center icon in client rectangle
int cxIcon = GetSystemMetrics(SM_CXICON);
int cyIcon = GetSystemMetrics(SM_CYICON);
CRect rect;
GetClientRect(&rect);
int x = (rect.Width() - cxIcon + 1) / 2;
int y = (rect.Height() - cyIcon + 1) / 2;
// Draw the icon
dc.DrawIcon(x, y, m_hIcon);
}
else
{
if ( mat.size() < 1 ) return;
CRect rect;
GetClientRect(&rect);
int rectx1 = rect.left + 20;
int rectx2 = rect.right - 150;
int recty1 = rect.top + 20;
int recty2 = rect.bottom - 140;
CPen pen( PS_SOLID, 1, RGB( 0, 0, 0 ) );
dc.SelectStockObject(BLACK_BRUSH);
int tour_size = mat.size();
for ( count = 0; count < tour_size; count++ )
{
xc1 = mat.GetX( count );
yc1 = mat.GetY( count );
xn1 = (float) ( xc1 - mat.GetMinX() ) /
(float) ( mat.GetMaxX() - mat.GetMinX() );
yn1 = (float) ( yc1 - mat.GetMinY() ) /
(float) ( mat.GetMaxY() - mat.GetMinY() );
xcoord1 = rectx1 + (int) (float) ( xn1 * abs( rectx1 - rectx2 ) );
ycoord1 = recty2 - (int) (float) ( yn1 * abs( recty1 - recty2 ) );
dc.Ellipse( xcoord1 - 2, ycoord1 - 2, xcoord1 + 2, ycoord1 + 2 );
if ( hasRun && count < tour_size - 1 )
{
cc1 = alg.GetTourCity( count );
cc2 = alg.GetTourCity( count + 1 );
xc1 = mat.GetX( cc1 );
yc1 = mat.GetY( cc1 );
xc2 = mat.GetX( cc2 );
yc2 = mat.GetY( cc2 );
xn1 = (float) ( xc1 - mat.GetMinX() ) /
(float) ( mat.GetMaxX() - mat.GetMinX() );
yn1 = (float) ( yc1 - mat.GetMinY() ) /
(float) ( mat.GetMaxY() - mat.GetMinY() );
xn2 = (float) ( xc2 - mat.GetMinX() ) /
(float) ( mat.GetMaxX() - mat.GetMinX() );
yn2 = (float) ( yc2 - mat.GetMinY() ) /
(float) ( mat.GetMaxY() - mat.GetMinY() );
xcoord1 = rectx1 + (int)(float)(xn1 * abs( rectx1 - rectx2));
ycoord1 = recty2 - (int)(float)(yn1 * abs( recty1 - recty2));
xcoord2 = rectx1 + (int)(float)(xn2 * abs( rectx1 - rectx2));
ycoord2 = recty2 - (int)(float)(yn2 * abs( recty1 - recty2));
dc.MoveTo( xcoord1, ycoord1 );
dc.LineTo( xcoord2, ycoord2 );
}
}
if ( hasRun )
{
cc1 = alg.GetTourCity( tour_size - 1 );
cc2 = alg.GetTourCity( 0 );
xc1 = mat.GetX( cc1 );
yc1 = mat.GetY( cc1 );
xc2 = mat.GetX( cc2 );
yc2 = mat.GetY( cc2 );
xn1 = (float) ( xc1 - mat.GetMinX() ) /
(float) ( mat.GetMaxX() - mat.GetMinX() );
yn1 = (float) ( yc1 - mat.GetMinY() ) /
(float) ( mat.GetMaxY() - mat.GetMinY() );
xn2 = (float) ( xc2 - mat.GetMinX() ) /
(float) ( mat.GetMaxX() - mat.GetMinX() );
yn2 = (float) ( yc2 - mat.GetMinY() ) /
(float) ( mat.GetMaxY() - mat.GetMinY() );
xcoord1 = rectx1 + (int) (float) ( xn1 * abs( rectx1 - rectx2 ) );
ycoord1 = recty2 - (int) (float) ( yn1 * abs( recty1 - recty2 ) );
xcoord2 = rectx1 + (int) (float) ( xn2 * abs( rectx1 - rectx2 ) );
ycoord2 = recty2 - (int) (float) ( yn2 * abs( recty1 - recty2 ) );
dc.MoveTo( xcoord1, ycoord1 );
dc.LineTo( xcoord2, ycoord2 );
}
CDialogEx::OnPaint();
}
}
Step 7: Add methods to initialize observer and refresh display
Insert this code to CTwoOptDlg.cpp to initialize the observer pattern and output the details of the best tour found:
void CTwoOptDlg::Init( TSPalgorithm* tsp )
{
alg.AddObserver( this );
}
void CTwoOptDlg::UpdateDisplay( const float& dist )
{
hasRun = true;
std::string s = make_string() << "Total distance: "
<< dist;
m_Distance.SetWindowText( s.c_str() );
int tour_size = mat.size();
std::string tour = make_string() << "Tour:\n";
std::string t;
for ( int i = 0; i < tour_size; i++ )
{
t = make_string() << alg.GetTourCity( i ) + 1
<< "-";
tour.append( t );
if ( i > 0 && i % 35 == 0 )
{
tour.append( "\n" );
}
}
t = make_string() << alg.GetTourCity( 0 ) + 1;
tour.append( t );
m_Tour.SetWindowText( tour.c_str() );
RedrawWindow(
0,
0,
RDW_INVALIDATE | RDW_UPDATENOW | RDW_ERASE );
}
Step 8: Ensure necessary headers are present in CTwoOptDlg.cpp and update OnInitDialog
Make sure the following headers are included in CTwoOptDlg.cpp:
#include "stdafx.h"
#include "Two-Opt.h"
#include "Two-OptDlg.h"
#include "MakeString.h"
#include <fstream>
#include <sstream>
#include <string>
#include "afxdialogex.h"
BOOL CTwoOptDlg::OnInitDialog()
{
CDialogEx::OnInitDialog();
SetIcon(m_hIcon, TRUE); // Set big icon
SetIcon(m_hIcon, FALSE); // Set small icon
Init( &alg );
alg.Initialize( 10000, &mat );
hasRun = false;
font.CreatePointFont(100, _T("Arial"));
m_Distance.SetFont(&font);
m_Tour.SetFont(&font);
GetDlgItem(IDC_DISTANCE)->SetFont(&font);
GetDlgItem(IDC_TOUR)->SetFont(&font);
return TRUE; // return TRUE unless you set the focus to a control
}
Step 9: Add additional variables and methods to the CTwoOptDlg class
This includes the TSPalgorithm and CoordMatrix objects and methods to initialize the observer and update the display. You can just copy and insert the complete CTwoOptDlg.h code listing shown here:
#pragma once
#include "TSPalgorithm.h"
#include "CoordMatrix.h"
#include "afxwin.h"
// CTwoOptDlg dialog
class CTwoOptDlg : public CDialogEx, Observer
{
// Construction
public:
CTwoOptDlg(CWnd* pParent = NULL);
// Dialog Data
enum { IDD = IDD_TWOOPT_DIALOG };
protected:
virtual void DoDataExchange(CDataExchange* pDX);
// Implementation
protected:
HICON m_hIcon;
// Generated message map functions
virtual BOOL OnInitDialog();
afx_msg void OnPaint();
afx_msg HCURSOR OnQueryDragIcon();
DECLARE_MESSAGE_MAP()
public:
afx_msg void OnBnClickedOk();
afx_msg void OnBnClickedOpen();
afx_msg void OnBnClickedRun();
void Init( TSPalgorithm* tsp );
void UpdateDisplay( const float& dist );
private:
TSPalgorithm alg;
CoordMatrix mat;
bool hasRun;
int cc1, cc2, xc1, xc2, yc1, yc2;
float xn1, xn2, yn1, yn2;
int xcoord1, xcoord2, ycoord1, ycoord2;
int x1, y1, count;
CStatic m_Distance, m_Tour;
LOGFONT lf;
CFont font;
};
Once the project is completed, using it is simple: download a test problem as a *.tsp file such as Att48.tsp, representing 48 capital cities of the USA:
http://www.technical-recipes.com/Downloads/att48.tsp
Click Open to load this test problem and then click Run.
To try out the algorithm, first click Open to load the test problem. This will represent the geographical locations of cities as a series of nodes:
Upon pressing Run, the 2-opt algorithm is applied to run through all two-edge combinations and find the best solution obtained from this process. The program will periodically update the graphical layout as the algorithm finds progressively better solutions.
Chapter Summary
To summarize this master lesson, you have learned how to:
·Apply the 2-opt algorithm in C++ to generate near-optimal solutions to traveling salesman test problems.
·Create a MFC dialog application and use standard drawing objects to present the results graphically.