SEARCHING ALGORITHMS-I Flashcards
How to choose a Heuristic Function
We use average branching factor (ABF) to choose a heuristic function.
ABF = (No. of explored nodes) /
(Path of Optimal Solution)
What is the Best First Search
The Best First Search picks the most promising node from the Open list in each and every iteration, while adding it’s successors simultaneously until the goal node is found.
Completeness –> For finite search space this is complete, but for infinite search space it depends on the heuristic value.
Optimality –> Depends on the heuristic value.
What is the space and time complexity of Best first Search
Space complexity –> b^d.
Time complexity –> depends on heuristic value.
What is Beam Search Algorithm
Beam Search algo, is an extension to the best first search algo. Best first searches chooses the best node, and stores the rest in memory, where as beam search, also chooses the best node, but stores only a certain amount in memory, this is defined by Beta.
Explain Simple Hill Climbing
Simple hill climbing moves up/down in the direction of better value of the heuristic function i.e. uphill/downhill.
It has no backtracking and stops when no better move is found.
Explain Steepest Hill Climbing
In steepest hill climbing, all the children nodes are checked, out of which the one with the best HF value is selected. This is an optimal solution but takes longer than the simple hill approach.
Mention the Limitations of Hill Climbing Approach
1) Local Maxima –> This state is better than all it’s neighbouring states, but is also not the goal state, which means that improvements cannot be made, and the algorithm fails. This can be fixed by back tracking.
2) Plateau –> A plateau is a flat area of the search space in which a whole set of neighbouring states have the same value. Again, because there can be no improvements, the algorithm fails.
3) Ridge –> A ridge is a special kind of local maximum. It is an area of the search space that is higher than the current node, but cannot be accessed but the directions in which they exist, makes it impossible to traverse a ridge by single moves.
