Important Questions and Answers: Logical Agents

1.    Define greedy best-first search.

Greedy best-first search expands the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly. Thus, it evaluates nodes by using the heuristic function f(n) = h(n).

2.    Define A* search.

A* search evaluates nodes by combining g(n), the cost to reach the node, and h(n), the cost to get from the node to the goal.

f(n)=g(n)+h(n)

3.           Define Consistency.

A heuristic h(n) is consistent if, for every node n and every successor n’ of

n generated by any action a, the estimated cost of reaching the goal n is no greater than the step cost of getting to n’ plus the estimated cost of reaching the goal from n’:

h(n) <= c(n, a, n’) | h(n’)

4.    What do you mean by Recursive best-first search?

Recursive best-first search is a simple recursive algorithm that attempts to minimize the operation of standard best-first search, but using only linear space.

5.  What are the reasons that hill climbing often gets stuck?

Local maxima:

A local maximum is a peak that is higher than each of its neighboring states, but lower than the global maximum.

Ridges:

Ridges results in a sequence of local maxima that is very difficult for greedy algorithms to navigate.

Plateaux:

A Plateaux is an area of the state space landscape where the evaluatin function is flat.

6.  Define Hill Climbing Search.

The hill climbing search algorithm is simply a loop that continually moves in the direction of increasing value that is uphill. It terminates when it reaches a “peak”

where no neighbor has a higher value.

7.     Mention the types of hill-climbing search.

·                                                              Stochastic hill climbing

·                                                              First-choice hill climbing

·                                                              Random-restart hill climbing

8.     Why a hill climbing search is called a greedy local search?

Hill climbing is sometimes called greedy local search because it grabs a good neighbor state without thinking ahead about where to go next.

9.  Define genetic algorithm.

A genetic algorithm is a variant of stochastic beam in which successor states are generated by combining two parent states, rather than by modifying a single state.

10. Define Linear Programming problem.

Linear programming problem is in which the constraints must be linear inequalities forming a convex region and the objective function is also linear. This problem can be solved in time polynomial in the number of variables.

11. Define online search problems.

An online search problem can be solved only by an agent executing actions, rather than by a purely computational process. Assume that the agent knows the following:

·                                                                    ACTIONS(s), which returns a list of actions allowed in states.

·                                                                    The steps-cost function c(s, a, s’) note that this cannot be used until the agent knows that s’ is the outcome.

·                                                                    GOAL-TEST(s)

15.          Define constraint satisfaction problem.

Constraint Satisfaction problem is defined by a set of variables, X1,

X2,…..Xn and a set of constraints, c1,c2,…..,cm. Each variable xi has a nonempty domain

Di of possible values. Each constraints Ci involves some subset of the variables and specifies the allowable combinations of values for that subset.

16. Define linear constraints.

Linear constraints are the constraints in which each variable appears only in

linear form.

17. What are the types of Constraints?

Unary Constraints:

Unary constraints are one which restricts the value of a single

variable.

Binary Constraints:

Binary constraints are one with only binary constraints. It can be represented as a constraint graph.

18. Define Triangle Inequality.

A heuristic h(n) is consistent if, for every node n and every successor n’ pf n generated by any action a, the estimated cost of reaching the goal form n is no greater than the step cost of getting to n’ plus the estimated cost of reaching the goal form n’:

H(n)                     <= c(n, a, n’)     +  h(n’)

This is a form of the general triangle equality.

19. Define game.

A game can be defined by the initial state, the legal actions in each state, a terminal test and a utility function that applies to terminal states.

20. What is alpha-beta pruning?

The problem with minimax search is that the number of games states it has to examine is exponential in the number of moves. We can’t eliminate the exponent, but we can effectively cut it in half. The trick is that is possible to compute the correct minimax decision without looking at every node in the game tree. This technique is called alpha-beta pruning.

21. Define Offline search.

Offline search algorithms compute a complete solution before setting in the real world and then execute the solution without recourse to their percepts.

22. Define the term backtracking search.

Backtracking search is used for a depth first search that chooses values for one variable at a time and backtracks when a variable has no legal values left to assign.

23. When a problem is called commutative?

A problem is commutative if the order of application of any given set of actions has no effect on the outcome.

24. What do you mean by minimum remaining values?

Choosing the variable with the fewest “legal” values is called the minimum remaining values heuristic. Otherwise called as “most constraint variable” or “fail first”

25.Define informed search strategy.

Informed search strategy is one that uses problem specific

knowledge beyond the definition of the problem itself that can find solutions more efficiently that an uniformed strategy.

26.What do you mean by Best First Search approach?

Best first search is an instance of the general TREE SEARCH algorithm in which a node is selected for expansion based on an evaluation function, f (n).

27.  Define heuristic function.

Best first search typically use a heuristic function h (n) that estimates the cost of the solution from n.

h(n) = estimated cost of the cheapest path from node n to a goal node.