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)
12. 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.
13. Define linear constraints.
Linear constraints are the
constraints in which each variable appears only in linear form.
14. 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.
15. 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.
16. 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.
17. 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.
18. 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.
19. 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.
20. 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.
21. 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”
22.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.
23.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).
24. 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.
No comments:
Post a Comment