Explore
Login
Register
/
Untitled
Clone
Register
Report Bug
Untitled
View
Untitled Deck
Study
Week 2: Blind and heuristic searches
Techniques used in search algorithms to find solutions efficiently.
Heuristic
A technique used to cut down the running time of a search algorithm by evaluating a state to determine if it is close to the end goal.
Heuristic search
A search algorithm that uses heuristics to guide the search and constrain the search space. Also known as informed search.
Blind Search
A search algorithm that does not use any information about the problem, such as the goal state or the cost of actions.
Depth-First Search (DFS)
A blind search algorithm that explores the deepest branch first and uses a Last-In-First-Out (LIFO) approach.
Breadth-First Search (BFS)
A blind search algorithm that explores all neighboring nodes first before moving to the next level and uses a First-In-First-Out (FIFO) approach.
Lowest Cost First Search (LCFS)
A blind search algorithm where the edges are not of uniform cost and the lowest-cost path is chosen.
Dijkstra Algorithm
A blind search algorithm that finds the shortest path between two nodes in a graph with non-negative edge weights.
Best-First Search
A heuristic search algorithm that uses an evaluation function to determine the best next node to explore.
A* Search
A heuristic search algorithm that combines the lowest-cost search and the best-first search by considering the cost of the path done so far and the estimated cost to the goal.
Constraint Satisfaction Problems (CSPs)
Problems that involve finding solutions that satisfy a set of constraints.
Domain
The set of possible values that a variable can take in a CSP.
Hard Constraints
Constraints that must be satisfied in a CSP and specify legal combinations of values for variables.
Soft Constraints
Constraints in a CSP that have a cost associated with each assignment of a value to a variable.
Optimization
The process of finding the best solution among a set of feasible solutions in a CSP.
Constrained Optimization Problem
A problem that involves satisfying a set of hard constraints while trying to optimize a cost function.
Knapsack Problem
A problem where there is a knapsack of capacity M and N items with weight and cost. The goal is to select items to maximize the total cost while not exceeding the knapsack capacity.
Traveling Salesman Problem (TSP)
A problem where the goal is to find the shortest possible route that visits all cities and returns to the starting city.
Sudoku
A puzzle that involves filling a 9x9 grid with numbers so that each column, each row, and each of the nine 3x3 subgrids contain all of the numbers from 1 to 9.
Greedy Search
A search algorithm that makes locally optimal choices at each step based on a strategy or heuristic. It may not lead to the globally optimal solution.
Randomized Search
A search algorithm that introduces randomness in the search process, such as random restart, random step, or random modification.
Simulated Annealing
A randomized search algorithm that uses a cooling schedule to gradually reduce the probability of accepting worse solutions.
Genetic Algorithm
A population-based algorithm that explores multiple solutions in parallel, mimicking the process of natural selection and evolution.
Constraint Propagation
A technique used in CSPs to reduce the search space by reasoning about the constraints and propagating the effects of variable assignments.
Generate and Test
A problem-solving strategy that generates possible solutions and tests them against a set of constraints or criteria.
Adversarial Searches
Search algorithms used in competitive environments, where multiple agents have opposite goals and try to outsmart each other.
Minimax
An adversarial search algorithm that considers all possible outcomes of a game and chooses the move that minimizes the maximum possible gain for the opponent.
Alpha-Beta Pruning
An optimization technique used in adversarial search algorithms to reduce the number of nodes evaluated by eliminating branches that are guaranteed to be worse than other branches.
Expectimax
A search algorithm used in games where there is an element of chance or uncertainty. It calculates the expected utility of each move instead of assuming the most optimal outcome.
Expectiminimax
A search algorithm that combines elements of minimax and expectimax algorithms to handle games with both deterministic and chance moves.
