4.3 Matrix Chain Multiplication - Dynamic Programming

the problem is somatic chain multiplication in this video I'll explain you what is matrix multiplication problem then what does it mean by Mattox much change multiplication then I will show how to solve this by applying dynamic programming then we will come up with the formula that is used for solving this problem and also I will discuss the time complexity so let us start with matrix multiplication first of all if you have matrix 2 matrices and you want to multiply them and their dimensions are suppose Phi cross 4 and 4 cross 3 the condition for multiplying two matrices the number of columns of the first matrix should be equal to number of rows of second Matrix then only multiplication can be done if I write other way B cross a then their dimensions 4 cross 3 and Phi cross 4 will be there they cannot be multiplied because these are not same so a cross B is fit is possible then B cross a is also possible it's not necessary when you multiply the resultant matrix will be C and the dimension of that resultant matrix will be Phi cross 3 number of rows of first one and number of columns of last one by cross 3 so it means how many elements will be there so 15 elements will be there then for getting each element what we are supposed to do multiply first row with first column so how many elements first row will have four elements and this will also have four elements that is 4 you can see so total four multiplications I have to do for getting this one single element then again first row with second column I get this element so it means for getting each element of the same matrix I have to make four multiplications so this is into four so finally it is like this 5 into 3 into 4 this is 16 so it means for generating the C matrix I have to make 60 multiplications 5 4 3 60 multiplications quite right so this about the cost of multiplying two matrices depends on the number of multiplications that you are performing so how to obtain the number of multiplication this or we can find out the number of multiplications now coming to the problem here for medicines are given and the dimensions are given they are arranged such that they can be multiplied because these are same you see and the 6x is same 2 2 is same so they can be multiplied but the question is not to multiply and get the answer no we don't want the answer for multiplying I cannot multiply all of them together I have to take a pair at a time and multiply so the question is which parachutes select such that the total cost of multiplying all of them is minimum so the problem is not to multiply them the problem is to know how to multiply them this is matrix multiplication problem it means how I should parenthesize them shall I do it like this a 1 is multiplied with a 2 and that result is multiplied with a 3 and that result is multiplied with a 4 shall we do it like this or a 1 and a 2 are multiplied and separately a 3 and a 4 are multiplied then their results are multiplied together which method I should follow see like this how many possibilities are there there are many ways I can parenthesize them so let me know total how many ways are there so if I show this in the form of a tree a 1 is multiplied with a 2 then a 3 is multiplied with a 4 then their results are multiplied so it is forming like a tree right if you see this is forming like tree with how many nodes three nodes because there are three multiplications out of four mattresses so three knows we are getting so for this one if I represent then this is a 1 is multiplied with a 2 and that result is multiplied with a 3 and that result is multiplied with a 4 see this is representing that pattern that tree is representing this parenthesis ation so like this three nodes how many different trees are possible so it means how many different parenthesize Asians are possible see four unknowns - n c n by n plus one binary trees are possible now for three nodes how many it will be if I substitute three here then I get answer five so it means these matrices can be multiplied in five different ways five different ways they can be parenthesized which one I want I want minimum so shall I try all five and calculate their total cost and pick up the best one no I don't have to do it like this no doubt I have to try all possible five but I will follow easy method that is given by dynamic programming so dynamic programming says that you try out all possibilities and pick up the best one so how to try all possibilities it is difficult for every problem even they may be missing some possibility also so without missing anything how to get the perfect answer by trying all possibilities now we will see how to solve this problem let us solve this problem using dynamic programming as a dynamic programming uses tabulation method so these are the tables I have I will call this with named M and this with named s any name you can give M as the name I have taken now we will fill up this table and in tabulation method will follow bottom of approach we should take the smaller values and fill the table first so actually we are talking about multiplication so let us take just a 1 not multiplied with anything just a 1 so what is the cost of multiplication it's not multiplied with anything so the cost of zero so when I say a 1 so let me call it as M of 1 comma 1 so M of 1 comma 1 is 0 then if I take a 2 just a 2 then this will be M of 2 comma 2 and there is nothing multiplied so this is also 0 same way M of 3 comma 3 0 4 comma for you see so this is small problem let us find out M of 1 comma 2 M of 1 comma 2 means I am multiplying two matrices that is 1 2 2 so a 1 with a 2 then what are the dimensions of a 1 5 4 and dimensions of a 2 4 6 so what will the total cost of multiplication 5 into 4 into 6 this is 120 so I am off 1 comma 2 that is multiplying this pair of matrixes 120 so here I write 1 2 in the first value and for this one with the two I multiplied so I will take it as 1 so at same 1 comma 2 I will write it as 1 why I am writing that I will explain after some time now next I will try a 1 2 2 is over now 2 2 3 I will select this page first I selected this mix am selecting this after that I'll be selecting this so 2 2 3 I will select so M of 2 to 3 that is a 2 with a 3 what are the dimensions 4 comma 6 and 6 comma 2 4 into 6 and 6 into 2 so this will be 48 right so 2 comma 3 M of 2 comma 3 is 48 so I am filling this diagonally next I will be selecting a 3 4 so here I will write on M of 3 comma 4 will be multiplying these two matrices so their dimensions are 6 2 + 2 7 right so 6 into 2 into 7 is 84 so 3 comma 4 3 comma 4 is filled with 84 so now I have the cost of multiplying pair of Madison and there are different way possible I have taken all possible pairs now to two medicines were selected now we will select three matrix so that is I will find out a of 1 comma 3 and 1 comma 3 means a 1 a 2 and a 3 so when we consider all three then there are two possibilities one s this is multiplied the result of this or first a1 and a2 are multiplied and their result is multiplied by a 3 there are two possibilities now what is the cost of what are the name what are the dimensions of this phi cross 4 and this is for draw 6 6 2 & 5 4 4 6 6 2 now what is the cost of a of one this is nothing but m 1 comma 1 plus what is the cost of this M 2 2 3 2 2 3 then what is the cost of this multiplication see this is already done we know the cost right 2 comma 3 I have written I want to know only this multiplication just 1 multiplication so this depends on the dimension so what are the dimensions 5 & 4 2 so 5 4 2 so the result of this will be 4 cross 2 so 5 into 4 into 2 so this will be 5 into 4 into 2 then what about the site this is M of 1 comma 2 plus M off this is just 3 so write the 3 comma 3 then plus what are the dimension see the final dimensions of this one will be these 2 so 5 into 6 into 2 5 into 6 into 2 now M of 1 comma 1 is how much 0 plus M of 2 3 2 3 is 48 plus how much this is 40 then M of 1 comma 2 1 comma 2 is 120 Plus mm of 3 3 3 comma 3 is 0 plus how much this is 60 right which one is minimum this is 88 and this is 180 this is meaning so M of 1 comma 3 is 88 M of 1 comma 3 is 88 now here there were two possibilities we have tried this one versus this one and took meaning amount of these two right we have taken minimum of these two so who has given minimum this one was this side and 2 3 4 2 3 was that side so one has given us the result so for this value I should write 1 here as I find out M of 2 comma 4 means I should select these three so M of 2 comma 4 in this there are 2 possibilities a 2 multiplied with the result of this 1 or a 2 multiplied with a 3 and the result of it a for C in this way I am trying all possibilities but an easy method because the result I can get it from the table from the table I am getting the values and I am filling the table let us take this four six six two two seven four six six two two seven four six six two two seven now what is this one this is M of 2 2 plus this side is M of three four plus what will be the product of this one see we will get this as a dimension right and these two are same so they are multiplied 4 into 6 into 7 4 into 6 into 7 then what about this side this is M of 2 to 3 plus M off 4 to 4 plus the result of this one will be this one and as these two are same then final will be 4a 2 to Windows 7 so 4 into 2 into 7 let us see how much mrs. M of 2 comma 2 2 comma 2 is 0 plus M of 3 for M of 3 comma 4 is 84 then this is 168 then M of 2 3 2 3 is how much 48 48 plus M 4 4 is 0 plus 56 so which one is smaller this is 252 and this is one not four so which one is minimum one not for is minimum so the answer for this one is 1 not 4 that is 2 comma 4 2 comma 4 is over not for and who give this value see this side is 2 3 and that side is 4 so answer is 3 so 3 has given us minimum resinate how to find out this final value that is all 4 so we tried to then 3 at a time no 400 now M of 1 comma 4 so now I will use the formula and show you write use the formula M of 1 comma 4 is minimum of M of 1 comma 1 plus M of 2 comma 4 C 1 comma 1 this side then 2 to 4 remaining Plus what will be the cost of multiplying them from here I will see this is 1 and these are together 2 to 4 so this is 5 into 4 into 7 so 5 into 4 into 7 comma I have to take the minimum this is one possibility 1 a 1 is this side and all 3 that side so I wrote here 1 then again M off 1 comma C that time I wrote one here now I will write 2 here so then plus M off this will three four so this means one two to the side and three to four that side so two separate plus what will be the cost of this one five four and seven sorry five or six and seven so 5 into 6 into seventh then there are two more possibilities here write em off 1c first time 1 so decide to then next is to know it is a 3 1 comma 3 plus M of 4 comma 4 so 1 2 3 this side and 4 that side so this is 5 into 2 into 7 so 5 into 2 into 7 that's it so what are the possibilities I have only 1 decide 3 that side or to this side to that side or 3 this side and one that side so all possibilities I have taken here I have to find out what is the cost of this one see this is 0 and 2 comma 4 is how much 1 not for one not for under this is 40 and this is M of 1 comma 2 is how much 120 plus 3 comma 4 is 84 plus 2 10 and 1 comma 3 is how much fun comma 3 is 88 this is 88 plus 4 comma 4 is 0 and this one is 7 and D naught of this which seems to be smaller this is 200 and this is a 3 400 above and this is 158 yes this has given us a smaller result so the result is 158 then on what value I got the sons are 3 so this is 3 that's it I have filled the table right so finally I have used the formula slowly I have build a formula right so finally I have build a table not two tables already now we need to know the answer before knowing the answer I will write down the formula say here if I say em off I comma J minimum of what is this I'm off I to some K so you can see that this was 1 so 2 then 2 then 3 then 3 and 4 so I'm off I comma k plus M off k plus 1 comma J this is the form - this is 1 comma 1 so 2 2 4 1 2 2 3 2 4 so 1 2 3 4 - 4 i2 k k plus 1 to j then plus this was getting multiplied these are getting multiplied so how I should represent them now from the example I will show you so if I say this is a tension 1 then this is a dimension 2 then this is a dimension 3 then this is a dimension 4 then this I have to call it as a dimension 0 like there are four mattresses for total 5 dimensions so I should start from zero so see otherwise if I start from 1 I will end up at 5 but the last matrix is 4 so let us start from zero dimension 0 1 2 3 4 so when I am multiplying any matrix see when I am multiplying the matters that is I t 2k + 1 2 change so I should take I so if I is this matrix then I should take this 1 I minus 1 so this is d of I minus 1 into D of K into D of J this is the formula now let me follow this table the one which was giving minimum I was writing them here so the first topmost one what it says 3 so it means this side then this is separate so this is one parenthesis at the 3 this is splitted K is a 3 so 1 2 3 is this side and for that side right no what about one two three so if I check 1 2 3 it is 1 1 2 3 is giving 1 so 1 this side so a 1 this side then what that side is remaining a 2 and a 3 then all the way this outer bracket was there then a 4 that's it 2 2 3 so 2 2 3 gives us 4 2 only so there are only 2 so let them be as it is so how it looks like C a2 and a3 are multiplied first and we get this result then a1 is multiplied with a result all right then a4 s multiplied with their result that's how the multiplication will be done this is a train we got of this shape we got right so this is a solution now let us check what is the time complexity so actually we are preparing a table but we are not preparing entire table we are preparing half of the table so also you can say n into n plus 1 by 2 number of elements we are generating right see this is 1 then 2 then 3 so on so n in n plus 1 or n minus 1 also you can say because this diagonal is all 0 so really you want to consider or not so anyway this is going to be N squared approximately n square right if you want to write notation it's n square but each element how we are getting we are calculating all and finding the minimum so how much time it takes at most n so this is into n so the time complexity of this one is n cube so this is Theta of n cube so the time complexity for Mattox chain multiplication is n cube multiplying the mattis's also in queue and solving the parent isolation problem of mitosis is also n cube then lastly I will show one more thing the stable I draw it like this right because we are not using this portion so first row I will write like this this is first row right then this is second row then this is third row and this is fourth row so these are rows 1 2 3 so this is 1 2 3 4 so if I say I is for row and J is for column so these are I so I'll write I hear right that side from that satisfy C then these are columns so these are columns so this is 1 2 3 4 so this are J then what is the value here 158 and this is 88 and 1 not 4 and 1 2048 and 84 0 0 0 0 this is how a table is prepared instead of drawing it like this and half unfilled or empty we can also draw it like this so just done is that site you get this table

Channel: Abdul Bari

Views: 785,883

Keywords: matrix chain multiplication, matrix chain dp, matrix chain dynamic programming, dynamic programming, algorithms, algorithm, abdul bari, bari, gate

Id: prx1psByp7U

Length: 22min 59sec (1379 seconds)

Published: Fri Feb 16 2018