# Problem Solving

`Problem Solving – 1`

1. The main task of a problem-solving agent is

a) Solve the given problem and reach to goal

b) To find out which sequence of action will get it to the

goal state

c) Both a) and b)

d) Neither a) nor b)

2. What is state space?

a) The whole problem

b) Your Definition to a problem

c) Problem you design

d) Representing your problem with variable and

parameter

e) A space where you know the solution

3.The problem-solving agent with several immediate

options of unknown value can decide what to do by just

examining different possible sequences of actions that

lead to states of known value, and then choosing the

best sequence. This process of looking for such a

sequence is called Search. State True or False

a) True

b) False

4. A search algorithm takes _________ as an input and

returns ________ as an output.

a) Input, output

b) Problem, solution

c) Solution, problem

d) Parameters, sequence of actions

5. A problem in a search space Is defined by,

a) Initial state

b) Goal test

c) Intermediate states

d) All of the above

6. The Set of actions for a problem in a state space is

formulated by a ___________.

a) Intermediate states

b) Initial state

c) Successor function, which takes current action and

returns next immediate state

d) None of the mentioned

7. A solution to a problem is a path from the initial state

to a goal state. Solution quality is measured by the path

cost function, and an optimal solution has the highest

path cost among all solutions. State whether true or

false.

a) True

b) False

8. The process of removing detail from a given state

representation is called______.

a) Extraction

b) Abstraction

c) Information Retrieval

d) Mining of data

9. A problem solving approach works well for

a) 8-Puzzle problem

b) 8-queen problem

c) Finding a optimal path from a given source to a

destination

10. The _______ is a touring problem in which each city

must be visited exactly once. The aim is to find the

shortest tour.

a) Finding shortest path between a source and a

destination

b) Travelling Salesman problem

c) Map coloring problem

d) Depth first search traversal on a given map

represented as a graph

`Problem Solving Approach – 2`

1. Web Crawler is a/an

a) Intelligent goal-based agent

b) Problem-solving agent

c) Simple reflex agent

d) Model based agent

2. The major component/components for measuring the

performance of problem solving

a) Completeness

b) Optimality

c) Time and Space complexity

d) Correctness

3. A production rule consists of

a) A set of Rule

b) A sequence of steps

c) Both a) and b)

d) Arbitrary representation to problem

e) Directly getting solution

4. Which search method takes less memory?

a) Depth-First Search

c) Both (a) and (b)

d) Linear Search

e) Optimal search

5. Which is the best way to go for Game playing

problem?

a) Linear approach

b) Heuristic approach (Some knowledge is stored)

c) Random approach

d) an Optimal approach

e) Stratified approach

6. The game of Poker is a single agent.

a) True

b) False

7. Satellite Image Analysis System is (Choose the one

that is not applicable).

a) Episodic

b) Semi-Static

c) Single agent

d) Partially Observable

8. What is the rule of simple reflex agent?

a) Simple-action rule

b) Condition-action rule

c) Both a & b

d) None of the mentioned

9. An agent is composed of,

a) Architecture

b) Agent Function

c) Perception Sequence

d) Architecture and Program

10. In which of the following agent does the problem

generator is present?

a) Learning agent

b) Observing agent

c) Reflex agent

d) None of the mentioned

`Uninformed Search Strategy`

1. Which search strategy is also called as blind search?

a) Uninformed search

b) Informed search

c) Simple reflex search

d) All of the mentioned

2. How many types are available in uninformed search

method?

a) 3

b) 4

c) 5

d) 6

3. Which search is implemented with an empty first-infirst-out queue?

a) Depth-first search

c) Bidirectional search

d) None of the mentioned

4. When is breadth-first search is optimal?

a) When there is less number of nodes

b) When all step costs are equal

c) When all step costs are unequal

d) Both a & c

5. How many successors are generated in backtracking

search?

a) 1

b) 2

c) 3

d) 4

