Brainscape's Knowledge GenomeTM

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


See full index

Intro to AI > Uninformed Search > Flashcards

Uninformed Search Flashcards

1
Q

What is a problem-solving agent

A

an agent that considers a sequence of actions that form a path to a goal state

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

What is an atomic representation

A

When the states of the world are considered as wholes, with no internal structure visible to the problem-solving algorithms

In this representation, each state of the world is a black box that has no internal structure. E.g., finding each state is a city. AI algorithms: search, games, Markov decision processes, hidden Markov models, etc.

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

What is factored representation?

A

when each state has some attribute value properties. E.g., GPS location, amount of gas in the tank. AI algorithms: constraint satisfaction, and Bayesian networks.

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

What is structured representation?

A

When relationships between the objects of a state can be explicitly expressed. AI algorithms: first-order logic, knowledge-based learning, natural language understanding

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

What is an uninformed search?

A

A search where the agent can’t estimate how far from the goal it is

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

What is the state space?

A

a set of possible states an environment can be in

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

What is the initial state?

A

the state the agent starts in

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

What is a goal state?

A

The state that we want the agent to reach

An agent can have 1+ goal states

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

What is a transition model?

A

says what each action does

e.g. Result of (s, a), where s = state and a = action
returns the state that results from doing that action in state s

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

What is an action cost function?

Action-Cost(s, a, s’)

A

Gives the cost of applying an action a in state s to reach state s’

s = current state
a = action to be applied
s’ = the state we want to reach

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

T/F: a sequence of actions forms a path

A

True

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

T/F: a solution is a path from the initial state to a goal state

A

True

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

What is an optimal solution?

A

solution that has the lower path cost amongst all solutions

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

T/F: the state space cannot be represented as a graph

A

False, it can

vertices = states

edges = the actions

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

What is a model

A

an abstract mathematical description

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

What is abstraction?

A

the process of removing details form a representation

An abstraction is valid if we can elaborate any abstract solution into a solution in the more detailed world

an abstraction is useful if carrying out each of the actions in the solution is easier than the original problem

Good abstraction –> removing as much detail as possible while still having validity and ensuring the abstract actions are easy to carry out

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

What is a search algorithm?

A

takes a search problems as input and returns a solution or indication of failure

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

What is the difference between the state space and the search tree?

A

State space: all the possible set of states in the worlds, and the actions that allow transitions from one state to another

Search tree: describes paths between these states, reaching towards the goal

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

T/F: A search tree can have multiple paths to any given state?

A

True

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

Does each node in a search tree have a unique path back to the root?

A

Yes

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

What is best-first search?

A

Where you choose a node from the fringe with a minimum value of some evaluation function, f(n). You expand the node if it has the minimum value and return it if it’s the goal state. If it’s not the goal state, you expand on it’s children. Keep doing this until the goal is found or all nodes are expanded

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

What are the uninformed search algorithms?

A

BFS
DFS
Depth-limited search
Iterative deepening DFS
Uniform cost search
Bidirection Search

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

What is BFS?

A

Search the tree level by level before expanding and looking at the children

Uses a FIFO queue

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

What are the advantages of BFS?

A

Provides a solutions

Provides the shallowest solution (i.e. least number of steps)

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

What are the disadvantages of BFS?

A

Requires a lot of memory since each level of the tree must be saved in order to expand the next level

Takes a lot of time if the solution is far from the root node

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

What is DFS?

A

Recursive algorithm where you search from the root node to the deepest node (leaf) before back tracking and continuing down the next deepest path

Uses a Stack FILO

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

What are the advantages of DFS?

A

Requires less memory: only needs to store a stack of the nodes on the path

Takes less time to reach the goal node than BFS if it goes down the right path

28
Q

What are the disadvantages of DFS?

A

Can end up in an infinite loop

No guarantee of finding the solution if states are re-ocurring

29
Q

What are the disadvantages of DFS?

A

Can end up in an infinite loop

No guarantee of finding the solution if states are re-ocdurring

30
Q

Is BFS complete?

A

Yes, if there is a finite number of nodes

31
Q

