Greedy Best First Search-Artificial Intelligence-Unit - 1 -Problem Solving -Informed Searching
ฝัง
- เผยแพร่เมื่อ 12 พ.ค. 2021
- Unit - 1 - Problem Solving
Informed Searching Strategies - Greedy Best First Search
Greedy best-first search algorithm always selects the path which appears best at that moment.
It is the combination of depth-first search and breadth-first search algorithms.
It uses the heuristic function and search.
With the help of best-first search, at each step, we can choose the most promising node.
In the best first search algorithm, we expand the node which is closest to the goal node and the minimum cost is estimated by heuristic function
The evaluation function is f(n) = h(n)
Were, h(n)= estimated cost from node n to the goal.
Greedy search ignores the cost of the path that has already been traversed to reach n
Therefore, the solution given is not necessarily optimal
Greedy best-first search can start down an infinite path and never return to try other possibilities, it is incomplete
Because of its greediness the search makes choices that can lead to a dead end; then one backs up in the search tree to the deepest unexpanded node
Greedy best-first search resembles depth-first search in the way it prefers to follow a single path all the way to the goal, but will back up when it hits a dead end
The quality of the heuristic function determines the practical usability of greedy search
Greedy search is not optimal
Greedy search is incomplete without systematic checking of repeated states.
In the worst case, the Time and Space Complexity of Greedy Search are both O( b m ),
Where
b is the branching factor and
m the maximum path length
Subscribe this channel, comment and share with your friends.
For Syllabus, Text Books, Materials and Previous University Question Papers and important questions
Follow me on
Blog : dsumathi.blogspot.com/
Facebook Page : profile.php?...
Instagram : / dsumathiphd
shouldn't we include A's h(n) values why summing up at end?
you should have made tree first
personally i have really enjoyed this class, u made it so easy for me to understand,thank you
You're very welcome!
how to find the cost between start A to B,C,E,asking about the values 118,140,75 how did it came??
That was already given in the question itself. It is basically cost between each node. If you calculate that you will get the total cost and if you calculate the heuristic value you will get the total distance so we are finding the optimal solution with help of either characteristic value or cost value. Anyhow, this algorithm is not optimal and it is prone to getting struck.
Why will GBFS back up if it meets a dead end? Then how will GBFS get stuck in a loop then? I hope you can answer my question
bro it will back up only when we use Depth first search (DFS) in greedy best first search.
Very Nice
Thanks for sharing!!
Thanks
You are welcome Melih Ekinci
thank u very much man u r the best
Thank you Nikash Yadav.
Good work, well explained, keep doing
Thank you, I will
Thanks, will do!
I need this slide please send me
good but
better to explain the calculation of h(n)
Thank you
Sorry for that
thank yo
You are welcome, keep watching...
@@WinningCSE where can i find branch and bound lecture ☹
@@5it.005 Branch and bound. Ok
I will try to do this. Which university you are
@@WinningCSE first thank so much ☹❤❤ i rlly value it cuz i get ur explaining v well 💕
is best first search and greedy search is same or different?
Both are different
What happens if two nodes have the same heuristic value?
While implementing this, we found that it takes the first one.
@@WinningCSE How can I get in contact with you, I would like your assistance on some AI questions (Informed search and uninformed search).
Madam Is This Table Will Give In Exam Section??
If it is problem then surely they will give, otherwise if you asked to explain the topic with your own example, then you have to draw the table.
You make things complicated
Is it so
caste ki baat mat kr aunty
Talk louder your voice is not audible
Ok next time
you dont got volume button ?
worst example of the life
Thank you
i do not recommend you
Thank you 🙏