Good videos, these have assisted me with understanding these algorithms. However, an example of Iterative Deepening with DFS with depth bound of k + 3 would have been good to see. Although Iterative Deepening is quick with DFS I think it repeats its work. For example, it repeats work of k when traversing to k+1 and it repeats work of k and k+1 when traversing to k+2 etc etc...
A depth limit of value 3 or 4 would have been more insightful. And you forgot to mention on how the nodes are generated repeatedly. Like for depth limit 2, the root will be generated 3 times, and nodes at level 1 will be generated two times and likewise.
Sorry but at 03:03 are you saying that we can't search B because our depth limit is a maximum of 2 but if it was a maximum of 3 - you would then search B. However you have already placed a dead end on it even before you find the goal state. This bit is slightly confusing but nice clear explanation
Yes. Every Iteration you start from the start. Now you may think: "oh but then thats way too costy than just doing deep first". But it's not. Because every time n increments, the number of nodes (generally in normal graphs) exponentially increments too. What I'm saying is: in most graphs, level n has more nodes than levels (n-1)+(n-2)+...+1
3:20 you found the goal, but now the way you check all nodes seems the same like BFS for me. If you wouldve applied BFS you wouldve found the same solution, and did not even check all things twice or three times. My question is, how is this different from BFS and how can this be better than BFS
@@H0llowed8D Yes that is for the last iteration, but before that iteration those nodes were checked right? Or am I missing something? At 2:00 he checks all the nodes at Level 1 as well, so the B and D at level 1 are checked. For me this still looks like BFS since you only make it 1 deeper per iteration
The main difference lies in the memory space being used to store the frontier. BFS stores all the nodes at the depth that the algorithm is currently in, so if a level has 99 nodes, at some point BFS would need that memory space to store all of them. On the other hand DFS only stores the frontier nodes that are on it's current path, therefore at the same depth, DFS would use strictly less memory space than BFS during the search. (therefore if you have infinite memory space, then yes BFS is faster than iterative deepening search) The problem with DFS is that it is possible for the algorithm to go down a wrong path that is extremely long, therefore wasting even more time than using iterative deepening search.
I should have rubbed out the tree after d = 1, but this is not breadth first search. It is depth-limited depth first search, starting with a depth limit of 0, and increasing this depth limit incrementally until a solution is found.
This is totally different from BFS. You can see at level 2, the BFS could have expanded other two nodes also. But here with ID, it does just expanded the left most node and done with it at level 2.
![รุ่นใหญ่ EP.2 บุกบ้าน เสรีพิศุทธ์ ระหว่าง บิ๊กต่อ กับ บิ๊กโจ๊ก อา รักใครมากกว่า ?? l [Nickynachat]](http://i.ytimg.com/vi/j2inUqhN__0/mqdefault.jpg)
It's a rare gem to hear CS lectures in a understandable accent.
honestly
Probably the best cs teacher i have seen deserves a subscribe
It would be very good, if the videos were numbered. Especially if on video is referred to in another.
Thank you for excellent material.
ThankYou Sir. Easy to understand explanation.
Nice video, you can also explain CSP (Constraint Satisfaction Problems)
Very good explanation, thank you.
Thanks, good explanation
Thanks for helping again!!!
Thank you sir (I wanted to mention that you are very similar to the actor in lost called Benjamin) Love you sir
Please sir put videos on bidirectional searches. Also point out the real world scenarios where each type of search is suitable.
Thank you very nice video.
Great explanation, but the camera's auto-focus seems to be on and the image keeps zooming in and out.
*Modified DFS with a bound. You only continue going down the tree to nodes that take d or less steps to get to.
Thanks for the video!
Good videos, these have assisted me with understanding these algorithms. However, an example of Iterative Deepening with DFS with depth bound of k + 3 would have been good to see. Although Iterative Deepening is quick with DFS I think it repeats its work. For example, it repeats work of k when traversing to k+1 and it repeats work of k and k+1 when traversing to k+2 etc etc...
but it has already explored nodes so whether it repeats it doesnt take more time or space
we love you
When will more videos be uploaded, please thanks.
thank you sir
my goat
Hi, is this the same as iterative deepening A* search?
A depth limit of value 3 or 4 would have been more insightful. And you forgot to mention on how the nodes are generated repeatedly. Like for depth limit 2, the root will be generated 3 times, and nodes at level 1 will be generated two times and likewise.
Thanks for the feedback! I'm going to redo this one with your suggestions :-)
Sorry but at 03:03 are you saying that we can't search B because our depth limit is a maximum of 2 but if it was a maximum of 3 - you would then search B. However you have already placed a dead end on it even before you find the goal state. This bit is slightly confusing but nice clear explanation
Since this is a variation of DFS, we see we cannot go beyond our depth limit so B's neighbors cannot be expanded yet.
When you increase the depth limit, do you start from the start state again and do all those expansions again?
Yes. Every Iteration you start from the start.
Now you may think: "oh but then thats way too costy than just doing deep first". But it's not. Because every time n increments, the number of nodes (generally in normal graphs) exponentially increments too. What I'm saying is: in most graphs, level n has more nodes than levels (n-1)+(n-2)+...+1
What are the explored states? It is SA?
yes
3:20 you found the goal, but now the way you check all nodes seems the same like BFS for me. If you wouldve applied BFS you wouldve found the same solution, and did not even check all things twice or three times. My question is, how is this different from BFS and how can this be better than BFS
@@H0llowed8D Yes that is for the last iteration, but before that iteration those nodes were checked right? Or am I missing something? At 2:00 he checks all the nodes at Level 1 as well, so the B and D at level 1 are checked. For me this still looks like BFS since you only make it 1 deeper per iteration
The main difference lies in the memory space being used to store the frontier.
BFS stores all the nodes at the depth that the algorithm is currently in, so if a level has 99 nodes, at some point BFS would need that memory space to store all of them.
On the other hand DFS only stores the frontier nodes that are on it's current path, therefore at the same depth, DFS would use strictly less memory space than BFS during the search.
(therefore if you have infinite memory space, then yes BFS is faster than iterative deepening search)
The problem with DFS is that it is possible for the algorithm to go down a wrong path that is extremely long, therefore wasting even more time than using iterative deepening search.
@@zucchinirosti Thank you for the explanation!
Can you post a video on IDA* please?
focus messed up
Poor explanation, forgot to mention on how the nodes are generated repeatedly.
The explanation is wrong! His algorithm is no difference with breadth first search!!!
I should have rubbed out the tree after d = 1, but this is not breadth first search. It is depth-limited depth first search, starting with a depth limit of 0, and increasing this depth limit incrementally until a solution is found.
@@johnlevine2909 Btw, in IDS, if we are solving a sliding puzzle using tree search, do we take into account of redundant/loop path?
This is totally different from BFS. You can see at level 2, the BFS could have expanded other two nodes also. But here with ID, it does just expanded the left most node and done with it at level 2.