What is the time complexity of BFS?

A

O (b^d), where d = depth of shallowest solution

32
Q

What is the space complexity of BFS?

A

O (b^d), where d = depth of shallowest solution

33
Q

Is BFS optimal?

A

Yes, if it returns a value, it is the shortest path

34
Q

What is the time complexity of DFS?

A

O (b ^m) where m = maximum depth of the tree

35
Q

What is the space complexity of DFS?

A

O(bm)
This is the size of the fringe

36
Q

Is DFS optimal?

A

No, not guaranteed to provide the shortest path

37
Q

What is Depth-limited search algorithm?

A

Performing DFS with a predetermined limit on the depth DFS can go to

Solved the infinite path problem

two Conditions of failure:
- Standard failure value: It indicates that problem does not have any solution.
- Cutoff failure value: It defines no solution for the problem within a given depth limit.

38
Q

What are the advantages of Depth-limited searhc?

A

memory efficient

39
Q

What are the disadvantages of depth-limited search

A

incomplete
may not be optimal if the problem has more than one solution

40
Q

Is depth-limited search complete?

A

Yes if the solution is above the depth-limit

41
Q

Time complexity of Depth-limited search

A

O(b^l) where l = limit

42
Q

Space complexity of depth-limited search

A

O(bl)

43
Q

Is depth-limited search optimal?

A

No; could find a less optimal goal/path

44
Q

What is uniform cost search?

A

searching a weighted tree or graph

nodes are expanded based on their path costs; the smallest cost in the fringe is expanded and it’s children are also added to the fringe

Uses priority queue

45
Q

What are the advantages of uniform cost search

A

optimal because it returns the smallest costing path

46
Q

what are the disadvantages of uniform cost search

A

Can get stuck in an infinite loop

47
Q

Is uniform cost search complete?

A

Yes; if there is a solution, it will find it

48
Q

What is the time complexity of uniform cost search?

A

O(b^ (1 + [C/ε]) ), where
C = cost of the optimal solution
ε = each step to get closer to the goal node

number of steps taken = C/ε+1, where
+1 is added since we start from state 0 and end at C/ε

49
Q

What is the space complexity of uniform cost search?

A

O(b^ (1 + [C/ε]) ), where
C = cost of the optimal solution
ε = each step to get closer to the goal node

number of steps taken = C/ε+1, where
+1 is added since we start from state 0 and end at C/ε

50
Q

Is uniform cost search optimal?

A

Yes; always gives the least costing path

51
Q

What is iterative deepening dfs

A

Combination of DFS and BFS

This algorithm performs depth-first search up to a certain “depth limit”, and it keeps increasing the depth limit after each iteration until the goal node is found.

52
Q

What are the advantages of iterative deepening dfs?

A

Combines benefits of DFS and BFS for fast search and memory efficiency

53
Q

What are the disadvantages of iterative deepening dfs?

A

repeats all of the work of the previous phase

54
Q

Is iterative deepening dfs complete?

A

Yes if the branching factor is finite

55
Q

What is the time complexity of iterative deepening dfs?

A

O(b^d) where d = depth and b = branching factor

56
Q

What is the space complexity of iterative deepening dfs?

A

O(bd) where d = depth

57
Q

Is iterative deepening dfs optimal?

A

Yes, it returns the shortest path

58
Q

What is bidirectional bfs search?

A

Run BFS search from start and goal node until they intersect/meet each other

59
Q

What are the advantages of bidirectional (bfs) search?

A

Fast
requires less memory

60
Q

What are the disadvantages of bidirectional (bfs) search?

A

Hard to implement
Need to know goal state in advance

61
Q

Is bidirection (bfs) search complete?

A

Yes if you use BFS

62
Q

bidirectional search time complexity

A

O(b^(d/2) ) where d = depth

63
Q

What is the bidirectional search space complexity?

A

O(b^(d/2) ) where d = depth

64
Q

Is bidirectional search optimal?

A

Yes, returns shortest path

65
Q

What is the difference between Dijkstra’s algorithm and uniform-cost search?

A

none, they’re the same

Intro to AI (5 decks)

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