( Index )
Month
Ubuntu g++

Brief Information about the Sept '11 CSIG Meeting

TSP - Traveling Salesman Problem

Microsoft C++ and Visual Studio

Written by B. Arnold

Welcome to the CSIG, a Special Interest Group of the ACGNJ. We will be discussing Windows Programming using Visual C++  from Microsoft.

First, let me welcome everyone back from their Summer activities.

Travelling Salesman Problem

The subject for this month is an extremely simple version of the Travelling Salesman Problem. The program uses a "Command Box" which is similar to a "Dos Box" and does not use any of the Windows Graphic libraries. It is very easy to understand. The code uses the C++ compiler in Microsoft's Visual Studio 2008 and may also be compiled using the free C++ Express compiler. Some of the items that we will discuss are as follows.

Windows Programming with Microsoft Managed code
Microsoft Visual Studio 2008
Debugging
Text Processing and Console I/O
OOP - Object Oriented Programming
The Monte Carlo Algorithm

The TRAVELLING SALESMAN PROBLEM (TSP) is a classic computer subject. There are probably over 100 web sites devoted to TSP discussions. Here's something from Wikipedia:

Travelling salesman problem
From Wikipedia, the free encyclopedia

The travelling salesman problem (TSP) is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once. The problem was first formulated as a mathematical problem in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved.

My goal at this meeting is not to discuss 3rd year Computer Science algorithms. The goal is to discuss relative simple text based programming using C++ with OOP or Object Oriented Programming techniques. I choose the TSP because it is easily understood by most people. Here's an example: You want to visit the center of 9 cities and you wish to choose a route that minimizes travel distance. At the right is a screen shot showing the results of the program. This TSP solution is very simple in that it uses a Monte Carlo technique. This algorithm guesses at a solution using random numbers and then finds the best solution. It is only useful for small groups of cities, lets say 20 or so, because after that the number of permutations of possible paths become astronomical. Because it is a text based C++ program, it is quite fast. This implimentation checks 10 million possible solutions in only a few seconds.

The algorithm takes as input a list of town names and their corresponding coordinates in latitude and longitude. But, where do you get the numbers? If you enter a location in Google Maps (maps.google.com) and then right-click on the balloon marker to select "what's here?", Google puts the numbers in the search bar. They can then be pasted into this program. For example: Fanwood, NJ = 40.641638,-74.383407 degrees.

This month we will solve the problem using text mode code. Time permitting, I will also discuss a version developed under Linux Ubuntu Code-Blocks g++. Next month the plan is to graph the results using graphics based Windows code.

Text processing is an area that C++ programs shine above all other languages. The code produced is usually quite compact and ultra fast. Last year I wrote a program for doing text replacement in a data file. The user had to convert extra characters from a Mainframe dump into readable text. The source was a 10 Megabyte text file and the processing took about 1 hour of actual computer time to accomplish the replacement using Notepad. The operation was repeated daily. My program, using normal C++ functions, took about 20 seconds! The user was dumbfounded.

This is an exciting time for the C Language programming since Microsoft now has 4 different language compilers: C++, C++ Express, C-Sharp, and C-Sharp Express. These are all capable of creating Windows (tm) programs and the "Express" versions are free ! I see also that Microsoft is advertising a still newer version, Visual Studio 2010. Additionally, there are other companies making free and almost free compilers. Here's a link with many compilers: http://www.willus.com/ccomp.shtml

Microsoft .NET Framework

This is a large package, over 24 Megs. Most people running updated versions of Windows will already have it on their computer. If not, it may be downloaded from Microsoft.

Here's the download address for the Microsoft Framework:
Microsoft Software
Or, just look for: Microsoft .NET Framework Version x.x Redistributable Package (x86)

There are a number of ways to refer to this compiler and code.

The beginning of the evening (starting at 7:30pm) will be a RANDOM ACCESS discussion. The main presentation will discuss the program.

Our download site has code and programs from most of our meetings. ( Source Code Files )

Sample Code -

Sample Code
===========
// ===================================== CLASS CITY ====================================
ref class CCity
	{
	public:
	CCity(double latitude, double longitude, String ^city)
		{
		mLat = latitude;
		mLong= longitude;
		mCity= gcnew String(city);
		};
	~CCity() {};
	String ^mCity;
	double mLat;
	double mLong;
	};

// ================================ CLASS TRAVELING SALESMAN PROBLEM ==================
ref class CTsp
	{
	public:
	CTsp()
		{
		latFactor = 70.0; // miles per degree. NS (Central NJ)
		longFactor = 49.0; // miles per degree. EW
		cityCount = 0;
		cityArray = gcnew array<CCity ^>(10);
		Map = gcnew array<Int32>(10);
		MapBest = gcnew array<Int32>(10);
		};
	~CTsp()
		{
		for (int i=0; i<cityCount; i++)
			delete [] cityArray[i];
		delete [] cityArray;
		delete [] Map;
		delete [] MapBest;
		};
	void GoMonte();
	void ConShowCities();
	void AddCity(double latitude, double longitude, String ^city);
	double CalcDistance();
	double CalcVector(int city1, int city2);
	void ScrambleArray();
	int cityCount;
	double latFactor;
	double longFactor;
	double distance;
	double bestDist;
	array<Int32> ^Map;
	array<Int32> ^MapBest;
	array<CCity ^> ^cityArray;
	CShuffle ^RandomDigit;
	};

//
// Initialize the next record.
//
void CTsp::AddCity(double latitude, double longitude, String ^city)
	{
	if (cityCount == cityArray->GetLength(0))
		{
		Array::Resize(cityArray, cityCount + 100);
		Array::Resize(Map, cityCount + 100);
		Array::Resize(MapBest, cityCount + 100);
		}
	cityArray[cityCount++] = gcnew CCity(latitude, longitude, city);
	}



"Random Access" questions start at 7:30 Tuesday night.

SOURCE CODE

Source Code Files

For help, email me at b a r n o l d @ i e e e . o r g
Back to C++ Main Page