CHAP 4 : Search techniques (informed) Flashcards
** What is true for informed search?
- Can distinguish goal states from non-goal states.
- Can tell which non-goal state is better, given some guidance.
- Cannot tell which non-goal state is better
- Uses an evaluation function that controls the path of the search.
1,2,4
What is the idea behind Best-first search?
- Use an evaluation function, f(n) for each node. It gives an estimate of desirability and we expand the most desirable unexpandable nodes
How to implement best first search? (what data structure is used)
- Order the nodes in frontier in decreasing order of desirability with priority queue data structure.
What are the 2 special cases of best first search?
- Greedy best-first search
- A* Seach
What is the aim of greedy best first search and its drawback?
It aims to minimise search cost , h(n) to the destination by reducing the search domain considerably
Drawback : result is suboptimal
How does greedy best first search compute the cheapest cost to the goal state?
Through heuristic function, h(n).
Best first search uses an evaluation function for specific nodes only. Is the statement true or false?
False
Evaluation function can be described as an estimate of “desirability” to reach goal state. Is the statement true or false?
True
** The implementation of Best-first search orders the nodes in the frontier only in increasing order of desirability. Is the statement true or false?
False, in decreasing order of desirability
Greedy best-first search expands the node that is truly-closest to the goal. Is the statement true or false?
False. It expands the node that appears to be closest to the goal
Evaluate the Greedy Best-first search algorithm. (Completeness, optimal, time and space)
Completeness : Yes, if state space is finite and no duplicate nodes are expanded.
Optimal : No.
Time and space : time and space complexities are exponential if bad heuristic function is used.
Greedy best-first search with a good heuristic function is usually:
- Complete
- Optimal
- Time-efficient
- Space-efficient
1,3,4
What is the aim of uniform cost search and its drawback?
It minimises the cost of the path, g(n) and finds the optimal solution
Drawback : inefficient when domain is large
What kind of function does A* Search use to compute the estimated total cost of the cheapest solution through the current node?
Evaluation function, f(n)
f(n) = g(n) + h(n)
g(n) = actual cost to current state
h(n) = estimated cost to reach goal from current state
A* search takes advantage of both Greedy Best-first Search and Uniform Cost search. Is the statement true or false?
True
A* search is most popularly used in games. Is the statement true or false?
True
What are the 2 criteria that the heuristic function must possess?
- Admissible
- Consistent
What is meant by an admissible heuristic function?
A heuristic function is admissable if for every node n, h(n) <= h*(n)
h*(n) : TRUE COST to reach goal state from current node n
It means that the heuristic function never overestimates the cost to reach the goal.
What is meant by a consistent heuristic function?
A heuristic is consistent if for every node n, every successor n’ of n generated by any action a , we have h(n) <= c(n,a,n’) + h(n’), where c(n,a,n’) is the estimated step cost from n to n’
— basically, a consistent heuristic will not discard truly good options just because it overestimates their cost and treat them as bad options.
Evaluate the A* search algorithm
Complete : Yes, if there is finite no of nodes with cost less than or equal to the cost of the optimal solution path.
Optimal : Yes, if h(n) is consistent
Time and space : Bad in time and space complexity. The space + amt of time is not small, for a big state space, the tree built is very big while enlarging the frontier
Runs out of space before running out of time.
What is optimaisation in AI?
The process to find the state at which the objective function is minimum or maximum.
Local search deals with problems where the path to the goal is irrelevant, and its only aim is to find the goal state. Is the statement true or false?
True
Benefits of local search? [3]
- Checks and updates only the curent state along the path
- Require very little/constant memory
- Find reasonable solutions in large / infinite state spaces
How is local search conducted? [4 steps]
- Start with a feasible solution x
- Define a neighbourhood of x
- Identify an improved neighbour y
- Replace x by y and repeat
What is hill-climbing algorithm?
A hill-climbing algorithm is a local search algorithm that moves continuously upward (increasing) / DOWNWARD (decreasing) until the best solution is attained.
What is an objective function?
The real-valued function whose value is to be either minimized or maximized subject to the constraints.
What are the axes for hill-climbing algorithm?
y-axis : objective function
x- axis : state space
What are the drawbacks of hill-climbing algorithm? [2]
- It cannot detect whether it’s in a local minimum/maximum or a global minimum/maximum.
- It is not always possible to find a global maximum using a hill-climbing search, as there might be local maxima that the algorithm can stuck at.
For the map colouring problem, the either of the followings can be the objective function for optimization. True or False?
(a) number of conflicting regions
(b) number of non-conflicting regions
True.
Aim : minimise no of conflicting regions / maximise no of non-conflicting regions
