Abstract: In this post, we look at how to find the shortest path through a subset of nodes. We reduce the problem to the Traveling Salesperson Problem, and show how our solution is optimal. There is also a discussion on what NP-hard problems are, and why finding a solution to our problem is hard.
Ticket to Ride is a modern day classic, and a game we have looked at before. (For a look at how Ticket to Ride plays look at first post – Ticket to Ride and Dijkstra’s algorithm) In our last post on Ticket to Ride, we looked at how we can use Graph Theory to analyze Ticket to Ride. By using Dijkstra’s algorithm we can find the shortest route between any two cities. This allows us to find the most optimal route when trying to complete ticket cards. However, during most games, players will have multiple tickets in there hand, and will need to find the shortest path between multiple cities.
First, we must define our problem statement. Giving a undirected graph G = (V, E), we must find the shortest path between a subset of nodes. While this seems like a problem that wouldn’t be that hard to solve, it turns out to actually be quite hard. In fact, it is what we would call NP-Hard. I have previously touched on the subject of NP and complexity theory before, but will give a refresher before moving on to the definition of NP-Hard.
NP is a class of programs that are easy to verify, but hard to solve. Essentially, there exists a polynomial or efficient (technically the polynomial could be 200, in which case it is not really efficient) runtime algorithm to verify if a solution is correct. However, no polynomial time algorithm exists for find said solution.
NP-Hard problems are problems that are at least as hard as the hardest problems in NP (we call these problems NP-Complete, and NP-Completeness will likely be looked at in a future post). When we say a problem is NP-Hard we are essentially giving the difficulty of computing a solution a lower bound. Located on the right, is a graph detailing the relationships between the different complexity classes. However, this graph makes a (somewhat big) assumption – P != NP. Or, that problems with a polynomial verifier, don’t have an efficient algorithm to solve.
Currently, the theoretical computer science community believes that P != NP. Many smart people have spent there whole lives trying to find a efficient algorithm for NP problems, and have failed to do so. As such, we shall continue assuming that P != NP.
The solution to our problem takes two parts. The first, its the Floyd–Warshall algorithm, and the second is a brute force algorithm.
The purpose of the Floyd-Warshall algorithm is to find the shortest path between all pairs of nodes. We do this so that we can simplify the graph. Because we only care about a certain subset of nodes, we can use the shortest paths between them for our brute force algorithm. This can also be proved to be optimal.
First, we assume a shorter path between the nodes exists (V0 -> V1 -> V2 -> … ->VF= D(k). We know the distance between the nodes Vi -> Vi+1 must be at least the smallest, per the correctness of the Floyd-Warshall algorithm. Because we only need to connect a subset of the nodes, and we know that the shortest path between those nodes is found by Floyd-Warshall, we can reduce the graph to just the subset of required nodes. Each node has an edge to all other nodes with the weight being that of the shortest path found by Floyd-Warshall.
The Floyd-Warshall algorithm, is basically multiple nested for loop comparisons. It works by repeatedly finding better paths between a pair of nodes, until the optimal path is found. We start by finding the shortest path between two nodes I & J with a distance of 1, increasing all the way to N (N is the number the nodes). My implementation for the algorithm is seen below.
# Floyd–Warshall algorithm
def findAllShortestPaths(cityList):
routes = getAllRoutes(cityList)
rows, cols = (len(cityList), len(cityList))
# This generates nested arrays for easy indexing
dist = dict()
for city in cityList:
dist[city.getName()] = dict()
for city2 in cityList:
dist[city.getName()][city2.getName()] = 100
next = dict()
for city in cityList:
next[city.getName()] = dict()
for city2 in cityList:
next[city.getName()][city2.getName()] = None
for route in routes:
dist[route.city1][route.city2] = route.cost
dist[route.city2][route.city1] = route.cost
next[route.city1][route.city2] = route.city2
next[route.city2][route.city1] = route.city1
for city in cityList:
dist[city.name][city.name] = 0
next[city.name][city.name] = 0
for k in cityList:
for i in cityList:
for j in cityList:
if dist[i.name][j.name] > dist[i.name][k.name] + dist[k.name][j.name]:
dist[i.name][j.name] = dist[i.name][k.name] + dist[k.name][j.name]
next[i.name][j.name] = next[i.name][k.name]
return dist, next
There are a couple of interesting things about this implementation. First, this implementation uses nested dictionaries instead of 2-D arrays, as the graph is represented through classes which use strings as the node names. Second, the implementation also doubles when adding the initial routes to the 2-D array. Why is that the case you ask? Basically I’m lazy, and didn’t want to type everything twice. Third, a second 2-D dictionary stores the next node in the shortest path allowing us to quickly find the shortest path between all of our nodes.
Once we have reduced the graph, we are left with a version of the Traveling Salesperson Problem. A classic computer science problem which tries to figure out what is the shortest path between all the nodes. This problem is NP-Hard (defined earlier) which means that computing the answer is going to take some time.
To solve the Traveling Salesperson Problem brute force algorithm. Although a slightly more “efficient” (still exponential) dynamic programing solution excises for solving this problem, I elected not to implement it as it could be a future post, and is not needed for the small number of nodes here. (In most games of ticket to ride, you are connecting 6-10 cities, which can be solved in about a minute.)
To search through all possible orderings I used a recursive function to generate and test each combination. The implementation is given below.
def solveTSP(cityGraph, nextCity):
global bestPath
global currentSmallest
global currentOrder
if len(cityGraph) == 1:
counter = 0
for route in currentOrder:
counter += route.cost
if counter < currentSmallest:
currentSmallest = counter
bestPath = copy.deepcopy(currentOrder)
elif nextCity is None:
for city in cityGraph:
cityGraph.remove(city)
for route in city.getRoutes():
currentOrder.append(route)
solveTSP(cityGraph, route.city2)
currentOrder.pop()
cityGraph.append(city)
else:
nextCity = findCity(cityGraph, nextCity)
for route in nextCity.getRoutes():
if cityIsAvailable(cityGraph, route):
currentOrder.append(route)
solveTSP(cityGraph, route.city2)
currentOrder.pop()
cityGraph.append(nextCity)
Once the shortest path between all of the “important” nodes has been found, we can work our way through the next dictionary, taking the shortest path between all of our nodes. Once that is done, we have our answer. The shortest path possible that connects all of our ticket cards! One thing to note. This is not necessarily the only shortest path. It is possible that more than 1 path exists with the same weight, however no path can exists that has a smaller weight.
Final Thoughts and Conclusions: Somewhat of a simpler project this week, as I am just utilizing already established algorithms. However, there where still some implementation challenges. Ticket to Ride and Graph Algorithms are sure to return, as not only are graphs super useful, they are also fun!
As for a future project, I am unsure of what is likely to come next. More than likely it will be something smaller that is contained to a single post. I still would like to attempt an AI that lacks perfect information, however I am unsure of which game it will be on. Lost Cities still remains a strong contender, but we shall see. As always the code is located down below, and thanks for reading!
The Board Game Scholar 