0
$\begingroup$

I recently took a test and I had a particularly difficult time with one problem. I would like to know more about this problem: what general class of problems does this problem belong to, what are some good resources to learn more about this class of problems, how should I have recognized the problem for what it was?

So here is the problem, distilled down to its essential components.

You have a task you are trying to accomplish. There are n different ways to to accomplish that task but each approach has a cost and probability of success associated with it. The problem is to figure out how to order your attempts at the task so that the average cost is minimized.

There is a small twist, if all but your last attempt has failed then you are guaranteed success on your last attempt regardless of the probability of success associated with it.

So here is a concrete example. The following list of tuples represents three ways to complete a task. The first value is the cost and the second value is the probability of success:

[(10,0.5),(8,0.25),(5,0.2)]

One possible order would be [0,1,2] (each value is the index of an attempt in the above list).

That has an average cost of:

0.5*10 + (1-0.5)*0.25*(10+8) + (1-0.5)(1-0.25)(10+8+5) = 8.975

But the optimal order is [0,2,1]:

0.5*10 + (1-0.5)*0.2*(10+5) + (1-0.5)(1-0.2)(10+8+5) = 8.8

The obvious way to solve this problem is to simply try every possible order but that has a runtime of O(n!). What you are supposed to know is that by dividing the cost by the probability and sorting the list using that value as the key you will get the optimal order.

I did figure that out eventually but it was not obvious to me at all, I went down a long and winding route and hit many dead ends before I arrived at that solution. So what was the trick here to quickly come to this conclusion?

$\endgroup$
  • 1
    $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Aug 8 '16 at 8:35
4
$\begingroup$

The algorithm that you have found is an example of a "greedy algorithm". When trying to find an algorithm for a problem there is a small bag of standard tricks that you can use but these are quite limited and for most problems, there's no easy solution: you have to "go down the long and winding route".

The trick here was to recognize that this problem has a property known as "optimal substructure": a solution to the problem consists of making some top-level choice, and then solving a smaller subproblem. The optimal substructure property states that any optimal solution consists of a top-level choice, and then an optimal solution to the subproblem (the way to solve the subproblem does not depend on previous choices).

If your problem has optimal substructure you can try solving it with dynamic programming (but that does not give a polynomial algorithm here because the problem does not have sufficient overlap between subproblems). Another option is using a greedy strategy, which happens to work here. The greedy strategy is (simply put): define some criterion by which to pick the locally "best" top-level choice and do not consider the possibility of making any choice.

In this case, the "right" criterion apparently is the expected cost of accomplishing that task by using that method. This intuitively makes sense (the option with highest success/cost ratio should be the one you try first) but to show that this choice indeed results in an optimal order, you have to show that the problem, coupled with this criterion, satisfies the "greedy choice property": any solution that does not use the "best" choice, can be modified to a solution that uses the "best" choice and whose objective value is at least as good or better as the objective of the solution that does not use the "best" choice. You can usually show this by some sort of exchange argument ("suppose the solution does not start with the best success/cost ratio, consider what happens if we swap the first step in the solution with the best success/cost ratio one, then the objective can only improve,...")

$\endgroup$
3
$\begingroup$

Assume no method is free: If some methods are free, you try all the free methods first obviously, and you are left with a problem without free methods.

Assume you have only n = 2 methods. Method 1 costs x and works with probability p. Method 2 costs y and works with probability q. The cost will be x+y if you have bad luck and your first attempt fails. If you use method 1, there's a probability p that you save y from the worst case cost. If you use method 2, there's a probability q that you save x from the worst case cost. You chose method 1 if the expected saving is greater, that is if p * y ≥ q * x or p / x ≥ q / y.

Assume you have more than n = 2 methods. Again, assume Method 1 costs x and works with probability p, and method 2 costs y and works with probability q. Assume you want to try these two methods first. No matter which one you try first, the probability of failure using both methods, the cost of trying both methods, and the cost of accomplishing the task after both methods failed, is the same - so we can ignore this. But now we only need to optimise the cost of using one or both methods, and the analysis is exactly the same as in the case n = 2 above. So if we decided to start with method 1 and 2 in unspecified order, we should start with method 1 if p / x ≥ q / y.

This doesn't apply to method 1 and 2 only: Whatever two methods we use first, we should try the one with the higher ratio (probability of success) / (cost of attempt) first. After trying one method, we have exactly the same problem except that n is now smaller by one and the method we just tried is not available anymore.

Therefore, if we decide to attempt methods 1 to n in any order, an optimal order will have the property that for any two methods that we use in turn, we should try the one with a bigger ratio (probability of success) / (cost of attempt) first. That means we find the optimal solution by sorting all methods according to that ratio, with the highest ratio first. So we found a very simple solution to this problem.

The problem is altogether different and much harder if the probabilities for success or the cost are not independent. The cost of method A might be lower if we tried method B first (because some of the work in method B can be used for method B) and vice versa. Or method A might be more likely or less likely to succeed if method B has already failed.

$\endgroup$

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.