CHAP 3 : Search Techniques (uninformed) Flashcards
What is the definition of search?
It is the process of looking for a sequence of actions that reaches the goal.
What are inputs in problem formulation? [6]
- State space
- all possible combinations of states in the end, set of all possible configurations of a system - Action space
- Successor function
- a description of possible actions, a set of operators.
- for state x, returns s(x) –> Given a state, generates its sucessor states - Start state
- Goal test (aka goal state)
- Path cost
- A function that assigns a numeric value to each path.
What is a state?
A representation of physical state
What is a node
A data structure that is part of a search tree
What is a branching factor?
What is the branching factor of the search trees given in the slides?
- The branching factor is the number of children at each node.
- The search trees in the slides have a branching factor of 2. (Binary tree)
What are the parts of a search tree? [3]
- Root (parent) node
- Child nodes
- Edges –> representing the action and costs
What is the output of a search problem?
The output is the sequence of actions that reaches the goal state from the current state.
Predicting the sales price of an HDB flat is considered a search technique. Is the statement True or False?
False
The maximum number of elements in an action space is one. Is the statement true or false?
False
Goal test finds if a state is goal state or not a goal state. Is the statement true or false?
True
Search Trees are data structures that are used to represent the search problem. Is the statement true or false?
True
When planning a route for a robot, it is possible to build a search tree to find the most optimal routes. Is the statement true or false?
True
What the definition of a frontier in a search tree?
It is the set of unexplored child nodes that is to be expanded
What kind of data strucutres may be used for the frontier and how do they work?
- Queue – FIFO
- Stack – LIFO
- Priority queue – nodes expanded following a priority function that is set between the nodes
What is the definition of the explored set?
It is the set of leaf nodes that are already explored
What does the explored set do in a search tree?
It saves unique instances of the states from the search tree.
The explored set needs to provide fast insertion and searching. True or False?
True
What is a search strategy?
It is the order of picking a node for expansion
What are the criteria that strategies are evaluated based on? Give the definitions too
- Completeness : guarantee of finding a solution
- Optimality : guarantee of finding an optimal solution
- Time complexity : time spent to find a solution
- Space complexity : memory space needed to perform the search.
What is the main difference between uninformed search techniques and informed search techniques?
Uninformed search techiques use only the info that is avail in the problem definition, and have no additional info about the states and cannot distinguish which non-goal state is better. They blindly try all possible ways to reach the target.
However, informed search techniques can tell which non-goal state is better, given some guidance
What is the idea behind the breadth first search and how is it implemented (frontier)?
Idea : Expand shallowest unexpanded node.
Implementation : Frontier is a FIFO queue, i.e. insert new successors at the end
Evaluate breadth first search based on completeness, optimality, space and time complexity.
- Completeness : BFS is complete, IF BRANCHING FACTOR IS FINITE
- Optimality : Optimal, IF STEP COST = 1
- Space complexity : increases exponentially
- Time complexity : time taken increases as depth of tree increases
Space is a bigger problem than time
Uniform cost search is an extension of the breadth first search. True or False?
True. Uniform cost search is weighted breadth first search
Evaluate the uniform cost search
(compare time and space w BFS)
- Complete : Yes, if all state’s actions have non-negative values
- Optimal : Yes. Uniform-cost search expands nodes in order of their optimal path cost.
- Time and space : Performs worse than BFS — list is required to be kept and sorted as priorities in queue, store step costs etc.
What is the idea of depth first search? How is it implemented?
Idea : It expands the deepest unexpanded node
Implementation: Frontier –> LIFO stack, insert successors at the front
Evaluate the depth first search technique
- Completeness : Yes, if state space is FINITE with no repeated states and path
- Optimal : No, may find a solution at a deep level while a more optimal solution exists at a shallow level to the right side of the tree (bc always expand left first)
What are the characteristics of backtracking? [4]
- Only one successor is generated at a time
- Each partially expanded node remebers which successor to generate next
- Once a node has been expanded and al its descendants are fully explored, it can be removed from memor if goal state not found
- Uses recursion
What is recursion and when is it useful?
Recursion is a function calling itself and it is useful in solving problems that can broken down into smaller problems of the same kind
What are the sections involved in recursion?
- Base case
- Logic
- Recursive call
What are the sections involved in recursion?
- Base case
- Logic
- Recursive call
Breadth-first search is usually considered as complete (if branching factor=1) and optimal (step cost=1). Is the statement true or false?
True
Breadth-first search is usually considered as complete (if branching factor=1) and optimal (step cost=1). Is the statement true or false?
True
In Breadth-first search, memory space to store the nodes is usually the bigger problem than the computation time. Is the statement true or false?
True
UCS expands the node from the frontier with the cheapest path cost. Is the statement true or false?
True
UCS is always complete for any given search problem. Is the statement true or false?
False
- UCS is always optimal. Is the statement true or false?
True
The key difference between Breadth-first search and Depth-first search (DFS) is that the frontier for DFS operates using a FIFO order. Is the statement true or false?
False
DFS expands from the deepest unexpanded node. Is the statement true or false?
True
DFS is optimal. Is the statement true or false?
False
By using Backtracking only one successor node is generated at a time. This property of backtracking makes the search algorithm memory efficient. Is the statement true or false?
True
