Blind Search Flashcards
What is an algorithm?
A method aiming to solve a problem given:
- A Problem
- Some requirements that the solution should meet
- The available resources
- Any time constraints, etc.
What are the characteristics of an ideal algorithm?
- Searches as little space as possible
- Uses as little memory as possible
- Takes as little time as possible
- Guarantees to find the solution
- Guarantees to find the best solution
- It is easy to implement
When is an algorithm exhaustive?
When it searches the whole search space in order to find a solution
When is an algorithm complete?
When it guarantees a solution if such a solution exists
When is an algorithm admissible?
When it guarantees to find the best solution if such a solution exists
What is the Open List (Frontier)?
It is the list of all unexpanded nodes
What is the Closed Set?
It is the set of all expanded nodes
It is used to check whether the algorithm has encountered a state at an earlier stage (loop check)
How does a search algorithm work?
- Start from the initial state
- Keep expanding the state one by one
- Keep track of the choices you make (which state to expand and which ones you left behind to expand later if required)
- Keep track of the states you passed already (so you don’t consider them later)
- End the process when you reach the goal state(s)
What information is needed to keep in a search algorithm?
- The current state
- A set of all states that are left behind for later, Frontier (Open Set)
- A set of all states that have been already passed, Closed Set
What information is required for a search algorithm to work?
- The initial State
- The set of actions and the expansion function
- The goal test function
How does the Depth First Search (DFS) work?
Generates the search space by expanding the deepest state first
What are the advantages and disadvantages of DFS?
Advantages:
- The open list is relatively small
- It is space-efficient
Disadvantages:
- It is not complete
- It is not admissible
- It is not efficient
How does Breadth First Search (BFS) work?
Generates the search space by expanding the shallowest state first
What are the advantages and disadvantages of BFS?
Advantages:
- It is complete
- It is admissible
Disadvantages:
- It is not space-efficient
- The open list is relatively big
What is Iterative Deepening?
It is a combination of DFS and BFS that searches using depth-first but up to a certain point. If no solution is found, the depth is increased
What are the advantages and disadvantages of ID?
Advantages:
- It is complete
- It is admissible
- The shortest path is found (if the depth is increased by one)
- The open list is relatively small
Disadvantages:
- It is not time-efficient
What is Bi-Directional search?
It is a search algorithm in which one thread starts searching from the initial state to the final state and one from the final state to the initial state in parallel.
What happens when the two threads of the Bi-Directions Search find a common state?
Then the search terminates and the two paths are combined to produce a solution
What are the pre-conditions of the Bi-Directional Search?
- Operators must be reversive
- The goal state must be known
What are the advantages and disadvantages of Bi-Directional Search?
Advantages:
- Exploits the ability for concurrent solution
Disadvantages:
- Each node must track the nodes that have visited, but also check if the current state belongs to the other thread’s closed set
What is the ideal result when operators have different cost applications?
The best solution with respect to a cost function
What is Uniform Cost Search?
It uses the BFS method but doesn’t start from the shallowest state but the one with the minimum partial cost
What are the advantages and disadvantages of UCS?
Advantages:
- It is complete
- It is admissible (when all operator costs are greater than zero)
Disadvantages:
- It is not space-efficient
What is Branch & Bound Search?
It prunes search paths that do not lead to the best solution
