Artificial Intelligence Search Algorithms Quiz

Describes the starting point of a problem. It defines the initial conditions of the environment.

A function that maps a state to a set of possible actions and their resulting states. It represents the possible transitions from one state to another.

A criteria used to determine if a solution has been reached. This criteria can be explicit, like reaching a specific location, or implicit, like achieving a certain condition.

A measure of the cost of a solution. It can be the number of actions taken, the distance traveled, or any other relevant metric.

A sequence of actions that transforms the initial state into a goal state. This path fulfills the problem's objectives.

A simplified version of a real-world problem, designed to illustrate problem-solving techniques and compare performance of different algorithms. It's often used in research and development

A problem derived from a real-world situation. It has practical applications and people care about finding its solutions.

A simple example of problem solving using a virtual environment. It involves cleaning up dirt in a two-location space, illustrating the concept of problem solving using states, actions, and goal tests.

A problem where the agent lacks any sensory information (e.g., location, object states). The agent must act blindly, and a solution is a predetermined sequence of actions.

A problem where the environment's state is partially known, or actions have uncertain outcomes. Solutions are designed to handle different possibilities, often involving conditional actions depending on sensory information.

A specific type of contingency problem where the uncertainty is introduced by the actions of another agent (like an opponent in a game).

A problem where the agent has no prior knowledge of the environment's layout, actions, or states. The agent must explore and learn as it goes.

A representation of an agent's belief about the possible states of the environment based on available information.

A sequence of actions pre-determined to achieve a goal in a sensorless problem, without adapting to sensory feedback.

A plan in a contingency problem represented as a tree or a policy, branching based on sensory information and actions.

The problem of adapting actions based on new information, especially in contingency problems, often requiring interleaving search and execution.

A search strategy that explores the search tree level by level, starting with the root node and expanding all nodes at a given depth before moving to the next level. It is complete for finite search spaces and optimal for cases where the path cost is a function of the depth of the goal node.

A search strategy that explores the search tree by expanding the most promising node first, typically based on a heuristic function that estimates the distance to the goal. It is not complete or optimal but can be very efficient for finding a solution quickly.

A search strategy that explores the search tree by expanding the node with the lowest estimated total cost, which combines the path cost so far with the heuristic estimate of the remaining cost to the goal. It is complete and optimal for admissible heuristics (that never overestimate the actual cost to the goal).

A search strategy that explores the search tree depth-first but with a predetermined depth limit. It stops exploring a branch if it reaches the depth limit. It is not complete but can be more efficient than depth-first search for problems with large depth.

A search strategy that combines depth-first search with gradually increasing depth limits. It starts with a small depth limit and repeatedly increases it until a solution is found. It is complete, optimal for uniform cost problems, and generally more efficient than depth-first search for large depth problems.

A search strategy that explores the search tree by backtracking from a goal node to the initial state. It is typically used for problems where the goal state is known in advance and the focus is on finding a path to the goal.

A search strategy that explores the search tree by using a heuristic function to guide the search. It is not complete or optimal but can be very efficient for finding a solution quickly. It can explore multiple promising paths simultaneously.

A search strategy that explores the search tree by maintaining a set of nodes to be explored, called an open list, and a set of nodes that have been explored, called a closed list. It expands the most promising node from the open list and adds its unexplored children to the open list. It avoids revisiting previously explored nodes.

A type of hill-climbing search where downhill moves can be taken. The probability of accepting a downhill move decreases exponentially with the cost of the move, allowing the algorithm to escape local maxima. It was employed extensively in solving VLSI layout problems in the early 1980s.

A search algorithm used to find optimal solutions in a state space. In this method, the current state is replaced with a successor with a higher evaluation function value. It is guaranteed to be incomplete as it could get stuck in local maxima.

A search algorithm where a descendant state is created by mixing two parent states. Each state is a string of characters, usually 0s and 1s, and the population of states starts with k randomly generated ones.

A type of hill-climbing search where a successor state is chosen randomly and the selection probability is influenced by the steepness of the uphill move, meaning better moves are more likely to be chosen.

A type of hill-climbing search where successors are generated randomly until an improved state is found. This method is known for its simplicity and efficiency.

A method to overcome the local maximum problem in hill-climbing. It starts multiple searches from random states to increase the chance of finding the global maximum.

A random-walk search algorithm that is complete, meaning it guarantees finding a solution if one exists, but is very inefficient.

A search algorithm where an initial set of candidate solutions are randomly generated and then through a series of steps like selecting, evaluating, and recombining, a better solution is iteratively created.

A point in the search space that is higher than all neighboring points, but lower than the global maximum. Hill-climbing algorithms can get stuck here, unable to reach the optimal solution.

A sequence of local maxima, forming a 'ridge' in the search space. Hill-climbing algorithms struggle to traverse these ridges, as they get trapped at each local peak.

A flat area in the search space where the evaluation function doesn't change. This can be a flat local maximum, preventing further progress, or a 'shoulder', where moving in a specific direction might lead to a better solution.

A search algorithm that continually moves in the direction of increasing value, aiming to reach a 'peak' where no neighbor has a higher value. It's a simple and common technique.

A greedy algorithm that focuses on choosing the best neighboring state without considering the future consequences. It often leads to good solutions but is prone to getting stuck at local maxima.

The current state in the search process, representing the current position or configuration in the problem space.

A function that evaluates the quality of a state. It measures how good a particular state is, often measured as distance to the goal or cost of reaching it.

The best neighboring state to the current state, offering the highest value or the lowest cost according to the evaluation function. This is the state selected for the next step in the hill-climbing process.

A pruning technique for searching tree-structured game spaces, such as those in chess or checkers, where the goal is to find the optimal move for the current player.

The best possible score that the maximizing player (MAX) can guarantee, given the current state of the game.

The best possible score that the minimizing player (MIN) can guarantee, given the current state of the game.

When the alpha value is greater than or equal to the beta value, it means that the current branch of the search tree can be ignored because there's no way it can lead to a better outcome than what's already known.

The initial value of alpha is set to negative infinity (-∞), representing the worst possible outcome for the maximizing player.

The initial value of beta is set to positive infinity (+∞), representing the worst possible outcome for the minimizing player.

The algorithm starts by exploring the first possible move from the current state, and then recursively explores the resulting branches of the search tree, pruning branches that don't improve the current best score.

The algorithm continues to prune branches until it reaches a terminal node (leaf) of the search tree or until the pruning condition is met. The best move for the current player is then selected from the remaining un-pruned branches.