6. What is the space complexity of Depth-first search?

a) O(b)

b) O(bl)

c) O(m)

d) O(bm)

7. How many parts does a problem consists of?

a) 1

b) 2

c) 3

d) 4

8. Which algorithm is used to solve any kind of problem?

a) Breath-first algorithm

b) Tree algorithm

c) Bidirectional search algorithm

d) None of the mentioned

9. Which search algorithm imposes a fixed depth limit on

nodes?

a) Depth-limited search

b) Depth-first search

c) Iterative deepening search

d) Bidirectional search

10. Which search implements stack operation for

searching the states?

a) Depth-limited search

b) Depth-first search

d) None of the mentioned

`Uninformed Search and Exploration – 1`

1. Blind searching is general term for

a) Informed Search

b) Uninformed Search

c) Both a and b

d) Only a

2. Strategies that know whether one non-goal state is

“more promising” than another are called

a) Informed Search

b) Unformed Search

c) Heuristic Search

d) Blind Search

3. Which of the following is/are Uninformed Search

technique/techniques

a) Breath First Search (BFS)

b) Depth First Search (DFS)

c) Bi-directional Search

d) Best First Search

4. Which data structure conveniently used to implement

BFS?

a) Stacks

b) Queues

c) Priority Queues

d) Circular Queues

5. Which data structure conveniently used to implement

DFS?

a) Stacks

b) Queues

c) Priority Queues

d) All of the above

6. The time and space complexity of BFS is (For time and

space complexity problems consider b as branching

factor and d as depth of the search tree.)

a) O(bd+1) and O(bd+1)

b) O(b2) and O(d2)

c) O(d2) and O(b2)

d) O(d2) and O(d2)

7. Breadth-first search is not optimal when all step costs

are equal, because it always expands the shallowest

unexpanded node. State whether true or false.

a) True

b) False

8. uniform-cost search expands the node n with

the__________.

a) Lowest path cost

b) Heuristic cost

c) Highest path cost

d) Average path cost

9. Depth-first search always expands the ______ node in

the current fringe of the search tree.

a) Shallowest

b) Child node

c) Deepest

d) Minimum cost

10. Breadth-first search always expands the ______ node

in the current fringe of the search tree.

a) Shallowest

b) Child node

c) Deepest

d) Minimum cost

`Uninformed Search and Exploration – 2`

1. Optimality of BFS is

a) When there is less number of nodes

b) When all step costs are equal

c) When all step costs are unequal

d) Both a & c

2. How many successors are generated in backtracking

search?

a) 1

b) 2

c) 3

d) 4

3. What is the space complexity of Depth-first search?

a) O(b)

b) O(bl)

c) O(m)

d) O(bm)

4. Which search algorithm imposes a fixed depth limit on

nodes?

a) Depth-limited search

b) Depth-first search

c) Iterative deepening search

d) Bidirectional search

5. LIFO is ______ where as FIFO is ________?

a) Stack, Queue

b) Queue, Stack

c) Priority Queue, Stack

d) Stack. Priority Queue

6. When the environment of an agent is partially

observable in search space following problem/problems

could occur.

a) Sensorless problems: If the agent has no sensors at all,

then (as far as it knows) it could be in one of several

possible initial states, and each action might therefore

lead to one of several possible successor states.

b) Contingency problems: If the environment is partially

observable or if actions are uncertain, then the agent’s

percepts provide new information after each action.

Each possible percept defines a contingency that must

be planned for. A problem is called adversarial if the

uncertainty is caused by the actions of another agent.

c) Exploration problems: When the states and actions of

the environment are unknown, the agent must act to

discover them. Exploration problems can be viewed as

an extreme case of contingency problems

d) All of the above

7. For general graph, how one can get rid of repeated

states?

a) By maintaining a list of visited vertices

b) By maintaining a list of traversed edges

c) By maintaining a list of non-visited vertices

d) By maintaining a list of non-traversed edges

