4 ms·

Can you elaborate on this binary search? How do you get a proposed path to feed to your decision problem?

ColinWright 13y ago
Roughly - and possibly with some errors ... It's not a path that we're feeding to the decision problem. The decision problem is when we have a graph with costs on the edges, and when someone says "Is there a solution of cost less than K?" We're assuming we have a way to answer that, and using that to get a solution to the optimization problem. We need to use that to find the best possible path. We start by finding the cost of the best possible path. Set k=1 and ask if there's a solution. If not, double K and ask again. Repeat until the answer is "Yes". Now you know there is a solution with cost in the range [0,K]. Set L=0 and U=K. Now do a binary search. Set K = L + (U-L)/2 and ask if there is a solution of cost K. If not, set L=K, if so then set U=K. Lather, rinse, repeat, until U-L is sufficiently small (1 if using integer weights - more care required otherwise). Now we know the optimum price. Remove an edge and see if there's still a solution. If there is, there's an optimal path without it. If not, the edge is in the optimal path. Repeat for all edges - some efficiencies can be made.
- ufo 13y ago
  Removing one edge at a time won't work if there is a second, redundant, optimal path (every edge can be removed without altering the cost). I don't remember how you get around this but it shouldnt be too complicated...
  - ColinWright 13y ago
    Sorry, thought that was clear. If you remove an edge and find the cost doesn't change, don't put the edge back - carry on with the smaller graph.
habitue 13y ago
This doesn't get you the path itself, it only gets you the length of the path. Think of it like this: the decision version question is: Is there a path of length k that hits all of the cities? The algorithm just has to answer yes/no, it doesn't have to give you the path itself. So you can use binary search to repeatedly ask whether there is a path with length less than k, and home in on the optimal length. You still don't know what the path is. We assume it would be difficult for the algorithm to make this determination without having actually discovered the path, but the problem doesn't require that it output any such path. Edit: This is wrong, ColinWright details how to get the actual path from just knowing the length

Roughly - and possibly with some errors ... It's not a path that we're feeding to the decision problem. The decision problem is when we have a graph with costs on the edges, and when someone says "Is there a solution of cost less than K?" We're assuming we have a way to answer that, and using that to get a solution to the optimization problem. We need to use that to find the best possible path. We start by finding the cost of the best possible path. Set k=1 and ask if there's a solution. If not, double K and ask again. Repeat until the answer is "Yes". Now you know there is a solution with cost in the range [0,K]. Set L=0 and U=K. Now do a binary search. Set K = L + (U-L)/2 and ask if there is a solution of cost K. If not, set L=K, if so then set U=K. Lather, rinse, repeat, until U-L is sufficiently small (1 if using integer weights - more care required otherwise). Now we know the optimum price. Remove an edge and see if there's still a solution. If there is, there's an optimal path without it. If not, the edge is in the optimal path. Repeat for all edges - some efficiencies can be made.

ufo 13y ago
Removing one edge at a time won't work if there is a second, redundant, optimal path (every edge can be removed without altering the cost). I don't remember how you get around this but it shouldnt be too complicated...
- ColinWright 13y ago
  Sorry, thought that was clear. If you remove an edge and find the cost doesn't change, don't put the edge back - carry on with the smaller graph.

habitue 13y ago

This doesn't get you the path itself, it only gets you the length of the path. Think of it like this: the decision version question is: Is there a path of length k that hits all of the cities? The algorithm just has to answer yes/no, it doesn't have to give you the path itself. So you can use binary search to repeatedly ask whether there is a path with length less than k, and home in on the optimal length. You still don't know what the path is. We assume it would be difficult for the algorithm to make this determination without having actually discovered the path, but the problem doesn't require that it output any such path. Edit: This is wrong, ColinWright details how to get the actual path from just knowing the length