## Travelling Salesperson

**Deprecated**: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in

**/home/fnasim4196/nasim.org/blog/wp-includes/functions-formatting.php**on line

**76**

I’m taking an AI course this year and we have started to study some algorithms which will involve graph and tree traversals. For starters, we were given a very stripped down version of the travelling salesperson algorithm to work out in C/C++/C#/etc. The graph is undirected and each city can be visited only once, the salesperson must start from A, visit all cities and come back to city A. The values along the paths are the cost associated to the travel to each city. The task was to devise an algorithm which would compute all the possible paths and would give the total cost of each route. I devised a generic solution (it still can’t do city repetitions and it assumes that all cities are to visited). The first algorithm was aimed at solving the problem at hand and was a quick and dirty solution to get the job done. It wasn’t thread-safe and it used fixed-size data structures. The output was as follows:

ABCDEA - Cost: 940

ABCEDA - Cost: 920

ABDCEA - Cost: 920

ABDECA - Cost: 995

ABECDA - Cost: 875

ABEDCA - Cost: 970

ACBDEA - Cost: 975

ACBEDA - Cost: 930

ACDBEA - Cost: 930

ACDEBA - Cost: 970

ACEBDA - Cost: 910

ACEDBA - Cost: 995

ADBCEA - Cost: 880

ADBECA - Cost: 910

ADCBEA - Cost: 855

ADCEBA - Cost: 875

ADEBCA - Cost: 930

ADECBA - Cost: 920

AEBCDA - Cost: 855

AEBDCA - Cost: 930

AECBDA - Cost: 880

AECDBA - Cost: 920

AEDBCA - Cost: 975

AEDCBA - Cost: 940

Smallest Cost: 855

After that I redesigned the solution to be thread-safe and more organized with lesser hacks. I still have to incorporate a bunch of features. Here is what the header of tsp3.cpp reads:

// TODO:

// MUST VISIT: allow user to Nodes.mustvisit (char) for nodes that MUST be in the solution

// ALLOW REPEAT: a flag which tells us if cities can be revisited to find the most optimal solution

// TRAVEL: Nodes.Travel(src,dest) and take into account MUST VISIT and ALLOW REPEAT and give possible solutions

The solution I designed inherently supported directed and undirected graphs so that is one less thing on the TODO list.