Uninformed Search Problems Flashcards
What are the two types of search algorithms?
> Uninformed search: Each State has no additional information
Informed search: Each state has some information about how far the goal state could be
What is a search tree? Why is it called a tree? How is it given?
> It is a route for all the posible solutions
It starts at the root node and terminates at the leaf nodes
It is not explicitly given but is worked out as the search develops
What is a state?
> This is a representation of a physical configuration
> e.g. A city on a train map
What is a node? What does it represent and what information does it include?
> This is a data structure constituting part of a search tree
It includes the parent node, the children nodes, the depth
It represents a state. A state ≠ node
Why does a state ≠ node?
Because multiple nodes might represent the same state.
Each node representing the same state will have a different path / depth etc
What is the initial state?
this is the state that the problem starts at
What is the goal state?
This is the state that the problem is aiming to get towards
How can we analyse a problem into a search probelm?
> Conceptualise possible solutions and intermediate stages towards a solution
Identify the inital state
Identify the goal states
Possible actions: Identify transitions that allow a state to be transformed into other successor states
Devise an alorithm that will systematically search through possible paths from the inital state in order to find a path that ends in a goal
What is a path cost?
This is the sum of all costs asiated with transitioning between states (between nodes).
What is the fringe array?
This is a queue of all nodes that have been found but not processed
What is the explored array?
This is a collection of all the processed nodes
What are 2 main types of uninformed search?
> Breadth-frist search
> Depth-first search
What is breadth-first search?
This is where you always search the node with the smallest depth
[Picture1]
How is breadth-first search done?
> This is achieved with a First-in-first-out (FIFO) queue.
> The earliest node to be found and added to the fringe is the next one to be explored
How is a node removed from the fringe?
After it has been explored, it will be removed from the queue and added to the explored array.
How does a FIFO queue cause the search to be breadth first?
Because the nodes with the smallest depth are explored first before the deeper nodes as they are descovered first
What is depth-first search?
This is where you always search the node with the greatest depth
[Picture2]
How is depth-frist search done?
> This is achieved with a Last-in-first-out (LIFO) queue.
> The most recent node to be found and added to the fringe is the next one to be explored
How is a node removed from the fringe?
After it has been explored, it will be removed from the queue and added to the explored array.
How does a LIFO queue cause the search to be breadth first?
The nodes with the greatest depth are explored first before the deeper nodes as they are discovered most recently
What is the general procedure for an uninformed tree search?
[FUNCTION TREE_SEARCH] fringe += initial_state [LOOP] > IF fringe IS empty RETURN failure > node_test = fringe[LIFO/FIFO] > fringe.remove(node_test) > IF node_test == goal_state RETURN node_test > fringe += node_test.children
What is loop testing?
> This essentially adds a new array of all states that have been checked already.
Before a node is added to the fringe, it is checked to see if that state it already represents has been checked or not. This prevents loop issues
What is the general procedure for an uninformed tree search with loop checking?
[FUNCTION TREE_SEARCH] fringe[] += initial_state [LOOP] > IF fringe[] IS empty RETURN failure > node_test = fringe[LIFO/FIFO] > fringe.remove(node_test) > IF node_test == goal_state RETURN node_test > explored[] += node_test > add_fringe = Unexplored(node_test.children) > fringe[] += add_fringe
What are methods of evaluating a search strategy?
> Completeness: Does it always find a solution (if one exists)
Time complexity: The number of nodes traversed until a goal
Space complexity: Largest number of nodes the fringe can store
Optimally: Does it always find the least-cost solution
How can time and space complexity be measured?
b = Maximum branching factor of the search tree d = depth of the least cost solution m = maximum depth of the state space (may be ∞)
Evaluate breadth-first search
> Completenes: Yes (if b (branching factor) is finite)
Time = 1 + b + b^2 + … + b^d = O(b^d)
Space = O(b^(d+1))
Optimal: Yes (if cost = q per step), but not optimal in general
Evaluate depth-first search
> Completness: No, fails in infinite-depth spaces
Time = O(b^m)
Space = O(bm) linear space
Optimal: No
