02 Searching Flashcards
Searching
The search starts in an initial state. Then it iteratively explores the state space by selecting a state node and applying operators to generate successor nodes until it finds the goal state node or has to give up.
The choice of which node to expand at each level is determined by the search strategy
The part of the state space (defined by inital state and actions) that is explored is called the search tree
Formulation of a search problem
Initial state
Initial state of environment
Actions
Set of actions available to agent
Path
Sequence of actions leading from one state to another
Goal state
Test to check if a state is a goal state
Path cost
Function that assigns cost to a path
Solution
Path from initial state to a state that satisfies goal test
Problem-solving agents
Problem-solving agents are goal-based agents that use search to find action sequences
Tree search vs. graph search
The state space may contain loops (path back to earlier state) or redundant paths (more than one path between two states). Simple tree expansion will run infinitely or “explode” in such search spaces.
To avoid the problem, tree search can be replaced by generalized graph search. In graph search, the algorithm keeps track and avoids expanding already visited nodes.
Uninformed search strategies
Uninformed search has no information on path cost from current to goal states.
Breadth-firsth
Uniform-cost
Depth-first
Depth-limited
Iterative deepening
Bidirectional
The strategies differ by order in which nodes are expanded
Evaluation of search strategies
Completeness
Does the strategi always find a solution when there is one?
Optimality
Does it always find the best solution?
Time complexity
How long does it take to find a solution?
Space complexity
How much memory is needed?
Search tree data structures
Datatype node with components
– STATE - search space state corresponding to the node
– PARENT-NODE - node that generated this node
– ACTION - action that was applied to generate this node
– PATH-COST - cost of path from initial node (called g)
– DEPTH - number of nodes on path from initial node
Search tree nodes kept in a queue with operators
– MAKE-QUEUE(Elements) - create queue with given elements
– EMPTY?(Queue) - true if no more elements in queue
– FIRST(Queue) - returns first element of the queue
– REMOVE-FIRST(Queue) - removes and returns first element
– INSERT(Element, Queue) - inserts an element into queue
– INSERT-ALL(Elements, Queue) - inserts set of elements into queue
General tree-search algorithm
- frontier is an initially empty queue of a certain type (FIFO, etc.)
- SOLUTION returns sequence of actions back to root
- EXPAND generates all successors of a node
Breadth-first search
• FIFO - First In First Out (add nodes as last)
• Expands all nodes at a certain depth of search tree before expanding any node at next depth
• Exhaustive method - if there is a solution, breadth-first will find it (completeness)
• Will find the shortest solution first (optimal)
• All nodes on one level are explored before moving to next level
• Complexity: O(b^d) (exponential)
– b = branching factor
– d = depth(rootnode, d=0)
Uniform-cost search
The search begins at the root node. The search continues by visiting the next node which has the least total cost from the root. Nodes are visited in this manner until a goal state is reached.
Uniform-cost search is optimal since it always expands the node with the lowest cost so far. Completeness is guaranteed if all path costs > 0.
Depth-first search
Start at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.
LIFO-Last In First Out (add nodes as first). Always expands a node at deepest level of the tree, backtracks if it finds node with no successor. May never terminate if it goes down an infinite branch, even if there is a solution (not complete). May return an early found solution even if a better one exists (not optimal).
Worst case time complexity is O(b^m) for branching factor b and depth m. But depth-first may find solution much quicker if there are many solutions (m may be much larger than d - the depth of the shallowest solution).
Depth-limited search
Modifies depth-first search by imposing a cutoff on the maximum depth of a path. Avoids risk of non-terminating search down an infinite path. Finds a solution if it exists within cutoff limit (not generally complete). Not guaranteed to find shortest solution (not optimal). Time and space complexity as for depth-first
Iterative deepening search
Modifies depth-limited search by iteratively trying all possible depths as the cutoff limit. Combines benefits of depth-first and breadth-first. Time complexity is O(b^d), space complexity O(bd). Iterative deepening is the preferred (uninformed) search strategy when there is a large search space and the solution depth is unknown.
Bidirectional search
Searches simultaneously both forward from initial state and backward from goal state. Time complexity reduced from O(b^d) to O(b^{d/2}).
But. . . Does the node predecessor function exist? What if there are many possible goals? Must check a new node if it exists in other tree. Must keep at least one tree, space complexity O(b^{d/2}).
Evalution of uninformed search strategies (table)
