Search Flashcards
Defining a state space
When solving a problem, we start by defining what each “state” looks like and how states transition from one to another. Each state represents a possible configuration of the problem at a particular point in time. Basically the set of all possible configurations.
Pruning strategies
Systematically eliminate certain states from consideration to reduce search space and improve efficiency
Search strategies
Strategies for deciding how to explore the state space. Different strategies determine the order in which states are considered
Navigating the Frontier
In search algorithms, the “frontier” is the set of states that are ready to be explored next. For ex. BFS, states are explored layer by layer, while DFS, states are explored by diving deep into one path before backtracking
Search Heuristics
guide the search process by estimating how close a given state is to the goal. Heuristics help the search algorithm to be more efficient
Completeness
Will the search always find a solution of a solution exits
Optimality
Will the search always fin the least cost solution if actions have cost
Time Complexity
What is the maximum number of nodes that can be expanded or generated
Space Complexity
What is the maximum number of nodes that have to be stored in memory
Uninformed Search strategies
-Adopt a fixed fule for choosing the next state to be expanded.
- They don’t take into account any domain specific information about a specific search problem
- Ex. BFS, uniform-cost, DFS
Uniform Cost search
BFS but frontier is sorted in increasing cost of the path. It always expands the least cost node
Dept limited search
DFS but to a pre-specified depth limit L. No node over L steps is on the frontier.
This eliminates infinite length paths problem
Iterative deepening search
Dept limit search but starting at depth limit L=0 and iteratively increase the depth limit, doing a DLS for each depth limit
Cycle Checking/ Path checking
Ensure that the state c is not equal to the state reached by any ancestor of c along this path
merit of a frontier node
A measure that helps decide the order in which nodes should be expanded
- “Cost of solution” notion of merit
Greedy best-first search
Greedily trying to achieve a low cost solution
h(n)
heuristic estimate of the cost of getting to a goal node from n
- it is always an underestimates of the true cost
A* search
Always expand the node with lowest f-value on the frontier
f(n)= g(n) + h(n)
g(n) is the cost of the path to node n
h(n) is the heuristic estimate of the cost of getting to a goal node from n
Monotone consistent Heuristic
h(n1) <= c(n1->n2) + h(n2)
c(n1->n2) is the actual of the step from n1 to n2
-Monotonicity implies admissibility
Local Search
This algorithm operate using a single Current State and generally move to neighbours of that state
Why search
Successful: in game playing, and other AI problems can be solved
Practical: Useful in approximation
What search show
Search only shows how to solve the problem once we have it correctly formulated
TreeSearch
TreeSearch(Frontier, Successors, Goal?)
BFS time complexity
O(b^(d+1)
Admissibility
idea of h(n) understating the true cost
h(n) <= h*(n)
Suduko_bruteforce
?- game(easy, Ls), solve(Ls).
Looks for the possible choices for each slot, then uses the first choice, then back tracks
- only one solution
Sudoku_forward
Removing choices. If the guess does not conflict with the guesses for previous cells, it advances(forwarded)
Sudoku_dynamic
Chooses the choices with fewer choices available
This is pruning
World_path
Changes one letter at a time to go from start word to finish word. word_path(horse, mouse, Ps).
Ps= [horse, morse, mouse] ;
ps=[horse, morse, moise, mouse];
ps=[horse, morse, moise, moose, mouse];
Ps=[horse, morse, moose, mouse];
Pigeon-hole: Heuristics_Sudoku(Forcing a choice
For all slots in a group with slot S except for S are marked are not possible for X. Therefore, slot S must be X.
Imagine you have several places to put a number, but all spots except one are already ruled out for that number.
The only spot left must then hold that number because there are no other options.
Eliminating Choices
In/Out:
The main idea: If a number can’t go anywhere else in the “Out” group, it must go in a shared slot, meaning Slot S can’t be that number. Slot S is in one group not the other
exact Cover: If a group of slots will cover certain numbers exactly, then Slot S can’t use those numbers.
Word_trail
Swapping two letters or change one letter
swap_letters_in_world(barber, W).
First letter swapped with second letter, first letter swapped with third letter…..
second letter swapped with third letter…
word_trail(Cat, dog, Trail).
Trail= [cat, cot, dot, dog]
bagof(W, swap_letter_in_word(barber,W), Ws)
Ws= list of all swaps
bagof(W, swap_letter_in_word(barber,W), Ws), length(Ws, L)
output length
