Solving the Problems of Azeroth

My Mage managed to ding level 56 last night, while thinning out the population of Un'goro Crater. As I systematically eliminated a variety of Pterodax, Ooze, and Dinos I realized that I was racking up requirements for no less than 4 quests simultaneously. It's not unusual to see the counters up for 1 or even 2 quests at a time, but...4?

Amazing.

I mentioned previously that I'm following a leveling guide, at least for the past few levels, and I am truly in awe of the person who put it together. It reminds me of something from my college days that I thought would never have a practical application. Let me explain.

One of my classes in the field of Operations Research involved methods of solving difficult problems. Perhaps the most difficult problem is the Traveling Salesman Problem. This is a classic problem that has been taught for many, many years. Here's how it goes:

A traveling salesman needs to make sales calls in 4 different cities. Given the distance between each city find the optimal (shortest) route which includes all cities only once and returns to the starting point.

At first glance this may not seem to be a difficult problem to solve, and in fact if you only have 4 cities you can probably look at a map and figure out the fastest route. But...if you add additional cities, say 10 or 20 or more, it then becomes much more difficult.

There are only two way to solve this problem. The brute force method involves computing each possible combination of paths in turn and then selecting the shortest one. The number of possible routes for 4 cities is 4! (4 factorial), which is 4x3x2x1 = 24 possible routes. This is certainly manageable, tedious with pencil and paper, but simple if you use a computer. As you increase the number of cities, however, it gets exponentially harder.

Number of Cities	Possible Routes
5	120
10	103,628,800
15	1,307,674,368,000

Using a computer, you could still use the brute force method, but even a computer takes a good long time to calculate and compare over a trillion possibilities.

The second way to approach the problem is by using some sort of heuristic method. This essentially means that you make a series of educated guesses as to a good route, then compare other possible routes to your guess to see if they are better or worse. There are several possible algorithms designed to tackle this, and using any one of them you will get a good answer, but you will never be able to prove that you have the best route since you didn't test all of the possibilities. Looking at the map to guess which route is best for the initial example of 4 cities was essentially an heuristic method, since you would be eliminating the obviously longer routes based on your innate perception of distance. Unfortunately once you increase the number of cities you quickly outstrip the capability of this common-sense approach.

The point of this little ramble is that creating a leveling guide is much like solving the traveling salesman problem. Each quest is like a city, but even more complicated, because there are not only locations for quests, but also varying degrees of travel difficulty, different modes of transport available to different classes of characters, and prerequisites. There can also be multiple requirements for each quest, and they can begin and end in different locations. In short, a huge number of variations which would make the brute force approach to solving the problem even more daunting. There are also several constraints which limit the possible routes to take in completing quests, such as quests available only to one faction, race, class, or profession. And of course the menu of possible quests changes as you progress through the levels with new ones popping up and old ones going gray.

I'm pretty sure that the guide's creator didn't use the brute force approach, since in addition to requiring a huge amount of time and computing resources to solve, it would also require an extensive database of quest information to be compiled and programmed. Therefore the guide must be the result of an heuristic solution, otherwise known as educated guessing confirmed by experience gained by leveling multiple characters. I'd go even further and guess that the convergence of 4 simultaneous quests was more of a happy coincidence than a planned outcome. If I were to try to create a guide, here's how I would proceed.

First, I would narrow down the possible quests by faction and level, and then use Thottbot to find the ones with the largest XP rewards. Then, I'd try to find those featuring common locations and try to group them together. Finally, I'd draw myself a map and try stringing them together in several different ways. Once I had a route that looked pretty good, I'd run a character through it making careful notes on locations, the collection of items, and the rewards gained.

This is certainly a very tedious and time consuming approach, made even worse by the fact that it takes a considerable amount of time to get the test characters to the right level in the first place. And of course there's no way to guarantee that I would find the best solution, in fact my route might only be mediocre. Bet even so, it would still be much better and faster than randomly wandering through quest-givers never knowing if there was a better way.

So, to those who have taken the time to create a leveling guide, my hat is off to you, and you have my thanks. There may in fact be a better and faster way to level a character than your way, but I doubt that we will ever know for sure.

For more information on the Traveling Salesman Problem click here.