Athabasca University | AU Student/Staff Login | Invited Guest Login
Unit 3 Exercise 15.3-6 Discussion Question
Proof that finding the best sequence of exchanges for currencies exhibits optimal substructure when commission Ck = 0 for all k trades.
Let U1, U2, ..., Un be a collection of currencies. We can represent all possible sequences from U1 to Un as a directed graph where each node is a currency and is connected to each other node in the graph. Each directed edge represents a currency conversion value.
This problem is somewhat similar to the Unweighted Shortest Path problem only in this case, rather than hitting the fewest nodes from the start to end points, we wish to maximize the resulting value when exchanging from U1 along the sequence (path) to Un
For simplicity, assume nodes are only visited once and that U1 ≠ Un
Any path P from U1 -->P Un can be broken into sub-paths U1 -->P1 w -->P2 Un (where node w can equal U1, Un, or some other currency in the collection). The number of edges in P equals the sum of edges in P1 and P2.
We claim that if P is the optimal path from U1 to Un (that is, the sequence will offer the highest return of currency exchange) then P1 must be the optimal path from U1 to w and P2 must be the optimal path from w to Un
By the cut and paste argument, if there was a more optimal path P1’ from U1 to w, then we could cut out P1 and past in P1’ to give U1 -->P1’ w -->P2 Un as a more optimal path than P. However, this contradicts P’s optimality. Likewise, if there was a more optimal path P2’ from w to Un , then we could cut out P2 and past in P2’ to give U1 -->P1 w -->P2’ Un as a more optimal path than P. However, this contradicts P’s optimality.
This proves that finding the best sequence of exchanges for currencies exhibits optimal substructure when commission Ck = 0 for all k trades.
When Ck are arbitrary values for all k trades, finding the best sequence of exchanges no longer has optimal substructure. This is because the sub-problem of finding the best return along the path is not independent from the problem of minimizing commissions based on the number of trades. What was once an optimal path when Ck = 0 could no longer be optimal when Ck is some other value.
COMP372 Design and Analysis of Algorithms
Comments
I'd say that the main reason why there is no guarantee that the sub-problems may give optimal solutions, because the commission rates are arbitrary values so as long as that is the case then the problem won't exhibit optimal substructure property.
Great proof of the optimal substructure. It is fun to also think of counterexamples for when the commission rates are nonzero!