Module 3 Flashcards

1
Q

What is an agent that plans ahead

A

Problem solving agent

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

What spectrum do problem solving agents use

A

Atomic structure

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

What spectrum do planning agents use

A

Factored or structured

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

What is an informed algorithm

A

Agent can estimate how far it is from the goal

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

What is uninformed algorithm

A

No estimate available

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

What are the four phases of problem solving agents

A

Goal formulation, problem formulation, search, execute

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

What do search problems consist of?

A
States space  - S
Initial state - S0
Action in state - A(s) 
Transition model - Results (s,a) 
Goal test - G(s)
Action cost  c(s,a,s’)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is a solution

A

An action sequence that reaches goal state

Optimal solutions reaches goal state with least steps

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

What are standardized problems

A

Can be given precise exact descriptions and can compare performance of algorithms

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

What is a real world problem

A

Solution people use and formulation is idiosyncratic

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

Characteristics of state space graphs

A

Nodes are abstract world configurations
Arcs represent successors
Goal test is a set of goal node(s)
Each state occurs once

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

State graph vs search tree

A

Each node in search tree is a path in state graph

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

Name all search data structures

A

node. state - current state of node
node. parent - parent of current node
node. action - action through which arrived at current node
node. path-cost - total cost to current node from initial node

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

List types of nodes, are they reached?

A

Generated nodes and expanded nodes

Both nodes are considered reached

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

List frontier functions

A

IsEmpty - returns true/false
Pop - removes top node and returns it
Top - returns top node
Add -inserts node into place

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

What measures are there for problem solving performance

A

Completeness - is algorithm guaranteed to find solution and reports failure

Cost optimality - does it find solution at lowest cost

Time complexity - how long does it take to find a solution

Space complexity - how much memory is needed

17
Q

List BFS properties ( space + search , complete, optimal)

A
Space + Search time - O(b^s) 
B - nodes at solution level
S - depth at solution level
Complete 
Optimal if costs are equal
FIFO
18
Q

List UCS properties ( space + search , complete, optimal)

A
Space + Search time - O( b ^ C* / E ) 
C* - total cost of solution 
E - least cost of arc
Complete if C* finite
Optimal 
Priority Queue
19
Q

List DFS properties ( space + search , complete, optimal)

A
Search time - O( b ^ m)
Space - O (bm)
B - nodes at lowest level 
M - levels
Not Complete if M infinite 
Not Optimal
LIFO
20
Q

When is BFS better than DFS

A

On sparse graph with low branching
Requirement to find optimal solution and search entire space
When there is a shallow solution , s

21
Q

When is DFS better than BFS

A

Where tree like search feasible , less memory

When solution at all m, and common at m

22
Q

What is iterative deepening

A

Tries to get DFS space advantage with BFS time advantage

Runs DFS with level limits

23
Q

What is the purpose of an informed search

A

Guide the search towards the goal using domain specific hints called heuristics

More efficient that uninformed

24
Q

What are heuristics and notation

A
Hints 
H(n) - est cost of cheapest path from node to goal state
25
Q

List properties of Greedy best first search

A
Expands node with lowest h(n) value 
It’s complete 
Search and Time - O ( V ) 
With good h(n) - O (bm)
Con - does not consider cost already incurred
26
Q

List properties of A* search

A

Expands node most likely to be optimal path
Expands node with lowest g(n) + h(n) value
- g(n) cost from root to node
- h
(n) optimal cost node to goal
Priority queue
Complete

27
Q

When is heuristic admissible

A

If 0<= h(n) <= h*(n)

where h*(n) is true cost to nearest goal

28
Q

What problems are Admissible heuristics a solution for

A

Relaxed problems