tsp.cpp

solving travelling sellsman problem

#include "PCTimer.h"
#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;

// #define SUPPRESSOUTPUT
#define INFINITY (-((1 << 31)+1))

void error(char * msg)
{
    cerr << "Error: " << msg << endl;
    exit(-1);
}

enum CityStatus {UNUSED, USED};

struct City
{
    int id;
    int X;
    int Y;
    CityStatus status;

    City()
        : id(0), X(0), Y(0)
    {
    }

    friend ostream & operator << (ostream & out, City & v)
    {
        return out << "(" << v.id << "," << v.X << "," << v.Y << ")";
    }

    friend ostream & operator << (ostream & out, City * v)
    {
        if (v)
            out << *v;
        else
            cout << " NULL City ";
        return out;
    }

};

template
    <class T>
struct ListNode
{
    T info;
    double cost;
    ListNode<T> * next;

    ListNode<T>(T t, double cst, ListNode<T> * n)
        : info(t), cost(cst), next(n)
    {
    }

    ListNode<T>(T t, ListNode<T> * n)
        : info(t), cost(0.0), next(n)
    {
    }

    static void deleteList(ListNode<T> * l)
    {
        if (l)
        {
            deleteList(l->next);
            delete l;
        }
    }

    static void print(ostream & out, ListNode<T> * l)
    {
        if (l)
        {
            print(out, l->next);
            out << l->info;
        }
    }

    friend ostream & operator << (ostream & out, ListNode<T> * l)
    {
#ifndef SUPPRESSOUTPUT
        out << l->cost  << " ";
        print(out, l);
        out << endl;
#endif
        return out;
    }

};

typedef ListNode<City *> CityListNode, * CityList;
typedef ListNode<CityList> PathListNode, * PathList;

class Holder // this is currently a stack, could be queue, or priority queue
{
    PathList head;
public:
    Holder()
        : head(NULL)
    {
    }

    void insert(CityList cl)
    {
        head = new PathListNode(cl, head);
    }

    CityList remove()
    {
        CityList ret = NULL;
        if (head)
        {
            ret = head->info;
            PathList temp = head;
            head = head->next;
            delete temp;
        }
        return ret;
    }

};



// Vertices are integers from 0 to N-1

class TSPTour
{
    City * cities; // an array of Cities
    int maxSize;
    int size;
    Holder holder;
    int paths;
    double bestPathCost;
    CityList bestPath;
public:

    TSPTour(char fileName[])
    {
        int value, X, Y;
        paths = 0;
        bestPathCost = INFINITY;
        bestPath = NULL;
        ifstream in(fileName);
        if (in >> value) {
            maxSize = size = value;
            cities = new City[size];
        }
        else
            error("file not found");
        for ( int i=0; i < size; ++i )
        {
            City &v = cities[i];
            v.id = i;
            if (!(in >> X >> Y))
                break;
            v.X = X;
            v.Y = Y;
        }
        in.close();
    }
	
	void reset()
	{
		paths = 0;
        bestPathCost = INFINITY;
		bestPath->deleteList(bestPath);
		bestPath = NULL;
	}
	
	void setSize(int s)
	{
		if (s>maxSize)
		    error("invalid size");
		size=s;
	}

     double distanceBetween(int i, int j)
     {
          City & v1 = cities[i];
          City & v2 = cities[j];
          int DeltaX = v1.X - v2.X;
          int DeltaY = v1.Y - v2.Y;
          return sqrt(DeltaX*DeltaX + DeltaY*DeltaY);
     }

    friend ostream & operator << (ostream & out, TSPTour & g)
    {
        for ( int i=0; i < g.size; ++i )
            out << i << " " << g.cities[i] << endl;
        return out;
    }

    int time;

    void markUsedCities(CityList partialPath)
    {
        for ( int i=0; i < size; ++i )
        {
            City & c = cities[i];
            c.status = UNUSED;
        }
        for (CityList p = partialPath; p; p=p->next)
        {
            City & c = * p->info;
            c.status = USED;
        }
    }

