Racketeer Taxi Driver

2

1

The Scenario

You are a taxi driver in your city. You picked up a passenger from the airport and he told you the place he'd like to go.

To earn more money, you need to drive as much as you can. However, there are two problems:

  • He always looks around. Therefore, you cannot pass from the same district twice.
  • The passenger is not so dumb. He knows the shortest way between the airport and the destination. Therefore, while you're driving, you should pass each of those districts.

The Input

Input is an undirected and edge weighted graph. The vertices are the districts and the edges are the ways that connect those districts. The weights of the edges indicate the distance between the districts. You can model the graph any way you want.

The Output

Given the source and destination, among with the shortest path, find the longest path that contains each vertex in the shortest path.

The Example

An example graph WHOOPS there are two different edge weights between B and C.
Source: A
Destination: K
Shortest Path: A-D-F-I-K
Solution: A-B-C-D-E-F-G-H-I-J-K

Rules

  1. Your solution should be generic and can be applicable to all kinds of connected graphs.
  2. No cycles are allowed. You can pass through a vertex only once
  3. Brute-force is not allowed. Don't list all the possibilities and pick among them.
  4. The edge weights are always positive.
  5. It is a must to visit all vertices in the shortest path, however, the order is not important.

Duration: 1 week.
Tie breaker: Votes.
The code with the least run-time complexity (in terms of Big-O notation) wins!

padawan

Posted 2014-07-01T00:35:13.840

Reputation: 294

Clarification: Do we have to go through the shortest-path nodes in the correct order? Also, are edge weights guaranteed positive? – isaacg – 2014-07-01T00:40:38.417

3I'm pretty sure finding the optimal solution is NP-complete for the same reason Longest Path is. Just reduce from Hamiltonian Path. So, any algorithm is going to be exponential. Moreover, since the reduction doesn't require any blowup, no algorithm can be faster than one for Hamiltonian path, for which the best deterministic algorithm I'm aware of is O(n^2 2^n) – xnor – 2014-07-01T02:11:23.110

1On several edges in your example you gave more than one weight, e.g. B-C has weights 5 and/or 3 without an additional vertex between. – Howard – 2014-07-01T04:39:38.657

@xnor is that a problem? – Martin Ender – 2014-07-01T07:13:57.633

What is the tie breaker if two solutions have the same complexity? – Martin Ender – 2014-07-01T07:14:31.380

@mbuettner clearly, votes – padawan – 2014-07-01T07:52:47.610

1@cagirici "clearly"? No, that is by no means implied by any of the tags you used. Neither is it a common default tie-breaker employed on PPCG. If you want to use votes as the tie breaker, you should specify that in the challenge. – Martin Ender – 2014-07-01T09:21:39.443

@cagirici If a brute force solution is optimal, that is, if O(n!) is the minimum runtime, is it allowed? Or do you know there is a better solution? – isaacg – 2014-07-01T09:29:50.803

@m.buettner NP completeness isn't necessarily a problem, but it pushes the competition into the exponential time and limits the possibility of an algorithm significantly better than brute force, which I find less interesting, but YMMV. It also increases the odds that the brute force O(n!) is the best you can do. – xnor – 2014-07-01T13:05:48.787

Answers

4

Reduction to Traveling Salesman Problem, O(n^2*2^n).

In the above, n is the number of vertices in the graph.

I will give a description of the algorithm for now. Starting with the input graph, carry out the following steps:

  1. Create a new graph with edge weights equal to the negation of the input edge weights. These weights represent the value to the taxi driver of traversing those edges.

  2. Let N be the sum of all of the negative weights in the (new) graph minus 1. Add N to each outgoing edge from a node on the shortest path (as given in the input). This represents the fact that the taxi driver absolutely must cross each vertex in the shortest path.

  3. Now, use dynamic programming to solve the traveling salesman problem on this new graph as follows:
  4. Next, create a memo table, m, with entries that are pairs, (v,S), where v is the final vertex in the (partial) path created so far, and S is a subset of the vertices in the graph. The weight associated with this entry will be the minimum sum of edge weights to reach v after having passed through the vertices in S. Also, maintain a parent pointer.
  5. Initialize the memo table with the entry m[(source,{source}]=0, p[(source,{source}]=None.
  6. Fill in the memo table, using the recursion that m[(v,S)] = min(m[(u,S-{v})]+w[(u,v)] for u in S), where w is the the edge weight dictionary. Create parent pointers accordingly.
  7. Using the completed memo table, find the minimum value of m[(destination,S)], for all subsets S of the input vertices.
  8. Trace the parent pointers from this minimum value backwards until we reach the source node. The resulting path is the solution.

I don't feel like coding that all up, but I believe it is a correct solution. It runs in O(n^2*2^n) time because there are n*2^n entries in the memo table, and each is generated by taking a minimum over no more than n possibilities. All the other work takes far less than that amount of time.

This solves the problem because the traveling salesman path must go through all of the vertices on the shortest path, because skipping one of those vertices results in an increase in the traveling salesman cost of N, which cannot be offset by the negative edge weights in the graph, since N was chosen to be more negative than all of them combined.

isaacg

Posted 2014-07-01T00:35:13.840

Reputation: 39 268

Asked: 2014-07-01T00:35:13.840

Viewed: 683 times

Active: 2015-02-16T00:28:56.767