TGIMBA Automation – The Traveling Salesman and Permutation Algorithm Proof of Concept

Source Code – https://github.com/ehelin/Algorithms (get the commit closest to the date of this blog)

As I continue to create blog entries based on an interest that I have at a particular time, it is dawning how much I jump around.  At first, I was concerned about this.  But, after thinking about it more, it seems like this is how I handle having a wide variety of topics I care about.  For example, I have made only made a few blog entries on ‘The Globe In My Bucket Application’ (TGIMBA). This supposed to be my ‘main’ application that I use to learn new technologies/languages/etc.  Instead of creating a new application (which can take quite a while to get a stable code base) every time I wanted to explore another language, I was supposed to add it to TGIMBA.  However, my last half dozen blog entries deal with the cloud or something else.  I am getting back on track with this blog post, but I mention this because of how long my ‘technology to learn’ list is.  I would do this even if I didn’t have to work for a living.  So, if you were ever trying to determine if something is a hobby or work, ask yourself if it is fun or not and you will have your answer 🙂

Another point – given my incredibly long technology play list, picking up a project for a while, putting it back on the shelf and then picking it up later again does seem to be an effective way to spend time on all your projects.  At least it has been for me so far 🙂

Ok, this blog entry will deal with TGIMBA automation.  More specifically, a Proof Of Concept (POC) for that automation.  What do I mean by TGIMBA automation?  In this context, I mean non-website/mobile application event driven processing.  By itself, TGIMBA is a website/mobile application that is entirely event driven.  Users login, add bucket list items, delete a few, review the list and then log out.  There is nothing else.  So, to offer more features, some off-line processing is necessary.  When I first envisioned this, I thought about doing the automation in Node.js.  A couple of hurdles have deferred this (Node.js will eventually be the solution as I believe moving forward, JavaScript is rapidly becoming the language of choice) for now.  So, not wanting to lose time, the automation will initially take the form of a C# application.

The first feature I want to offer is an implementation of the traveling salesman algorithm.  Of course, I would not call it this for TGIMBA users.  For them, this will be a feature they can turn off or on (always, always give your users a choice…good rule of thumb) that will give them the fastest way to see their bucket list items that are location based.  The overall feature would involve identifying any location based bucket list items and then calculating the fastest (distance wise) way they can see all of these bucket list items together.

So, to start, I did a little reading on what the traveling salesman algorithm was conceptually and then started out to come up with a small POC.  My first attempt (I left all of the commits to chart my progress in case anyone wants to see this) was not so great.  Among other things, it dawned on me that I was not getting all of the possible location permutations.  More specifically, I treated ‘locations’ as ‘cities’ in the POC and I was missing some combinations.  So, I put the Traveling Salesman Algorithm aside and started on a permutation algorithm.

I found a pattern after reviewing different combinations and came up with what I thought would work.  It is quite possible this is also someone else’s solution, but I purposely try to hack my way through an implementation completely on my own without research to see what I can come up with.  I also find it helps me remember more.  I went through about 5-6 versions before coming up with one that seems to work up to 10 characters.  In reality, I will need to refactor it more to handle up to 40-50 locations (probably more).  However, for the POC, it seems enough.

The algorithm is fairly basic.  Major steps are:

  • Get factorial of the character count so you know how many permutations to expect
  • Sort characters in ascending order
  • Flip last two (from the right)
  • Increment the next position (from the right) until you have gotten the max value in the list of characters and sort in ascending order to the right of this position.

Continue in this manner moving towards the left of the character list until the iteration count matches the factorial.  If successful, the character list will be sorted in descending order as the result of the algorithm.  At least this is what I have observed.  I have added a test suite to test each option.  As I refactor this to handle larger lists of characters, I will add more tests.  They will just take a while to run!

PermutationAlgorithm

So now armed with the new permutation algorithm, I went back to the Traveling Salesman Algorithm.  For each city (ten in this simulation), these steps are performed:

  • Get a list of the other cities and the distance from this city to each one.
  • Get a permutation list of all possible city visit combinations starting from one city and then ending back on that city.
  • Record the result.

Initially, all of the ‘routes’ to visit the different cities came up with same distance and I thought this was an error.  It still may be an error, but I am starting to think the lowest cost order of cities is the same no matter what city you start from.  Oh well…time will tell.

TravelingSalesman

One thing I like to do when learning something is take the ‘out of the box’ or ‘layman’s’ approach.  More specifically, what can I do with a particular technology without much research.  For both algorithms, I took the brute force route.  I am certain there are better ways to approach these two algorithms, but by starting in this manner, I hope to retain more 🙂

Stay tuned!

References

  1. https://simple.wikipedia.org/wiki/Travelling_salesman_problem
Advertisements

One thought on “TGIMBA Automation – The Traveling Salesman and Permutation Algorithm Proof of Concept

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s