Brainscape's Knowledge GenomeTM

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


See full index

AI > Searching trees and game playing > Flashcards

Searching trees and game playing Flashcards

1
Q

What is the travelling salesman problem?

A

The minimum cost of a path for a salesperson to starts at any city and must finish at the same city without visiting the same city more than once

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

What is the travelling salesman problem an example of?

A

Combinatorial explosion
Unsolved theoretical problems

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

What is combinatorial explosion?

A

The feature where the number of solutions for a problem grows exponentially with the problem size

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

What is the search space of a problem?

A

Set of all possible solutions to a problem

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

How do we improve the search technique of a problem

A
  • Define problem into a smaller search tree
  • Improve search efficiency
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the branching factor?

A

Number of branches a node has

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

What is the average branching factor?

A

The 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
8
Q

Explain how a breadth first search works

A
  • Look at neighbouring nodes first
  • Add discovered nodes to the end of the queue
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Explain how depth first search work

A
  • Look at children nodes first
  • Add discovered nodes to the front of the queue
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Explain how uniform cost search works

A
  • Look at neighbouring nodes first
  • Add the discovered nodes in order of lowest cost
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the maximum branching factor?

A

The maximum number of children a node has

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

Explain the time, space and optimal completeness of a BFS

A

b is average branching factor
d is depth of tree

Space: b^d
Time: b^d
Optimal: Yes
Complete: Yes

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

Explain the time, space and optimal completeness of a UCS

A

b is the average branching factor
d is the depth of the tree

Space: b^d
Time: b^d
Optimal: Yes
Complete: Yes

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

Explain the time, space, optimal and completeness of DFS

A

b is the average branching factor
m is the maximum branching factor

Space: bm
Time: b^m
Optimal: No
Complete: No

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

What are fringe nodes?

A

Nodes that have been discovered but have not been processed

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

What are visited nodes?

A

Nodes that have been discovered and processed

17
Q

What are undiscovered nodes?

A

Nodes which have not yet been discovered nor processed

18
Q

What is the difference between a blind search and a heuristic search?

A
  • Blind search blindly explores the next node
  • Heuristic search searches the next best node using domain knowledge
19
Q

Explain the concept of the A* search algorithm

A

Finds shortest path to goal state using heuristics
- Order nodes by:
f(n) = g(n) + h(n)
- g is path cost from initial to current state
- h is heuristic cost from current state to goal state

20
Q

What does admissible heuristic mean?

A

if the heuristic never overestimates the actual cost to reach the goal (must be <=)

21
Q

Provide one guideline in designing a better admissible heuristics

A

The closer the estimate of the heuristic, the
better! (<= is better than <)

22
Q

What happens when the heuristic cost from current state to goal state is 0?

A

Search turns into a UCS, complete and optimal but blind

23
Q

What happens are h -> ∞? (where the heuristic cost from current state to goal state is very large)

A

Dominates cost of path from initial state to current state, the search becomes greedy and not optimum

24
Q

What is a good heuristic?

A
  1. It is admissible
  2. It is close to the actual cost
25
Q

What is the concept of the MinMax algorithm?

A

Maximise your position and minimise opponent

26
Q

What do utility functions do?

A

Measure how good a position is

27
Q

How do we know if we have a perfect game?

A

The root node will be 1, not 0

28
Q

What is meant by a perfect game?

A

The computer and human player picks perfectly

29
Q

If a node has no branches, what does that mean for the min/max this turn?

A

Min/max lost (so typically assign a 0)

30
Q

What is alpha-beta pruning search

A

Searching that uses supervised and reinforcement learning, stops searching as soon as it can deduce a solution

31
Q

What is meant by the completeness of a search?

A

We are guaranteed to find a solution if one exists

32
Q

What is meant by the time complexity of a search

A

How long it takes to find a solution

33
Q

What is meant by the space complexity of a search?

A

How much memory is required to perform the search

34
Q

How do we define a search problem?

A

Operators
States
Goal state

AI (5 decks)

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