Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

AI > Ch 3 (uninformed search) > Flashcards

Ch 3 (uninformed search) Flashcards

(63 cards)

Start Studying
1
Q

What are the components of search problem

A

State space
Start state
Goal state
Successor function
Solution

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

What is the state space

A

The set of all possible states in the problem

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

What is a successor function

A

Input : currect state and action
Output :cost(time,money) and next state
When we want to talk about it we say the action taken, and the cost

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

What is a start state ?

A

The state that we start the search from

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

What is the goal state

A

The state we want to reach

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

What is the goal test function

A

Function tests if the state is goal or not

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

What is a solution in search problem

A

Sequence of actions that take us from start to goal

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

How to know that a problem is search problem

A

When it has all the components

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

What are the strategies when talking about search problem to find solution

A

It is a strategy of 3
Depth first
Bredth first
Uniform cost

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

What is world state

A

It includes all the details about the environment

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

What is the search state

A

Abstraction of world state , so keeps the needed details about the environment

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

What are the stuff we need to know when working with search state

A

States and their representation way , different environments will give us different state representation needs. For pac man it will be different than pathing problem.
Goals test what is it?
Actions PLANS
Successor function (what will it do to the state) what will it change?

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

What is in a state space

A

All possible states and their details, either world state or search state

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

What is a state space graph

A

Mathematical way to represent a search problem

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

What do nodes represent in a state space graph ?

A

States , abstracted world configuration

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

What do arcs (edges) represent

A

Successor (action resault)

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

Goals test in state space graph

A

Goal node/s to see if the solution is found

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

How many times does each state occur in the state space graph

A

Once

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

Can we build a full state space graph in memory?

A

No because it is too big but it is a useful idea

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

Compare trees and graphs

A

Tree no cycles
Tree start from node and end in leaf
Tree larger
Tree may have the same node twice but the parents must be different
Trees are hyrarcal

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

What does the root node represent in search tree

A

Start state

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

What do children represent in search tree

A

Successor states from actions

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

What do nodes in search tree correspond to?

A

States, but each one corresponds PLANS that helped achieve it

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

What is PLANS

A

Sequence of actions taken to reach from one node to another

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Why can’t we build the whole search tree (store in RAM)
Because the tree is very large and it grows exponentially meaning big oh is bad in worst case, so we try building parts of it
26
27
What is a search tree
Is a what if tree showing plans and their outcomes, used for search problems
28
29
What does each node represent in search tree in terms of state space graph
A full path from the start node in the graph
30
What happens when we reach goal state in search tree
We stop adding nodes to it from that goal node
31
How large is the search tree when we have a cyclic graph
Infinite because we can just keep looping before getting to the goals state and we will have a lot of repeated structure in the tree
32
When working with search tree we have 3 terms what are they
Expand out Fringe Exploration startegy
33
How to know which node is best to expand out
Using a strategy to help us reach the optimal solution
34
What is expansion
Adding all possible nodes to a current node will expand it out (what are the potential plans that can be taken from here)
35
What is fringe
Plans that are currently taken in consideration and stored in RAM
36
What happens when we make a fringe but did not reach us to the goals state
We destroy it slowly so that we start from another node to expand out and possibly reach a goal node from another plan
37
What is depth search first
Search problem strategy Uses stack to work LIFO Goes to deepest node first
38
For depth first search strategy talk about it’s properties
Complete ? Will it find a solution if it exists? Yes unless the solution is not there or the tree is infinite Optimal? Always find the optimal solution? No it finds the left most solution Time complexity ? Complex grows up exponentially O(b^m) Space complexity? Not very complex (linear complexity O(bm)
39
What are the Cartoons (bases) of DFS
b is the branching factor (how many nodes go out of each node) m is the depth (longest path from root to leaf) G node may be on various levels
40
How to find number of nodes in the whole tree when it is full
Each level is b to the power of m , then sum them
41
How to know the fringe contents
Whatever is in the data structure is in the fringe, the fringe has stuff stored in the RAM
42
What is BSF
It is an uninformed search strategy that uses queue as data structure for its fringe, and it does not go deeply it goes side ways. (Shallow levels) It starts from left to right unlike DFS that goes from right to left.
43
Is BFS complete?
Yes, it will eventually give us the solution, if the tree is not infinite and we have a goal state .
44
Is BFS optimal
It is optimal only when the costs are equal for all arcs. When they are not it may not be, it may find the first solution in the tree but it is not necessary to be optimal
45
Does DFS and BFS worry about the cost?
No
46
How much space, and how much time does BFS take
BFS time and space depend on which tier or level it stops on. (Shallowest solution) Assuming that s is the tier it stopped on then both time and space will be o(b^s)
47
What nodes does DFS and BFS expand
DFS nodes on left prefix BFS all nodes above the shallowest solution Both could process the whole tree
48
When does BFS out perform DFS and the opposite
When the goal is in the shallowest levels, then BFS when the goal is in the deepest levels then DFS
49
Explain the time and space for BFS and DFS
Space is what is stored in the fringe, number of nodes. so for DFS some siblings on the path. For time is how many nodes were searched , and using sum in series rule it will give us the answers. For time you need b to the power of depth in all of the uninformed search methods. For space it differs
50
What is iterative deepening
It is a search problem algorithm that uses DFS space advantage with BFS since BFS takes a lot of space. The idea is you run DFS on parts of the tree, smaller levels, until you find a goal state. It is a good strategy because most work happens in the lower levels (where the number of nodes is large), so if you find a solution in the upper levels then you will be find . Uses stack as data structure
51
Is iterative deepening better than DFS and BFS ? How?
Yes, by space, it will take the same is DFS o(bs) And for time it will take o(b^s)
52
Is iterative deepening optimal? Is it complete?
It is complete if the tee is not finite and there is a goal state It is optimal only when the cost of arcs are the same
53
What is cost-sensitive search?
It is the search that takes cost in consideration, the only one that does it is uniform cost search,BFS will find shortest path in terms of number of actions, (arcs). And DFS will not find the shortest either way
54
What is uniform cost search
It is an uninformed search algorithm, that takes cost of actions in consideration. It uses priority queue as the data structure. It expands out the node with the least backward cost.
55
What is backward cost
It is the cumulative cost, from start node until we reach the current node.
56
Describe the movement of expanding the nodes for each type of uninformed search algorithms
DFS goes deep BFS shallow UCS random
57
For UCS what are the nodes expanded out?
The nodes that have backwards cost less that the cheapest solution
58
Explain the time and space complexity in UCS
It does not consider tiers in consideration and it moves randomly, so we will assume that the over all solution cost is c* and the cost of each arc or actions, (ɛ) the effective depth will be (c*/ɛ), so time will be b^of depth For space worst case will be the same
59
Is time and space for UCS good
They are bad because they grow exponentially, like BFS, we have a lot of stuff left out in the fringe that were not expanded out
60
Is UCS complete? Is it optimal?
Yes for both. Complete as long as the tree in finite and the minimum cost is positive
61
What are the goods and bads in UCS
Good: optimal and complete Bad: explores in every direction and it is uninformed (don’t know time/ location of goals state) like others, so does not know about the goals state or what will the action takes do.
62
What does a node represent in the tree or graph
State with its information
63
Can UCS movement be like BFS ?
Yes when the arcs cost are the same, UCS will not go randomly and it will do shallow levels until it reaches solution.

AI (2 decks)

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