Introduction to AI Search Methods

The current state's probability depends only on a fixed number of previous states.

A sequence of random variables where each variable follows the Markov assumption.

A Markov model where the state is hidden, but we can observe its effects.

The evidence (observation) depends only on the current state.

The degree of belief in a proposition without any additional evidence.

Calculating the probability of the CURRENT state based on past observations.

Calculating the probability of a FUTURE state based on past observations.

The degree of belief in a proposition given some existing evidence.

The probability of event 'a' occurring given that event 'b' has already occurred.

Calculating the probability of a PAST state based on current observations.

A variable in probability theory with a set of possible values it can take on.

Choosing the best option from a set of possibilities.

Two events are independent if the occurrence of one does not affect the probability of the other.

The probability of both event 'a' and event 'b' occurring is equal to the product of their individual probabilities if they are independent.

The likelihood of multiple events happening simultaneously.

A formula used to calculate conditional probability, particularly when you have prior knowledge.

A recursive function in the Minimax algorithm that calculates the maximum expected utility for the current player, assuming optimal play by both players.

A recursive function in the Minimax algorithm that calculates the minimum expected utility for the opponent, assuming optimal play by both players.

An optimization technique for the Minimax algorithm that eliminates unnecessary recursive computations by identifying and pruning branches of the game tree that cannot affect the optimal decision.

A description of how every possible action in a given state changes the game world, resulting in a new state.

The collection of all possible states reachable from the initial state of a game or system through any sequence of actions.

An agent that makes decisions by reasoning based on internal knowledge representations.

A formal system for representing knowledge using sentences that can be either true or false, but not both.

A relationship between two sentences where one sentence logically follows from the other, meaning that if the first sentence is true, the second sentence must also be true.

A state in a search space that's directly adjacent to the current state. It's usually similar in value to the current state.

A local search algorithm that iteratively moves to the best neighbor state. It aims to find the highest-valued state in the search space.

A function used to evaluate the quality of a state. It assigns a numerical value to each state, where higher values are generally considered better.

A state that has a higher value than all its neighboring states, but not necessarily the highest overall in the entire search space.

A state with the highest value of all states in the entire search space.

A variation of hill climbing where the algorithm always chooses the neighbor state with the highest value.

A hill climbing algorithm that chooses a neighbor state randomly from the higher-valued neighbors. This prevents getting stuck in local maxima by exploring other paths.

A hill climbing algorithm that chooses the first neighbor state it encounters that has a higher value than the current state. It stops searching after finding one better neighbor.

A constraint that involves only one variable. It's like checking if a single box in a puzzle fits its space.

A constraint that involves two variables, ensuring they satisfy a specific relationship. Imagine two puzzle pieces connecting in a specific way.

When all values in a variable's domain satisfy its unary constraints, ensuring each value individually fits the variable's requirements.

When all values in a variable's domain satisfy its binary constraints with neighboring variables. Imagine checking if every value in a row of a Sudoku puzzle works with the adjacent rows.

An algorithm that enforces arc consistency on the entire constraint satisfaction problem. It checks and adjusts variable domains iteratively.

A problem where you need to find values for variables that satisfy given constraints, like solving a Sudoku puzzle or scheduling classes.

A recursive search strategy for solving CSPs. It tries to assign values one by one, and backtracks if a conflict occurs.

In a CSP, the transition model describes how assigning a value to a variable changes the state of the problem. It's like seeing what happens after you place a puzzle piece.

An optimization algorithm that allows for occasional moves to worse states to escape local maxima and find a better global minimum. It uses a temperature parameter that gradually decreases, reducing the probability of accepting worse states over time.

A classic optimization problem where a salesperson needs to visit a set of cities exactly once and return to the starting city, minimizing the total distance traveled.

A mathematical technique for optimizing a linear function (cost function) subject to linear constraints. It involves finding the best values for variables that satisfy the constraints.

A constraint that indicates a preference for certain solutions over others, but doesn't make a solution invalid if it's not met. It influences the quality of the solution.