Month
Month
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.
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
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: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 ===========
// ===================================== 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);
}