Today we discuss the principle of optimality, an important property that is required for a problem to be considered eligible for dynamic programming solutions.
So if you take a glimpse of how Greedy and DP differs, the most noticeable feature is that Greedy is forward processing the question while DP appears to be backward propagation, though this stems from finding the optimal substructure.
We have a graduation project and we have a graph and want to find the optimal path. You saved us from reading lots of dull pages in 10 min. Thank you bro.
Was that the correct way to prove it? It sounded like "Prove A is the killer. Imagine B is the killer. but it is not possible because we already stated that A is the killer. So B cannot be the killer."
Not exactly... Induction is not a circular argument, though I do not think iwas well explained. The essence of induction is: -We Know it works for n=0 (or the number you want to start with) -Prove that, if it works for a given number N, then works for n+1 Now you know it works for 1, and for 2, and for 3... Example: prove any number multiplied by 0 is 0 We know 0*1 = 0 if 0*n = 0, then 0*(n+1)=0*n+0*1=0+0=0 It is true for n=1, so it works for n=2 Since it is true for n=2, then it is true forn n=3 Since it is true for n=3, then it is true forn n=4 You have proven n*0 = 0 for any natural number Note: I think there is a proof from the definition of number that says you can extend this to all numbers, and it is needed since, though it is ombvious, you can only entend this reasoning up to a certain number if you use a finite number of steps (in our case, up to n = 4), so yo need the iduction theorem
Nah. I had the same issue, but then I reflected on it a bit more. It all hinges on the fact that the optimal solution's cost is the sum of the costs of its parts. If the first half of the optimal path isn't optimal, then we could find a different sub -path which is optimal. But then the new sub-path plus the rest of the optimal path would give you a new solution, which would be better than the optimal path. In logical terms: "(Path is optimal) is true" "If not (sub-path is optimal) then not (path is optimal)" "Therefore, (sub-path is optimal) is true" With the middle sentence hinging on the fact that the optimal solution is sum of its sub-paths. Otherwise the implication cannot be made.
Great video! helping college student like me who's just confused why the lecturer explained this so looooong then you just explained it in less than 10 minutes mksieee pak, saya g ngangong waktu matkul RO. pdhl deadline besok t__T
hi may i know whats the complexity? (im not sure is it O(NE) where N is number of nodes and E is number of edges) if so that means dijkstra is still better?
All the comments here saying this proof is "nonsense" - it's not! It may look weird and confusing the first time you see this kind of proof, so pay attention and try to follow: Think of it as if we're given AS A FACT that the route named R from origin city 'a' to destination city 'j' is the shortest. We're not trying to prove that. It's a given fact! Now what we actually want to prove is that any sub-route inside R (for example from 'a' to some midpoint 'k' that is located between 'a' and 'j') would ALSO be the shortest route to that midpoint. And why is that?? Because if there would exist a different route from 'a' to 'k' that is shorter, then you could also use it to improve R and reach faster to the final destination 'j'. But that's a contradiction to the GIVEN FACT that we have in the first place (that R is already the shortest). Thus you prove that any sub-path within a given shortest path, is ALSO a shortest path....
I dont get it. whats the point of going from J to A, we traversed all the nodes, isnt it same as going from A to J? as long as we traverse all the nodes, we will have an optimal solution.
sorry, i have tried with the same approach even in forward and the paths found are the same (even ACEHJ is optimal), can you explain me why forward and backward are the same for this case? thank you
Wait... I thought at 2:38 that algorithm is Dijkstra's algorithm which is a greedy algorithm? Is it not? I am new to the field so I might be wrong, just wanna check...
@@navam23 It is because all nodes on any level are connected to ALL the nodes in the next/previous level, thus the algorythim will just take whatever the minimum one is the first, and roll with that.
I read many comments that the proof doesn't make sense. It does in fact. The statement to be proved was: R(a.j) is shortest path from a to j IF R(a.k) is shortest path from a to k . And the proof was not to be made about whether R(a.k) is itself the shortest path from a to k or not. This is another subject. He started where we already knew that R(a.k) is the optimal path from a to k.
What is preferred way of implementing dynamic programming? I know there's a way to do it recursively and a way to do it inside a for loop and I don't know which I should concentrate on in a dp problem.
You can implement both by recursion or iteration. This is not part of DP. Recursive solution will be more elegant, but usually computationally more heavy in terms of memory ... Gain from GP lies in throwing out non-optimal solutions at every transition from/to previous/next layer of nodes. You don't need to evaluate every possible path through the graf, you discard them at some layer as definitively non-optimal.
proof by contradiction is little hard to understand. We first make some assumption, then make more assumptions and then we know that our first assumption was correct.
Dynamic Programming has nothing with Fibonacci, Fibonacci is simple recursive definition, can be calculated recursively or iteratively, no chance/possibility to throw out non-optimal solutions and take advantage from DP.
MagicianCamille saw this video the first time then came to same conclusion. read the book multiple times and thought it was nonsense and pointless too. now returning to this video and it is making sense. i think it would help to brush up on proof by contradiction.
I love these series, you should definitely make more. There aren't that many good tutorials on the internet about CS
The explanation is quite clear. Thanks!
5:10: The proof is so awkwardly trivial that it is hard to wrap my head around, lol.
Great video! You made this much easier to understand than my textbook
instaBlaster
So if you take a glimpse of how Greedy and DP differs, the most noticeable feature is that Greedy is forward processing the question while DP appears to be backward propagation, though this stems from finding the optimal substructure.
Good video. Explicit and easy to understand!
Simplest explanation.
Thank you very much
Excellently done. Well worth the simple time investment involved.
great job done brother really loved all your videos . Please make another video for other greedy algorithms and optimal binary search tree!
Thank you very much for this Video.
amazing videos! thanks!
Excellent explanation!
Great video.Thanks a lot.
Great video, thx!
Such an amazing explanation !!! *CLAPS*
Very nice explanation!
really awesome tutorial.
We have a graduation project and we have a graph and want to find the optimal path. You saved us from reading lots of dull pages in 10 min. Thank you bro.
Omar Bin Salamah|| it involves that.
Was that the correct way to prove it? It sounded like "Prove A is the killer. Imagine B is the killer. but it is not possible because we already stated that A is the killer. So B cannot be the killer."
I know it's old but..
In proof by induction, we can assume that a proposition P(k) is true, as long as k
hahaha...
The proof was not that a chosen solution is optimal, but that an optimal solution cannot be made out of non-optimal subsolutions.
Not exactly... Induction is not a circular argument, though I do not think iwas well explained. The essence of induction is:
-We Know it works for n=0 (or the number you want to start with)
-Prove that, if it works for a given number N, then works for n+1
Now you know it works for 1, and for 2, and for 3...
Example: prove any number multiplied by 0 is 0
We know 0*1 = 0
if 0*n = 0, then 0*(n+1)=0*n+0*1=0+0=0
It is true for n=1, so it works for n=2
Since it is true for n=2, then it is true forn n=3
Since it is true for n=3, then it is true forn n=4
You have proven n*0 = 0 for any natural number
Note: I think there is a proof from the definition of number that says you can extend this to all numbers, and it is needed since, though it is ombvious, you can only entend this reasoning up to a certain number if you use a finite number of steps (in our case, up to n = 4), so yo need the iduction theorem
Nah. I had the same issue, but then I reflected on it a bit more.
It all hinges on the fact that the optimal solution's cost is the sum of the costs of its parts.
If the first half of the optimal path isn't optimal, then we could find a different sub -path which is optimal. But then the new sub-path plus the rest of the optimal path would give you a new solution, which would be better than the optimal path.
In logical terms:
"(Path is optimal) is true"
"If not (sub-path is optimal) then not (path is optimal)"
"Therefore, (sub-path is optimal) is true"
With the middle sentence hinging on the fact that the optimal solution is sum of its sub-paths. Otherwise the implication cannot be made.
Great video! helping college student like me who's just confused why the lecturer explained this so looooong then you just explained it in less than 10 minutes
mksieee pak, saya g ngangong waktu matkul RO. pdhl deadline besok t__T
hi may i know whats the complexity? (im not sure is it O(NE) where N is number of nodes and E is number of edges) if so that means dijkstra is still better?
Thanks!
thanks. u r great
Nicely explained
how about J to H, H to E, E to C and C to A? I think it is also 11.
Nati Econ You're right! I missed that!
Please do add a note to the video, very confusing when trying to analyze what is going on.
Please explain how these similar solutions are derived and please note there is one solution with 11 which was missed. See Arturo's comment!
Thanks you sir
All the comments here saying this proof is "nonsense" - it's not!
It may look weird and confusing the first time you see this kind of proof, so pay attention and try to follow:
Think of it as if we're given AS A FACT that the route named R from origin city 'a' to destination city 'j' is the shortest.
We're not trying to prove that. It's a given fact!
Now what we actually want to prove is that any sub-route inside R (for example from 'a' to some midpoint 'k' that is located between 'a' and 'j') would ALSO be the shortest route to that midpoint.
And why is that?? Because if there would exist a different route from 'a' to 'k' that is shorter, then you could also use it to improve R and reach faster to the final destination 'j'. But that's a contradiction to the GIVEN FACT that we have in the first place (that R is already the shortest).
Thus you prove that any sub-path within a given shortest path, is ALSO a shortest path....
Brilliant comment.
Helped me appreciate the proof better.
Awesome !!! Rightly explained !!! Thanks Helped me to better understand !!!
Dude doesn't look like Karim Hamasni
I dont get it. whats the point of going from J to A, we traversed all the nodes, isnt it same as going from A to J? as long as we traverse all the nodes, we will have an optimal solution.
thx
sorry, i have tried with the same approach even in forward and the paths found are the same (even ACEHJ is optimal), can you explain me why forward and backward are the same for this case? thank you
Principally, both forward & backward recursion result are the same but backward recursion is more reliable.
To me it looks like backwards Dijkstra
exactly it is
Yeah but what's weird is Dijkstra is taught under Greedy Algorithm.
So how is the example stated in video a part of Dynamic Programming?
Wait... I thought at 2:38 that algorithm is Dijkstra's algorithm which is a greedy algorithm? Is it not? I am new to the field so I might be wrong, just wanna check...
Great explanation Thanks
Ameenah Palmer... Are u computer engg..
Ci sono 3 soluzioni:
1) A-D-F-I-J = 3+1+3+4 = 11
2) A-D-E-H-J = 3+4+1+3 = 11
3) A-C-E-H-J = 4+3+1+3 = 11
Exactly! And it wasn't actually explained why / how these similar solutions are derived...
@@navam23 It is because all nodes on any level are connected to ALL the nodes in the next/previous level, thus the algorythim will just take whatever the minimum one is the first, and roll with that.
I read many comments that the proof doesn't make sense. It does in fact.
The statement to be proved was: R(a.j) is shortest path from a to j IF R(a.k) is shortest path from a to k .
And the proof was not to be made about whether R(a.k) is itself the shortest path from a to k or not. This is another subject. He started where we already knew that R(a.k) is the optimal path from a to k.
First I thought this is another solution to shortest path problem, other than djikstra's, but no
Does he have cold??
good
What is the point of proof? it is so useless? Or I dont understand its importance of it
What is preferred way of implementing dynamic programming? I know there's a way to do it recursively and a way to do it inside a for loop and I don't know which I should concentrate on in a dp problem.
Know both
You can implement both by recursion or iteration. This is not part of DP. Recursive solution will be more elegant, but usually computationally more heavy in terms of memory ...
Gain from GP lies in throwing out non-optimal solutions at every transition from/to previous/next layer of nodes. You don't need to evaluate every possible path through the graf, you discard them at some layer as definitively non-optimal.
proof by contradiction is little hard to understand. We first make some assumption, then make more assumptions and then we know that our first assumption was correct.
A to D then, D to F then, F to I then, I to J =11
Dynamic Programming has nothing with Fibonacci, Fibonacci is simple recursive definition, can be calculated recursively or iteratively, no chance/possibility to throw out non-optimal solutions and take advantage from DP.
Isn't Djikstra's Algorithm optimal than the DP approach in the first part of the video ?
Jagreet Das Gupta isnt the example basically Djikstra's?
That proof was nonsense.
MagicianCamille saw this video the first time then came to same conclusion. read the book multiple times and thought it was nonsense and pointless too. now returning to this video and it is making sense. i think it would help to brush up on proof by contradiction.
4:41: There is a shorter pathway. A-D2-F1-H-J cost only 10
is this proof stupid? or am i ?