Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Fundamentals of AI > IV: Tree Search Techniques > Flashcards

IV: Tree Search Techniques Flashcards

1
Q

What is combinatorial explosion?

A

Rapid growth of the complexity of a program - exponential growth of solutions

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

Why is search so important?

A

A lot of problems can be seen as a ‘search’ for the right answer

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

What is a search space?

A

The set of all possible solutions

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

What is the input to a search algorithm?

A

The problem

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

What does a search algorithm return?

A

A solution to the problem

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

In a search tree what is the depth of a node?

A

The number of branches from the root node to the node

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

What is the depth of a search tree?

A

Depth of the deepest level node

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

How do states of a problem convert to a search tree?

A

They are the nodes

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

What is the search space in the search tree model?

A

The set of all reachable states so all nodes in the tree

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

How do you model operators in a problem/game to the search tree model?

A

They’re the branches as they are actions that move the model from one state to another

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

What is a neighbourhood within a search problem?

A

All possible states reachable from a given state

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

What is a goal test within a search problem?

A

A test to a state to tell if the search reached a state that solves the problem

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

What is path cost within the search tree model?

A

Cost of taking a particular path

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

In the search tree model, what is the branching factor?

A

Average number of branches of all nodes in a tree

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

In search tree model, do we want a large or small branching factor?

A

Small as possible

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

What does BFS stand for?

A

Breadth - First - Search

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

What does BFS do differently to a general search algorithm?

A

Root node is expanded first, expand all nodes at level d before expanding level d+1

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

What does a queue function do for BFS?

A

Add a node to the end of the queue to test

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

What are the three types of nodes during a BFS (tree search)?

A
  • Fringe nodes (open nodes / leaves)
  • Visited nodes (closed nodes)
  • Undiscovered nodes
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

In BFS, what is a fringe node?

A
  • has been discovered
  • has not been processed yet
    e.g. child nodes not explored and hasn’t been tested to see if goal
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

In BFS, what are visited nodes?

A
  • have been processed
    e.g. nodes explored and tested
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is the difference in a search tree between a goal state and a solution?

A

A goal state is just a node that passes tests, the solution is the path taken to get there

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

What are the four criteria for evaluating a search technique?

A
  • Completeness
  • Time complexity
  • Space complexity
  • Optimality
24
Q

Define completeness as an evaluation criteria.

A

Is the search tree guaranteed to find a solution

25
Define time complexity as an evaluation criteria.
How long does it take to find the solution?
26
Define Space complexity as an evaluation criteria.
How much memory is required to complete the task
27
Define Optimality as an evaluation criteria.
Can it find the optimal solution? (not just any)
28
How complete is BFS as a search technique?
A solution will always be found, not necessarily the most optimal, since it won't go deeper if it's found a solution
29
What does big O mean ?
The worst case scenario / most time expensive solution - i.e. if its the very last solution
30
What are b and d in search tree notation?
b - average branching factor d - depth of the search tree
31
What is bd in search tree notation?
Time complexity and space complexity
32
What does DFS stand for?
Depth First Search
33
What is the DFS method?
Root node is expanded first, then one whole branch is explored before exploring another branch/ - its queuing functions adds nodes to the front of the queue when discovered
34
What is space complexity like for DFS?
Only stores the path from the root to the leaf on current branch and unexpanded neighbour nodes - better than BFS
35
How is the time complexity for DFS?
Bad, worse than BFS, in the worst case it's bm
36
How does DFS weigh up in terms of completeness?
With an infinite branch the search would never terminate if there's no goal state in that branch - not complete
37
What does UCS stand for?
Uniform Cost Search
38
How does UCS work?
Nodes are ordered in the queue based on price (nearest is cheapest) therefore when the closest node in queue is explored it's the cheapest
39
What is the point of UCS?
For when different paths cost different amounts (for any kind of 'cost' minimisation)
40
How complete is UCS as a method?
Always finds a solution
41
How optimal is UCS?
Always explores cheapest nodes first so always finds optimal
42
How do BFS and UCS compare using the four criteria? What is the caveat here?
Same for all four criteria, BFS can only be applied on trees where all branches have the same cost
43
What kind of problems can UCS be applied to?
Any as long as costs never decrease along the branches
44
When is DFS useful?
Useful if its adapted for specific problems
45
How is Heuristic search different from blind?
guidance is used to consider states rather than blindly adding to front or back of queue or cost.
46
How does Heuristic search work?
Next best node is explored which is more likely to lead the goal state
47
What is the A* method an example of?
Heuristic search
48
What does A* method combine when it evaluates a node?
The path cost so far and an estimated heuristic cost to the goal
49
In A* method, what does f(n) = g(n) + h(n) mean?
g(n) - path cost from initial state to current state n h(n) - heuristic cost from current state to goal state n f - estimated cost of the cheapest solution through n
50
What does A* become if h is 0?
UCS method, since its only using path cost
51
What happens to A* if h is too large?
h dominates g and becomes Greedy search
52
What actually is h as a guess (in A*)?
A lower bound
53
Why is h a lower bound guess in A*?
To ensure the solution is actually optimal, (the heuristic search isn't overestimating any of the path costs)
54
What does it mean for the heuristic to be admissable?
The heuristic cost estimate is the lowest possible and never an overestimate
55
Give an example of the heuristic estimate being a lower bound in A*.
If the cost is distance to travel between cities then the lowest bound is the straight line distance because you can't travel a shorter distance than that
56

Fundamentals of AI (5 decks)

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