8. DFS is ______ efficient and BFS is __________

efficient.

a) Space, Time

b) Time, Space

c) Time, Time

d) Space, Space

9. The main idea of bi-directional search is to reduce the

time complexity by searching two way simultaneously

from start node and another from goal node.

a) True

b) False

10. An algorithm is complete if

a) It terminates with a solution when one exists

b) It starts with a solution

c) It does not terminate with a solution

d) It has a loop

e) It has a decision parameter.

`Informed Search Strategy`

1. What is the other name of informed search strategy?

a) Simple search

b) Heuristic search

c) Online search

d) None of the mentioned

2. How many types of informed search method are in

artificial intelligence?

a) 1

b) 2

c) 3

d) 4

3. Which search uses the problem specific knowledge

beyond the definition of

the problem?

a) Informed search

b) Depth-first search

d) Uninformed search

4. Which function will select the lowest expansion node

atfirst for evaluation?

a) Greedy best-first search

b) Best-first search

c) Both a & b

d) None of the mentioned

5. What is the heuristic function of greedy best-first

search?

a) f(n) != h(n)

b) f(n) < h(n) c) f(n) = h(n) d) f(n) > h(n)

6. Which search uses only the linear space for searching?

a) Best-first search

b) Recursive best-first search

c) Depth-first search

d) None of the mentioned

7. Which method is used to search better by learning?

a) Best-first search

b) Depth-first search

c) Metalevel state space

d) None of the mentioned

8. Which search is complete and optimal when h(n) is

consistent?

a) Best-first search

b) Depth-first search

c) Both a & b

d) A* search

9. Which is used to improve the performance of heuristic

search?

a) Quality of nodes

b) Quality of heuristic function

c) Simple form of nodes

d) None of the mentioned

10. Which search method will expand the node that is

closest to the goal?

a) Best-first search

b) Greedy best-first search

c) A* search

d) None of the mentioned

`Informed Search and Exploration – 1`

1. A heuristic is a way of trying

a) To discover something or an idea embedded in a

program

b) To search and measure how far a node in a search

tree seems to be from a goal

c) To compare two nodes in a search tree to see if one is

better than another

d) Only a) and b)

e) Only a), b) and c)

2. A* algorithm is based on

b) Depth-First –Search

c) Best-First-Search

d) Hill climbing

3. The search strategy the uses a problem specific

knowledge is known as

a) Informed Search

b) Uniform-Cost Search

c) Heuristic Search

d) Best First Search

4. Uninformed search strategies are better than

informed search strategies.

a) True

b) False

5. Best-First search is a type of informed search, which

uses ________________ to choose the best next node

for expansion.

a) Evaluation function returning lowest evaluation

b) Evaluation function returning highest evaluation

c) Both a & b can be used

d) None of them is applicable

6. Best-First search can be implemented using the

following data structure.

a) Queue

b) Stack

c) Priority Queue

d) Circular Queue

7. The name “best-first search” is a venerable but

inaccurate one. After all, if we could really expand the

best node first, it would not be a search at all; it would

be a straight march to the goal. All we can do is choose

the node that appears to be best according to the

evaluation function. State whether true or false.

a) True

b) False

8. Heuristic function h(n) is,

a) Lowest path cost

b) Cheapest path from root to goal node

c) Estimated cost of cheapest path from root to goal

node

d) Average path cost

9. Greedy search strategy chooses the node for

expansion

a) Shallowest

b) Deepest

c) The one closest to the goal node

d) Minimum heuristic cost

10. In greedy approach evaluation function is

a) Heuristic function

b) Path cost from start node to current node

c) Path cost from start node to current node + Heuristic

cost

d) Average of Path cost from start node to current node

and Heuristic cost

`Informed Search and Exploration – 2`

1. Optimality of BFS is

a) When there is less number of nodes

b) When all step costs are equal

c) When all step costs are unequal

d) Both a & c

2. How many successors are generated in backtracking

