Brainscape's Knowledge GenomeTM

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


See full index

CSC325 Artificial Intelligence > Simple Search > Flashcards

Simple Search Flashcards

1
Q

What are the problem types for agents?

A
  • Deterministic
  • Non-observable
  • Nondeterministic and/or partially observable
  • Unknown state space
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a deterministic problem type for agents?

A

Singe-state problem. Agent knowns exactly which state it will be in; solution is a sequence (fully observable)

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

What is a non-observable problem type?

A

Conformant problem. Agent may have no idea where it is; solution (if any) is a sequence

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

What is a nondeterministic and/or partially observable problem type?

A

Contingency problem. Percepts provide new information about current state. Solution is a contingent plan or a policy. Often interleaves search, execution.

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

What is an unknown state space problem type?

A

Exploration problem

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

What is the single-state problem formula?

A

Problem is defined by four items:
- initial state
- successor function (action-state pairs)
- Goal test
- Path cost
A solution is a sequence of actions leading from the initial state to a goal state.

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

Why must we abstract the real world?

A

The real world is absurdly complex therefore state space must be abstracted for problem solving.

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

What is a state (states vs nodes implementation)?

A

(representation of) A physical configuration

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

What is a node (states vs nodes implementation)?

A

A data structure constituting part of a search tree and includes parent, children, depth, path cost.

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

What are the factors we use to measure problem-solving performance?

A
  • Completeness
  • Optimality
  • Time Complexity
  • Space complexity
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is completeness when measuring problem-solving performance?

A

Is the algorithm guaranteed to find a solution when there is one?

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

What is optimality when measuring problem-solving performance?

A

Does the strategy find the/an optimal solution?

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

What is time complexity when measuring problem-solving performance?

A

How long does does it take to find a solution?

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

What is space complexity when measuring problem-solving performance?

A

How much memory is needed to perform the search?

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

How does breadth-first search work?

A

Expanded the shallowest unexpanded node first (row by row).

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

What is time and space complexity measured in terms of?

A

b - maximum branching factor of the search tree
d - depth of the least-cost solution
m - maximum depth of the state space (can be infinite)

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

What is a search strategy?

A

Picking the order of node expansion

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

What are uniformed search strategies?

A

Use only the information available in the problem definition (no-domain knowledge)

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

Does breadth-first search satisfy the completeness property?

A

Yes (if b, branching factor is finite)

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

What is the time complexity of breadth-first search?

A

O(b^(d+1))

21
Q

What is the space complexity of breadth-first search?

A

O(b^(d+1))

22
Q

Is breadth-first search optimal?

A

Yes if cost = 1 per step, otherwise not optimal in general.

23
Q

Is breadth-first search practical?

A

Not very practical unless solution is an a small tree.

24
Q

What is uniform-cost search?

A

Expand least-cost unexpanded node.

25
Q

What is the implementation of uniform-cost search?

A

Create a fringe which is a queue ordered by path cost, lowest first. Same as breadth-first if steps costs all equal.

26
Q

Does uniform-cost search show completeness?

A

Yes if the cost is within the minimum cost value

27
Q

What is the time complexity of uniform cost search

A

O(b^[C/e]), C is the cost of optimal solution. E is minimum cost

Number of nodes with g (path cost) <= cost of optimal solution

28
Q

What is the space complexity of uniform-cost search?

A

O(b^[C/e]), C is the cost of optimal solution. E is minimum cost
Number of nodes with g <= cost of optimal solution

29
Q

Is uniform-cost search optimal?

A

Yes, nodes are expanded in increasing order of g(n)

30
Q

What is depth-first serch?

A

Expand deepest unexpanded child node. Once full depth has been expanded discard searched side.

31
Q

Does depth-first search show completeness?

A

No- fails in infinite-depth spaces or spaces with loops.

32
Q

What is the time complexity of depth-first search?

A

O(b^m) - terrible if m is much larger than d, but for dense solutions faster than breath-first

33
Q

What is the space complexity of depth-first search?

A

O(bm), linear space

34
Q

Is depth-first search optimal?

A

No - we may end up in infinite paths.

35
Q

What is a depth-limited search?

A

Do a depth-first search until limit x has been reached.

36
Q

What is an Iterative Deepening search?

A

Combination of depth-first search’s space-efficiency and breadth-first search’s fast search. Every call is a DFS with a restricted depth.

37
Q

Does Iterative Deepening search show completeness?

A

Yes

38
Q

What is the time complexity of a iterative deepening search?

A

O(b^d)

39
Q

What is the space complexity of an iterative deepening search?

A

O(bd)

40
Q

Is iterative deepening search optimal?

A

Yes, if step cost = 1

41
Q

Which simple searches are complete and not complete?

A

Complete
- Breadth-first (finite trees)
- Uniform cost (if step cost >= e)
- Depth-first (finite spaces)
- Iterative deepening

Not complete:
- Breadth-first (infinite trees)
- Depth-first (inifinite and loops)
- Depth-limited search
-

42
Q

Which simple searches algorithms are optimal and not optimal?

A

Optimal:
- Breadth-First (only if step cost = 1)
- Uniform-cost (nodes expanded in increasing order)
- Iterative deepening (if step cost = 1)

Not optimal:
- Breadth-First (if step cost > 1)
- Depth-First
- Depth-limited

43
Q

What is the implementation of a depth-first search?

A

Using a fringe, LIFO queue

44
Q

How do dynamic and BDI agents operate?

A

Dynamic and BDI agents work of a reasoning cycle.
- They perceive the environment
- Calculate the goal from the current state
- Determine what rules/actions to take to reach that goal
- Execute the actions

45
Q

What is the graph search infrastructure (for nodes)

A
  • n.STATE
  • n.PARENT
  • n.ACTION
  • n.PATH-COST
46
Q

What is the n.STATE (graph search infrastructure)?

A

The current state is the state space that the current node corresponds to

47
Q

What is the n.PARENT (graph search infrastructure)?

A

The previous node in the state space that generated the current node.

48
Q

What is the n.ACTION (graph search infrastructure)?

A

The action of the previous node (PARENT) that generated the current node

49
Q

What is the n.PATH-COST (graph search infrastructure)?

A

The cost, denoted by g(n), of path from the initial state to the current node

CSC325 Artificial Intelligence (8 decks)

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