1

I'm having trouble understanding a past quiz question I got:

Bobby works at Starbucks in San Mateo (V). He is doing quality assurance testing and needs to visit stores in Palo Alto (B), Tenderloin (C), and San Jose (S) - and then return to San Mateo for a meeting.

The distances between the stores are:

V→B = 2
V→C = 3
V→S = 6
B→C = 1
B→S = 5
C→S = 4

Which is the first store he visits in the optimal solution to this problem?

How would you approach solving this problem? It reminds me a bit of Djistra's algorithm but I suspect there's an easier way other than trying every combination as the time limit is short.

My interpretation: 

  B__1__C
  |     |
2 |     | 4
  |__6__|
  V     S

For Bobby to visit all 4 stores and return to V, he simply starts at V and travels the edges of the above box. But the question is asking which is the first store? Either direction will give a total of 13, so how is there a right answer?

|improve this question
  • (1) This is a variation of the Travelling Salesman Problem. (2) If you want to get an optimal solution, you simply have to try all alternatives (there's only very little wiggle room for clever cheating). You can however settle for a good-but-not-necessarily-optimal solution, which can be a lot faster. (3) Not every optimization problem has only one solution. You could output all solutions, but in practice any one of the optimal solutions would do. – amon Feb 4 '14 at 23:37
1

The right answer is that path which has the least cost. While this is technically traveling salesman and an exact solution is very difficult to achieve quickly, you can typically achieve an optimal or near optimal route by using a greedy, novelty hungry algorithm.

The algorithm is thus:

For current node pick the path with the least cost provided it leads to a node you've not visited prior. Travel to the new node and repeat until all nodes but the origin have been visited. Then visit origin by min cost path.

We start with an empty graph:

Initial Graph

Next we mark the current node as "visited" (bold) and follow the least cost path to an unvisited node:

Step 1 Graph

We continue this pattern for the next two nodes:

Step 2 Graph

Step 3 Graph

Now we have no new nodes to visit but we have the origin node connected so we take that path:

Final Step Graph

Thus we arrive at our solution. This algorithm is most optimal for fully connected graphs with distinctly weighted edges. We of course have used a form of Dijkstra's algorithm which confirms what you suspected. The best possible cost is 13.

|improve this answer
  • Very helpful diagrams, thanks! I still have some confusion due to the different ways you and I drew the diagrams (but both seem correct given the pathways). In my diagram, going clockwise gives you 13, while going counter-clockwise also gives 13. Since the question asks for the first store visited in the optimal path, my diagram seems to indicate that both B and S are valid answers given they both have a path of 13. The answer was supposedly B. Is there something I'm missing? – theintellects Feb 5 '14 at 0:09
  • B has the lowest initial cost of the three options available to V. You generally want the lowest initial cost. – World Engineer Feb 5 '14 at 0:13
  • Oh okay. I thought that might have been the case but I'm not familiar specific requirements for these types of algorithms. Thanks! – theintellects Feb 5 '14 at 0:18
  • @theintellects Since you don't always know what the whole graph looks like, greedy needs to pick lowest first in order to work optimally. The only time where this is not the case is the case of two edges on one node with equal weights. – World Engineer Feb 5 '14 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.