CHAP 3 : Search Techniques (uninformed)

Question 1

What is the definition of search?

Answer 1

It is the process of looking for a sequence of actions that reaches the goal.

Question 2

What are inputs in problem formulation? [6]

Answer 2

1. State space
   - all possible combinations of states in the end, set of all possible configurations of a system
2. Action space
3. Successor function
   - a description of possible actions, a set of operators.
   - for state x, returns s(x) –> Given a state, generates its sucessor states
4. Start state
5. Goal test (aka goal state)
6. Path cost
   - A function that assigns a numeric value to each path.

Question 3

What is a state?

Answer 3

A representation of physical state

Question 4

What is a node

Answer 4

A data structure that is part of a search tree

Question 5

What is a branching factor?
What is the branching factor of the search trees given in the slides?

Answer 5

• The branching factor is the number of children at each node.
• The search trees in the slides have a branching factor of 2. (Binary tree)

Question 6

What are the parts of a search tree? [3]

Answer 6

1. Root (parent) node
2. Child nodes
3. Edges –> representing the action and costs

Question 7

What is the output of a search problem?

Answer 7

The output is the sequence of actions that reaches the goal state from the current state.

Question 8

Predicting the sales price of an HDB flat is considered a search technique. Is the statement True or False?

Answer 8

False

Question 9

The maximum number of elements in an action space is one. Is the statement true or false?

Answer 9

False

Question 10

Goal test finds if a state is goal state or not a goal state. Is the statement true or false?

Answer 10

True

Question 11

Search Trees are data structures that are used to represent the search problem. Is the statement true or false?

Answer 11

True

Question 12

When planning a route for a robot, it is possible to build a search tree to find the most optimal routes. Is the statement true or false?

Answer 12

True

Question 13

What the definition of a frontier in a search tree?

Answer 13

It is the set of unexplored child nodes that is to be expanded

Question 14

What kind of data strucutres may be used for the frontier and how do they work?

Answer 14

1. Queue – FIFO
2. Stack – LIFO
3. Priority queue – nodes expanded following a priority function that is set between the nodes

Question 15

What is the definition of the explored set?

Answer 15

It is the set of leaf nodes that are already explored

Question 16

What does the explored set do in a search tree?

Answer 16

It saves unique instances of the states from the search tree.

Question 17

The explored set needs to provide fast insertion and searching. True or False?

Answer 17

True

Question 18

What is a search strategy?

Answer 18

It is the order of picking a node for expansion

Question 19

What are the criteria that strategies are evaluated based on? Give the definitions too

Answer 19

1. Completeness : guarantee of finding a solution
2. Optimality : guarantee of finding an optimal solution
3. Time complexity : time spent to find a solution
4. Space complexity : memory space needed to perform the search.

Question 20

What is the main difference between uninformed search techniques and informed search techniques?

Answer 20

Uninformed search techiques use only the info that is avail in the problem definition, and have no additional info about the states and cannot distinguish which non-goal state is better. They blindly try all possible ways to reach the target.

However, informed search techniques can tell which non-goal state is better, given some guidance

Question 21

What is the idea behind the breadth first search and how is it implemented (frontier)?

Answer 21

Idea : Expand shallowest unexpanded node.

Implementation : Frontier is a FIFO queue, i.e. insert new successors at the end

Question 22

Evaluate breadth first search based on completeness, optimality, space and time complexity.

Answer 22

1. Completeness : BFS is complete, IF BRANCHING FACTOR IS FINITE
2. Optimality : Optimal, IF STEP COST = 1
3. Space complexity : increases exponentially
4. Time complexity : time taken increases as depth of tree increases

Space is a bigger problem than time

Question 23

Uniform cost search is an extension of the breadth first search. True or False?

Answer 23

True. Uniform cost search is weighted breadth first search

Question 24

Evaluate the uniform cost search

(compare time and space w BFS)

Answer 24

1. Complete : Yes, if all state’s actions have non-negative values
2. Optimal : Yes. Uniform-cost search expands nodes in order of their optimal path cost.
3. Time and space : Performs worse than BFS — list is required to be kept and sorted as priorities in queue, store step costs etc.

Question 25

What is the idea of depth first search? How is it implemented?

Answer 25

Idea : It expands the deepest unexpanded node Implementation: Frontier --> LIFO stack, insert successors at the front

Question 26

Evaluate the depth first search technique

Answer 26

1. Completeness : Yes, if state space is FINITE with no repeated states and path 2. Optimal : No, may find a solution at a deep level while a more optimal solution exists at a shallow level to the right side of the tree (bc always expand left first)

Question 27

What are the characteristics of backtracking? [4]

Answer 27

1. Only one successor is generated at a time 2. Each partially expanded node remebers which successor to generate next 3. Once a node has been expanded and al its descendants are fully explored, it can be removed from memor if goal state not found 4. Uses recursion

Question 28

What is recursion and when is it useful?

Answer 28

Recursion is a function calling itself and it is useful in solving problems that can broken down into smaller problems of the same kind

Question 29

What are the sections involved in recursion?

Answer 29

1. Base case 2. Logic 3. Recursive call

Question 30

What are the sections involved in recursion?

Answer 30

1. Base case 2. Logic 3. Recursive call

Question 31

Breadth-first search is usually considered as complete (if branching factor=1) and optimal (step cost=1). Is the statement true or false?

Answer 31

True

Question 32

Breadth-first search is usually considered as complete (if branching factor=1) and optimal (step cost=1). Is the statement true or false?

Answer 32

True

Question 33

In Breadth-first search, memory space to store the nodes is usually the bigger problem than the computation time. Is the statement true or false?

Answer 33

True

Question 34

UCS expands the node from the frontier with the cheapest path cost. Is the statement true or false?

Answer 34

True

Question 35

UCS is always complete for any given search problem. Is the statement true or false?

Answer 35

False

Question 36

* UCS is always optimal. Is the statement true or false?

Answer 36

True

Question 37

The key difference between Breadth-first search and Depth-first search (DFS) is that the frontier for DFS operates using a FIFO order. Is the statement true or false?

Answer 37

False

Question 38

DFS expands from the deepest unexpanded node. Is the statement true or false?

Answer 38

True

Question 39

DFS is optimal. Is the statement true or false?

Answer 39

False

Question 40

By using Backtracking only one successor node is generated at a time. This property of backtracking makes the search algorithm memory efficient. Is the statement true or false?

Answer 40

True