Let’s look at one of the oldest examples of a graph problem. The idea comes from a real life problem where a salesperson needs to visit a series of cities to visit potential clients. A company wanted to find the most efficient path for him to take to visit all of the cities he needed to visit, without having him on the road traveling any longer than necessary.
Given that the salespeople needed to travel by road, you can’t simply go from one city to any other city. Some roads only connect certain cities, so you have to find the best route to travel. Additional variables might include not going to the same city more than once, or not having to travel more than X miles on a given leg of a trip.
Note: You can modify this problem to say that the salesperson has to travel by air, but planes only fly from one airport to another, and they don’t always fly to every airport, or everyday. However, this tends to add an unnecessary amount of complexity to this problem.
While this seems complicated at first, it turns out this information can be stored inside of a graph.
When you think about graphs, vertices and edges, start to look like maps, streets, and intersections, and thus can be used to develop a path between two points. The traveling salesperson starts looking only at city level logistics, not needing to look at small things like streets.
Note: Many companies do this. They may only look to place stores near interstates to simplify their logistics. Consider restaurants like Cracker Barrel which seem to only be on an interstate exit or Costco which always seem to be located within just a few miles of an interstate. Even Sam’s Club – which isn’t always off an interstate, is located near a neighboring Walmart. Sometimes even sharing a parking lot, but rarely more than across an intersection, to simplify their logistics.
Many systems use this as a basis to work, everything from AI systems in games looking for paths for them to take, to mapping software. We can see it’s effects in other software styles as well, but how do you go about finding a good path?
Well, generally, you work on creating a greedy algorithm. This is a sub-set of the divide and conquer. That is an algorithm that seems to take the best option immediately available to it. How? Well we start with a depth first search, looking at which option is the best to take right now by starting with the smallest leg.
We look at our starting point, and find all of the possible vertices that we need to travel to.. We add the node to our checked list, and then pick the closest node first to see if it takes us to our destination. We repeat this process until one of two things happens in our first attempt. 1) we either reach the destination with all required nodes being visited or 2) we reach a dead end where we can only go down a path that has already been tried.
This means we have to keep track of what vertices we’ve visited, as well as how long our path is. The second is important if we want to find the best path – in that we must start trying other paths. Those will end with either one of the first two cases, or a third case – we find that the new route is longer than a previous route.
Because we are looking for the shortest path we can look for the smallest edges to find the best route. This can be useful for more than just salespeople. This methodology is used in finding routing patterns for networks, road way directions, infrastructure routines, etc.
The problem arises when our graphs start to grow with more and more vertices. Especially as we add vertices of locations which we don’t necessarily need to visit. As the graph becomes complex, and if multiple vertices connect to other multiple vertices, then we start taking a long time to calculate.
This becomes more challenging as we work on adding additional routes, like the original Traveling Salesman problem postulates.
Luckily, we are usually limited by logical constraints and have only so many stops to make per trip, which keeps this problem relatively simple to solve.
The Traveling Salesperson was originally found on Access 2 Learn