search?

a) 1

b) 2

c) 3

d) 4

3. What is the space complexity of Greedy search?

a) O(b)

b) O(bl)

c) O(m)

d) O(bm)

4. In A* approach evaluation function is

a) Heuristic function

b) Path cost from start node to current node

c) Path cost from start node to current node + Heuristic

cost

d) Average of Path cost from start node to current node

and Heuristic cost

5. A* is optimal if h(n) is an admissible heuristic-that is,

provided that h(n) never underestimates the cost to

reach the goal.

a) True

b) False

6. What is the other name of informed search strategy?

a) Simple search

b) Heuristic search

c) Online search

d) None of the mentioned

7. What is the heuristic function of greedy best-first

search?

a) f(n) != h(n)

b) f(n) < h(n) c) f(n) = h(n) d) f(n) > h(n)

8. Which search uses only the linear space for searching?

a) Best-first search

b) Recursive best-first search

c) Depth-first search

d) None of the mentioned

9. Which method is used to search better by learning?

a) Best-first search

b) Depth-first search

c) Metalevel state space

d) None of the mentioned

10. Which is used to improve the performance of

heuristic search?

a) Quality of nodes

b) Quality of heuristic function

c) Simple form of nodes

d) None of the mentioned

`Local Search Problems and Optimization Problems – 1`

1. In many problems the path to goal is irrelevant, this

class of problems can be solved using,

a) Informed Search Techniques

b) Uninformed Search Techniques

c) Local Search Techniques

d) Only a and b

2. Though local search algorithms are not systematic, key

a) Less memory

b) More time

c) Finds a solution in large infinite space

d) No optimum solution

3. A complete, local search algorithm always finds goal if

one exists, an optimal algorithm always finds a global

minimum/maximum. State whether True or False.

a) True

b) False

4. _______________ Is an algorithm, a loop that

continually moves in the direction of increasing value –

that is uphill

a) Up-Hill Search

b) Hill-Climbing

c) Hill algorithm

d) Reverse-Down-Hill search

5. Hill-Climbing algorithm terminates when,

a) Stopping criterion met

b) Global Min/Max is achieved

c) No neighbor has higher value

d) Local Min/Max is achieved

6. One of the main cons of hill-climbing search is,

a) Terminates at local optimum

b) Terminates at global optimum

c) Does not find optimum solution

d) Fail to find a solution

7. Stochastic hill climbing chooses at random from

among the uphill moves; the probability of selection can

vary with the steepness of the uphil1 move.

a) True

b) False

8. Hill climbing sometimes called ____________ because

it grabs a good neighbor state without thinking ahead

a) Needy local search

b) Heuristic local search

c) Greedy local search

d) Optimal local search

9. Hill-Climbing approach stuck for the following reasons

a) Local maxima

b) Ridges

c) Plateaux

d) All of above

10. ___________ algorithm keeps track of k states rather

than just one.

a) Hill-Climbing search

b) Local Beam search

c) Stochastic hill-climbing search

d) Random restart hill-climbing search

`Local Search Problems and Optimization Problems – 2`

1. A genetic algorithm (or GA) is a variant of stochastic

beam search in which successor states are generated by

combining two parent states, rather than by modifying a

single state.

a) True

b) False

2. Mark two main features of Genetic Algorithm

a) Fitness function

b) Cross-over techniques

c) Individuals among the population

d) Random mutation

3. Which search agent operates by interleaving computation and action?

a) Offline search

b) Online search

d) Depth-first search

4. What is called as exploration problem?

a) State and actions are unknown to the agent

b) State and actions are known to the agent

c) Only actions are known to agent

d) Both b & c

5. In which state spaces does the online-dfs-agent will

work?

a) Irreversible state spaces

b) Reversible state spaces

c) searchable state spaces

d) All of the mentioned

6. Which search algorithm will use limited amount of

memory?

a) RBFS

b) SMA*

