How does greedy best first search works?

Question

In greedy best first search do we keep all the unexplored nodes alive and keep exploring the ones with minimum heuristic value until we get to a solution or dead end or keep removing those unexplored nodes as well ? I read a lot about it but some says it implements both bfs and dfs ,so there won't be a dead end but some describe it or in a way have unclear explanation as I said above ,if anyone can help clear up this thing for me please? Ty !

Answer 1

Abhay yeah exactly if goal state not found than it will backtrack to the open list available least heuristic value and expand those this way path will be found till goal state. Once you go throu the A* and Ao* algorithm the concept will be more clearer for you.

This kind of problen is consider as OR graph in AI.

Answer 2

Best First Search combines the benefits of both depth first and breadth first
search by moving along a single path at a time but change paths whenever some other path looks more promising than the current path. It uses the concept of informative search technique + heuristic function.

Informed search is an search which is done by selecting the paths and search intelligently in efficient manner and heuristic function is used the concept of selecting best promising path which gives efficient result means selecting the most profitable path with minimum cost. This assign every node an heuristic value.
F(n) = G(n) + H(n)
Where G(n) is path cost and H(n) is heuristic value and this used more advanced in A* algorithm with greedy best first search
https://code.sololearn.com/WE5IospTOq2X/?ref=app
https://www.mygreatlearning.com/blog/best-first-search-bfs/
http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
[part 1/5]

Answer 3

Best first search is worked over listing concept + informative + heuristic search to get optimal path. Listing is used here if two types Opened list and Closed list. When any node is read and scanned that enter in the Opened list and when we further evaluate and expand that and read their child node, at that time due to expanding A is put in Closed list and childs are placed in Opened list. Now the algorithm of best search work with selecting the least heuristic value path and place that in opened list first and then on expanding this will put their child in open and put the parent in closed as it's expanded. This way it uses bredth first search but suppose if the goal state and node where we want to reach is not exsist in the child we expanded till now than the algorithm used the "backtracking approach" by which it backtrack to those nodes whose huerisitc value is least in not expanded nodes.

[part 2/5]

Answer 4

Here A Is source node and J is destination node the heuristic value is assigned beside that it's just an sample example just randomly maded path for explanations purpose. Now look here first A read and enter in opened list than we expand it's successor so a put in closed and B, C, d will be in open list
Opened list :- B C D (the huerisitc value compare least value expanded)
Close list :-A
Than D opens and expanded so D is in close list and E and F is in Open list this way
Open list:- B C E F
Closed list:- A D
Now from open list least huerisitc value selected and expanded which is E so now E read and expanded
Open list :- B C E F
Closed list:- A D
The least heuristic value is selected again from open list and return and expand E
Open list :- B C F I J
Closed list :- A D E
Now as we can reached goal state from here so the resulting path is
A->D->E->J

This way comparison let you know about dfs technique used and per element bfs also on use this way both algorithm is used in that..

[part 4/5]

Answer 5

For example if we consider an graph or tree like this way:-
A->3
/ | \
/ | \
/ | \
6<-B C->5 D->1
/ \ / \
7<-G H->5 4<-E F->6
/ \
2<-I J->2

Here A Is source node and J is destination node the heuristic value is assigned beside that it's just an sample example just randomly maded path for explanations purpose.

[part 3/5]

Answer 6

Abhay the algorithm is used generally with A* with support of greedy best first search and meanwhile the use of pruning approach is also their as alternate min max pruning is used too to find path.

In above example suppose if min hueristic value raise on left subtree or graph than backtracking approach is also used to get that element..

follow the sequence 1 to 5 to go through all answers.
[part 5/5]

Answer 7

Preity yes I am trying to understand those A* and AO* as well ,ty again

Answer 8

I'm going to ping someone much more qualified than me to help you with this question.

Kuba Siekierzyński

Answer 9

Preity thank you so much! Lastly I wanna know that while expanding E if we found out that it has no successor nodes and we haven't reached goal state yet then we will select another element from open list with minimum heuristic value and then expand it?

Answer 10

Abhay no problem. I'm too waiting for more answer here might be they have some more information to provide.