Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Y1S2_IT1244 > CHAP 3 : Search Techniques (uninformed) > Flashcards

CHAP 3 : Search Techniques (uninformed) Flashcards

1
Q

What is the definition of search?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are inputs in problem formulation? [6]

A
  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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is a state?

A

A representation of physical state

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a node

A

A data structure that is part of a search tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A
  1. Root (parent) node
  2. Child nodes
  3. Edges –> representing the action and costs
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the output of a search problem?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

False

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

False

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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?

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What the definition of a frontier in a search tree?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A
  1. Queue – FIFO
  2. Stack – LIFO
  3. Priority queue – nodes expanded following a priority function that is set between the nodes
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the definition of the explored set?

A

It is the set of leaf nodes that are already explored

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What does the explored set do in a search tree?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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

A

True

18
Q

What is a search strategy?

A

It is the order of picking a node for expansion

19
Q

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

A
  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.
20
Q

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

A

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

21
Q

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

A

Idea : Expand shallowest unexpanded node.

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

22
Q

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

A
  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

23
Q

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

A

True. Uniform cost search is weighted breadth first search

24
Q

Evaluate the uniform cost search

(compare time and space w BFS)

A
  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.
25
Q

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

A

Idea : It expands the deepest unexpanded node

Implementation: Frontier –> LIFO stack, insert successors at the front

26
Q

Evaluate the depth first search technique

A
  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)
27
Q

What are the characteristics of backtracking? [4]

A
  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
28
Q

What is recursion and when is it useful?

A

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

29
Q

What are the sections involved in recursion?

A
  1. Base case
  2. Logic
  3. Recursive call
30
Q

What are the sections involved in recursion?

A
  1. Base case
  2. Logic
  3. Recursive call
31
Q

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

A

True

32
Q

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

A

True

33
Q

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?

A

True

34
Q

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

A

True

35
Q

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

A

False

36
Q
  • UCS is always optimal. Is the statement true or false?
A

True

37
Q

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?

A

False

38
Q

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

A

True

39
Q

DFS is optimal. Is the statement true or false?

A

False

40
Q

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?

A

True

Y1S2_IT1244 (12 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions