A Traveling Salesman Problem Example

Let’s say that you are trying to solve the traveling salesman problem. Let us compare two particular approaches: Random and Greedy. We will use a small subset of New York cities (NYC, Rochester, Albany, Syracuse).

Random Algorithm:

1. Pick a random starting city from (NYC, Rochester, Albany, Syracuse).
Let us start with Rochester. 
Chosen Cities = (Rochester)

2. Pick a random unchosen city from `(NYC, Albany, Syracuse)`
  Let us pick NYC (that’s 333 miles)
Chosen Cities = (Rochester, NYC)

2. Pick a random unchosen city from (Albany, Syracuse)
  Let us pick Syracuse (that’s 247 miles)
  Chosen Cities = (Rochester, NYC, Syracuse)

2. Pick a random unchosen city from (Albany)
  Let us pick Albany (that’s 145 miles)
  Chosen Cities = (Rochester, NYC, Syracuse, Albany)

Note: Albany back to Rochester is 226 miles.

3. There are no more cities and the route takes (333 + 247 + 145 + 226) = 951 miles

Greedy Algorithm:

1. Pick a random starting city from (NYC, Rochester, Albany, Syracuse).
  Let us start with Rochester again.
  Chosen Cities = (Rochester)

2. Pick closest unchosen city from (NYC, Albany, Syracuse)
  Syracuse is 87 miles away
  Chosen Cities = (Rochester, Syracuse)

2. Pick closest unchosen city from (NYC, Albany)
  Albany is 145 miles away
  Chosen Cities = (Rochester, Syracuse, Albany)

2. Pick closest unchosen city from (NYC)
  NYC is 156 miles away
  Chosen Cities = (Rochester, Syracuse, Albany, NYC)

Note: NYC back to Rochester is 333 miles.

3. There are no more cities and the route takes (87 + 145 + 156 + 333) = 721 miles