    CityList addCityToPath(CityList partialPath, int newCity)
    {
        City & parentCity = * partialPath->info;
        double parentCost = partialPath->cost;
        int parentId = parentCity.id;
        double cost = parentCost + distanceBetween(parentId, newCity);
        return new CityListNode(&cities[newCity], cost, partialPath);
    }

    bool addUnusedCities(CityList partialPath)
    {
        bool expanded = false;
        for ( int i=0; i < size; ++i )
        {
            City & c = cities[i];
            if (c.status == UNUSED)
            {
                CityList newList = addCityToPath(partialPath, i);
                holder.insert(newList);
                expanded = true;
            }
        }
        return expanded;
    }
	
	bool needPrune(CityList partialPath)  //using bound 2 to determine if partialPath need to be pruned
	{
		markUsedCities(partialPath);
		double mindist=INFINITY;
		City & parentCity = * partialPath->info;
        double parentCost = partialPath->cost;
        int parentId = parentCity.id; 
		int count=0;
		for ( int i=0; i < size; ++i )
        {
            City & c = cities[i];
            if (c.status == UNUSED)
            {
				count++;
			    double dist=distanceBetween(parentId, i);
				if (dist<mindist)
				     mindist=dist;
            }
        }
		if (count==0)
		     return false;
		else
		{
		if (parentCost+2*mindist>bestPathCost)
		    return true;
	    else
		    return false;
		}
	}
	
    bool generatedSuccessors(CityList partialPath)
    {
        markUsedCities(partialPath);
        return addUnusedCities(partialPath);
    }

    void checkSolution(CityList cl)
    {
        City & parentCity = * cl->info;
        double parentCost = cl->cost;
        if (parentCost < bestPathCost)
        {
            bestPathCost = parentCost;
            bestPath = cl;
            cout << "New Best: " << cl;
        }
        
    }

    void solve_DFS() //normal DFS way
    {
		PCTimer t;
		t.start();
        CityList startState = new CityListNode(&cities[0], NULL);
        holder.insert(startState);
        while ( CityList cl =  holder.remove() )
        {
            if (!generatedSuccessors(cl))
            {
                cl = addCityToPath(cl, 0);
                paths++;
                checkSolution(cl);
            }
        }
		t.stop();
		printf("DFS using time: %f\n", t.elapsedTime());
    }
	
	void solve_prunedDFS1() //Pruned DFS use bound 1
    {
		PCTimer t;
		t.start();
        CityList startState = new CityListNode(&cities[0], NULL);
        holder.insert(startState);
        while ( CityList cl =  holder.remove() )
        {
			if (cl->cost>bestPathCost)
			    continue; 
            if (!generatedSuccessors(cl))
            {
                cl = addCityToPath(cl, 0);
                paths++;
                checkSolution(cl);
            }
        }
		t.stop();
		printf("pruned DFS by bound 1 using time: %f\n", t.elapsedTime());
    }

	void solve_prunedDFS2()  //pruned DFS using bound 2
    {
		PCTimer t;
		t.start();
        CityList startState = new CityListNode(&cities[0], NULL);
        holder.insert(startState);
        while ( CityList cl =  holder.remove() )
        {
			if (needPrune(cl))
			     continue;
            if (!addUnusedCities(cl))
            {
                cl = addCityToPath(cl, 0);
                paths++;
                checkSolution(cl);
            }
        }
		t.stop();
		printf("prunedDFS2 using time: %f\n", t.elapsedTime());
    }
    ~TSPTour()
    {
        cout << "Found " << paths << " paths\n";
        delete[] cities;
    }

};


int main()
{
    TSPTour T("D:\\MyWorkSpace\\tsp.txt");
	int a;
	cout <<"number of cities:";
	cin>>a;
	T.setSize(a);
    cout << T << endl;
    cout << "DFS:"<< endl;
	T.solve_DFS();
	T.reset();
	cout<<endl;
	cout << "pruned DFS bound 1:"<<endl;
	T.solve_prunedDFS1();
	T.reset();
	cout<<endl;
	cout << "pruned DFS bound 2:"<<endl;
	T.solve_prunedDFS2();
	cin>>a;
    return 0;
}