c) Hill-climbing search algorithm

d) Both a & b

7. How the new states are generated in genetic

algorithm?

a) Composition

b) Mutation

c) Cross-over

d) Both b & c

8. Which method is effective for escaping from local

minima?

a) Updating heuristic estimate

b) Reducing heuristic estimate

c) Eliminating heuristic estimate

d) None of the mentioned

9. Which of the following algorithm is online search

algorithm?

b) Depth-first search algorithm

c) Hill-climbing search algorithm

d) None of the mentioned

10. Searching using query on Internet is, use of

___________ type of agent

a) Offline agent

b) Online agent

c) Both a & b

d) Goal Based

`Constraints Satisfaction Problems – 1`

1. _________________ are mathematical problems

defined as a set of objects whose state must satisfy a

number of constraints or limitations.

a) Constraints Satisfaction Problems

b) Uninformed Search Problems

c) Local Search Problems

d) Only a) and b)

2. Which of the Following problems can be modeled as

CSP?

a) 8-Puzzle problem

b) 8-Queen problem

c) Map coloring problem

d) Sudoku

3. What among the following constitutes to the

incremental formulation of CSP?

a) Path cost

b) Goal cost

c) Successor function

d) Objective function

e) Initial state

4. The term ___________ is used for a depth-first search

that chooses values for one variable at a time and

returns when a variable has no legal values left to assign.

a) Forward search

b) Backtrack search

c) Hill algorithm

d) Reverse-Down-Hill search

5. To overcome the need to backtrack in constraint

satisfaction problem can be eliminated by

a) Forward Searching

b) Constraint Propagation

c) Backtrack after a forward search

d) Omitting the constraints and focusing only on goals

7. Consider a problem of preparing a schedule for a class

of student. This problem is a type of

a) Search Problem

b) Backtrack Problem

c) CSP

d) Planning Problem

8. Constraint satisfaction problems on finite domains are

typically solved using a form of ___________.

a) Search Algorithms

b) Heuristic Search Algorithms

c) Greedy Search Algorithms

d) DFS/BFS Search Algorithms

9. Solving a constraint satisfaction problem on a finite

domain is an/a ___________ problem with respect to

the domain size.

a) P complete

b) NP complete

c) NP hard

d) Domain dependent

10. ____________ is/are useful when the original

formulation of a problem is altered in some way,

typically because the set of constraints to consider

evolves because of the environment.

a) Static CSPs

b) Dynamic CSPs

c) Flexible CSPs

d) None of the above

`Constraints Satisfaction Problems – 2`

1. Flexible CSPs relax on,

a) Constraints

b) Current State

c) Initial State

d) Goal State

2. Language/Languages used for programming Constraint

Programming includes

a) Prolog

b) C++

c) C

d) Fortrun

3. Which search agent operates by interleaving

computation and action?

a) Offline search

b) Online search

d) Depth-first search

4. Backtracking is based on,

a) Last in first out

b) First in first out

c) Recursion

d) Both a & c

5. Constraint Propagation technique actually modifies

the CSP problem.

a) True

b) False

6. Which search algorithm will use limited amount of

memory?

a) RBFS

b) SMA*

c) Hill-climbing search algorithm

d) Both a & b

7. How many the new states are generated in

backtracking algorithm?

a) 1

b) 2

c) 3

d) 4

8. When do we call the states are safely explored?

a) A goal state is unreachable from any state

b) A goal state is denied access

c) A goal state is reachable from every state

d) None of the mentioned

9. Which of the following algorithm is generally used CSP

search algorithm?

b) Depth-first search algorithm

c) Hill-climbing search algorithm

d) None of the mentioned

10. What do we mean by simulated annealing in artificial

intelligence?

a) Returns an optimal solution when there is a proper

cooling schedule

b) Returns an optimal solution when there is no proper

cooling schedule

c) It will not return an optimal solution when there is a

proper cooling schedule

d) None of the mentioned