Principle of Optimality Dynamic Programming

Kareem home as new here and today we're going to talk about the principle of optimality also known as optimal substructure this is a very important property that problems need to have in order to be eligible for a dynamic programming solution so let's dive it the textbook definition is a problem has optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems in other more layman terms we can solve larger problems given the solutions to smaller subproblems this was first coined by Richard bellman a computer scientist who literally wrote the book on dynamic programming in 1957 so let's take a look at a very simple example let's say we want to go from nodes 8 to C and we have an optimal path if that path has node B in the middle then we know that the path from A to B is optimal as well as the path from B to C let's take a look at an example that might not be so obvious at first here is a weighted graph that has distances between the nodes our goal in this problem is to get from node a to node J in the shortest distance possible and by doing so we want to get through the stages 1 2 & 3 sequentially so let's try naive greedy approach to this problem so starting at node a we're going to go the shortest path and in this case it's from A to B with a cost of 2 in the top right corner we'll keep track of our running running sum now a node B we're going to want to go to node F with the cost of 4 then from F we're going to pick between 6 and 3 to end we're going to pick 3 to get to node I and from I we're going to go to J with a cost of 4 giving us a total path cost of 13 is there a better way well let's take a look at some dynamic programming techniques that might show us a better path we're going to illustrate the optimal substructure and dynamic programming with this so let's dive in so let's define a function f of X and let that function be the minimum distance required to reach J from a node X so starting at the end at node J we know that F of J is equal to 0 because there's no cat no path cost to get to itself going back a level we can calculate f of H and F of I which we know are 3 & 4 simply based on the weighted edges in our left side we're going to keep a knowledge base with the actual costs of these functions so I'm going to fill in f of h equals 3 and F of 8 f of I equals 4 on the left now this is where things start to get interesting going back a level let's calculate F of e f of e is going to be the distance between two options either 1 plus f of H which is the path cost of 1 plus whatever cost we've calculated for f of H or it will be 4 plus F of I so it's C edge over here 4 plus the path cost of FY we know that the minimum in this case is 4 because 1 plus 3 is less than 4 plus 4 so we can now put that in our knowledge base and move on to calculating F of F here we'll calculate the minimum again and we'll determine that F of F is equal to 7 we throw that in our knowledge base and we move on to F of G which is equal to 6 going back a level more we now have three options as there are three paths paths coming out of each of these nodes so we calculate the min 7 plus F of e 4 plus f of F or 6 plus F of G we know that at F of B the shortest route to get to f of J is equal to 11 and throw that in our knowledge base and do the same for node C and nodes D from node C we can see the path cost of J is 7 and from D we can see that the path cost a J is 8 finally we're at node a using the distances that we've calculated for F of B F of C and F of D we can now calculate the total cost of the path from I to J in this case we found out that it's 11 this is definitely improvement over the 13 path that we discovered earlier through our naive greedy algorithm now let's take a look at the path that it takes we can go from A to D D to F F to I and I to J but this problem actually has another solution that has a path cost of 11a to D DD e e2 H and H 2 J so we've built an optimal solution in this case to optimal solutions using the subproblems to the problem this problem has optimal substructure but we want to define it using a proof so we'll do that by using a proof by contradiction we'll start our proof by saying let our a 2 J be the optimal path from nodes a 2 J are being symbol for the word root let's assume that this optimal path takes you through a city K our path can now be split into our a to K and our k 2j so let's look at a diagram for this from a to K and K 2 J I've put a squiggly line in between because it could go through other cities and it's not necessarily a direct path so our first step is just assume that there's a shorter path from A to K let's call it R prime a 2 K and I've drawn it into the diagram above if R prime a 2 K is less than R a to K and notice that I used less than here and not less than or equal to because we could have more than one solution then we know that R Prime a decay plus R K 2 J as a total is going to be a shorter path than R a 2 k plus RK 2 J but this can't be true we already know that our a 2 k plus RK 2 J is the optimal solution as stated before therefore R prime a 2 K a shorter path from indicate doesn't exist and our a 2 k plus RK 2 J is indeed the optimal solution this is proven by contradiction no it's a good idea to do your proofs before you attempt a dynamic programming solution that way you're not wasting your efforts in a futile attempt to apply dynamic programming to a solution that does not have optimal substructure now we can also prove optimal substructure using proof by induction so let's take a look at the example from the previous video for the Fibonacci sequence for those that haven't seen the previous video the Fibonacci sequence is a series of numbers where the next number in the series is equal to the previous two numbers so 0 plus 1 is equal to 1 1 plus 1 is equal to 2 1 plus 2 is equal to 3 and so on so let's start our proof by induction in a proof by induction we need to define our base case as step one step two we state the induction hypothesis and step three we perform the inductive step and that's where the real work comes in so in step one we'll just define our base cases as f of 0 is equal to 0 and F of 1 is equal to 1 in step two we'll start state our induction hypothesis so we'll assume that f of K is correct for all values of K less than or equal to n now let's do our inductive step from our inductive hypothesis we know that FK f FK is correct for the K Fibonacci number from our induction hypothesis we also know that F of K minus 1 is correct for the K minus 1 Fibonacci number because K minus 1 is less than n and we've stated in our induction hypothesis that it is true for all K less than or equal to n so what we want to solve for is f of k plus 1 so we'll continue our induction step and by definition we know of the Fibonacci sequence we know that f of k plus 1 is equal to f of k plus f of k minus 1 so f of k plus 1 returns the k plus 1 Fibonacci number because we use lower values of K to solve higher values of K we show that optimal substructure does exist therefore this is proven to have optimal substructure dynamic programming techniques are now okay to use with the Fibonacci sequence so once again just to recap we should use proofs to determine optimal substructure when using dynamic programming because problems that don't have optimal substructure cannot be solved effectively with dynamic programming thank you for watching go to see us break down calm for more subscribe to our videos and like this bye