Since I publish my AI lectures' slides in PDF, I uploaded this animation so that the students that attend the class can review it at home. , thus it is not self-contained.
Really helpful! The video elegantly emphasizes the fact that there is both an open priority queue and a closed one which I was struggling to understand
hello sir, can you give an example where Greedy Best First Search gets stuck in an infinite loop? Im having trouble proving it using the open and closed list.
Greedy best first search (GBFS) cannot get stuck in an infinite loop due to the checks in OPEN and CLOSE. However, it can get into an infinite branch. Assume, for example, that the goal is to find a finite string that satisfies some condition. Assume that problem is converted to a search problem by starting from the empty string, and adding one additional letter in each step. For a certain heuristic functions, it is possible for GBFS to get stuck in one branch indefinitely by keeping adding letters.
but this is ucs? greedy bfs would have explored 32 prior to 29 however at the same time idk what your graph looks like so im assuming the node that costs 32 leads back to 29 therefore its depth has ended and we will continue with the first method to get to 29 instead of taking the 26 node method since it costs less
Richard, I'm sorry but I did not get your point. This is Greedy best First Search. The algorithm expands the node in OPEN with the best (minimal) heuristic value. So a node of value 29 will be expanded before a node of value 32.
@@shaulm oh i must have misunderstood the algorithm. I thought that since greedy best first search will choose the best option for what is defined as “in the moment” and acts as a dfs once a least cost node is chosen, then it would continue down that leaf until it has been fully explored. I wasn’t aware that it kept a record or queue of the least cost nodes
Can you peeps maybe enlighten me for my assignment.. like here he followed the right legs cause it was the greedy path leading to his answer, what would happen if you follow the greedy path all the way down the right side and not find your answer? do you just jump back into your next open list item and then follow its greedy path? what I mean by this is we got a alphabetical tree, like A leads to B for a distance of 12 or C for 9, so your obviously gna follow C, but the answer node K that i want is down the left leg. so do i just do the entire right leg then pop back up in the open list to B then do its leg?
better than any 10 min video i've watched so far. Thanks !
Really helpful! The video elegantly emphasizes the fact that there is both an open priority queue and a closed one which I was struggling to understand
Fantastic work. simple and straight forward
Super clear, very intuitive much love and thank you for sharing with us students!
Better than my 3 hour lecture
Why does it choose node 31 first instead of 26?
That's rather understandable. Thanks a lot!
Great video thanks !
thank you so much. it is so simple and understandable
can any one explain why 31 is selected as close node instead of 26 which one is smaller than 31
When the node with value of 31 was selected, it was the best (lowest) node in OPEN. The node with the value of 26 was note discovered yet.
hello sir, can you give an example where Greedy Best First Search gets stuck in an infinite loop? Im having trouble proving it using the open and closed list.
Greedy best first search (GBFS) cannot get stuck in an infinite loop due to the checks in OPEN and CLOSE. However, it can get into an infinite branch. Assume, for example, that the goal is to find a finite string that satisfies some condition. Assume that problem is converted to a search problem by starting from the empty string, and adding one additional letter in each step. For a certain heuristic functions, it is possible for GBFS to get stuck in one branch indefinitely by keeping adding letters.
so what is the difference between this algorithm and UCS?
this one checks heuristic values, while UCS checks path cost
@@12Metatron is that the only difference? So why does it incomplete?
but this is ucs? greedy bfs would have explored 32 prior to 29 however at the same time idk what your graph looks like so im assuming the node that costs 32 leads back to 29 therefore its depth has ended and we will continue with the first method to get to 29 instead of taking the 26 node method since it costs less
Richard, I'm sorry but I did not get your point. This is Greedy best First Search. The algorithm expands the node in OPEN with the best (minimal) heuristic value. So a node of value 29 will be expanded before a node of value 32.
@@shaulm oh i must have misunderstood the algorithm. I thought that since greedy best first search will choose the best option for what is defined as “in the moment” and acts as a dfs once a least cost node is chosen, then it would continue down that leaf until it has been fully explored. I wasn’t aware that it kept a record or queue of the least cost nodes
surprisingly better!
thanks
Thanks
Silent genius.
you're here too.
Assignment needs to be done
Can you peeps maybe enlighten me for my assignment.. like here he followed the right legs cause it was the greedy path leading to his answer, what would happen if you follow the greedy path all the way down the right side and not find your answer? do you just jump back into your next open list item and then follow its greedy path? what I mean by this is we got a alphabetical tree, like A leads to B for a distance of 12 or C for 9, so your obviously gna follow C, but the answer node K that i want is down the left leg. so do i just do the entire right leg then pop back up in the open list to B then do its leg?
I think you got it, when your search leads you to a leaf that's not the goal, you go the next lowest cost node2and so on until you get to the goal
Makes sense thanks, just wanted a second opinion. teamwork makes the dream work
Toda!
קצר ולעניין
תודה רבה