naved's blog

Can you help me Solve this problem ?
By naved, 10 years ago, In English

I have a problem for which I am not getting optimal answer from last 3 days Problem is as Below Given a graph G find the shortest distance between Source to Destination node but you MUST PASS THROUGH ALL THE NODES before going to destination BECAUSE THEY ALL are MUST_PASS nodes.

Additional info: - -you can pass any node more than once if required to get optimal answer - -max number of nodes is 22 including source & destination

What I tried so far - brute-force : simple permutation will give you the answer for small n , but since upper bound is 20, it is not practical 20! duhh :(

  • TSP with DP: problem with this is I Start from Source visit all nodes except destination & comes back to start, now if I go back to last node which I visited and from their if I go to destination one might think that this will give me optimal result, but the result is sub-optimal and not optimal ...:(

  • suppose each must_pass node is named as C, Start as S, destination as D, then one might thing f(S,D) = min(S,C1) + min(C1,C2) + min(C2,Ck) + min(Ck,D) but this is also sub-optimal and optimal for small graph with fewer MUST_VISIT nodes

Max Must_Visit nodes are 20

  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
10 years ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

find the MST

now the distance you describe is equal to = the shortest path from the soure to the destination(can be found from the tree) + twice the sum of all edges which are not on the path(because once you go out of the shortest path, you have to go back to it so you pass each of these edges twice)

I haven't proved it yet but I think this is the answer

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    any graph can have two or more MSTs (for example, the K3 graph (triangle) has three different MSTs).
    this may lead to ur approach giving WA.

    → Reply
»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Your second approach seems to be on the right track, the problem is your tour doesn't need to revisit the start node so using TSP is not optimal.

Can you adapt TSP's DP so that you end in the destination instead of the start?

→ Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

If I understood correctly, you're asking to visit every node from the starting node and then go to the destination point. If max number of nodes is 22, why don't you just use Floyd-Warshall for all pairs shortest paths, do bitmask DP to calculate the optimal way to visit all must_pass nodes and then add the distance from the final node to the destination node (if necessary)?

The complexity of that solution is O(N2 * 2N), which can be more than 2000M operations for N = 22, but I can't think of anything faster right now...

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Is this question belong to some ongoing contest or school assignment? I have seen a lot of similar question these days on StackOverflow!

Link (See the comment part in the link also)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think so my friend who attended a interview couple of weeks ago said me they asked him this problem and solution was to be given in 2 hr (onsite) , he didn't able to do it. so he asked me.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No wonder, the thing is this question keep popping up, which normally the case when there is an on-going contest or smth, luckily this is not one of these :)

      → Reply