Ch 3 (uninformed search) Flashcards
What are the components of search problem
State space
Start state
Goal state
Successor function
Solution
What is the state space
The set of all possible states in the problem
What is a successor function
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
What is a start state ?
The state that we start the search from
What is the goal state
The state we want to reach
What is the goal test function
Function tests if the state is goal or not
What is a solution in search problem
Sequence of actions that take us from start to goal
How to know that a problem is search problem
When it has all the components
What are the strategies when talking about search problem to find solution
It is a strategy of 3
Depth first
Bredth first
Uniform cost
What is world state
It includes all the details about the environment
What is the search state
Abstraction of world state , so keeps the needed details about the environment
What are the stuff we need to know when working with search state
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?
What is in a state space
All possible states and their details, either world state or search state
What is a state space graph
Mathematical way to represent a search problem
What do nodes represent in a state space graph ?
States , abstracted world configuration
What do arcs (edges) represent
Successor (action resault)
Goals test in state space graph
Goal node/s to see if the solution is found
How many times does each state occur in the state space graph
Once
Can we build a full state space graph in memory?
No because it is too big but it is a useful idea
Compare trees and graphs
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
What does the root node represent in search tree
Start state
What do children represent in search tree
Successor states from actions
What do nodes in search tree correspond to?
States, but each one corresponds PLANS that helped achieve it
What is PLANS
Sequence of actions taken to reach from one node to another
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
What is a search tree
Is a what if tree showing plans and their outcomes, used for search problems
What does each node represent in search tree in terms of state space graph
A full path from the start node in the graph
What happens when we reach goal state in search tree
We stop adding nodes to it from that goal node
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
When working with search tree we have 3 terms what are they
Expand out
Fringe
Exploration startegy
How to know which node is best to expand out
Using a strategy to help us reach the optimal solution
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)
What is fringe
Plans that are currently taken in consideration and stored in RAM
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
What is depth search first
Search problem strategy
Uses stack to work LIFO
Goes to deepest node first
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)
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
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
How to know the fringe contents
Whatever is in the data structure is in the fringe, the fringe has stuff stored in the RAM
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.
Is BFS complete?
Yes, it will eventually give us the solution, if the tree is not infinite and we have a goal state .
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
Does DFS and BFS worry about the cost?
No
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)
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
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
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
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
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)
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
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
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.
What is backward cost
It is the cumulative cost, from start node until we reach the current node.
Describe the movement of expanding the nodes for each type of uninformed search algorithms
DFS goes deep
BFS shallow
UCS random
For UCS what are the nodes expanded out?
The nodes that have backwards cost less that the cheapest solution
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
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
Is UCS complete? Is it optimal?
Yes for both.
Complete as long as the tree in finite and the minimum cost is positive
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.
What does a node represent in the tree or graph
State with its information
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.
