Artificial Intelligence: Search Algorithms and Knowledge Representation

Vocabulary flashcards covering fundamental search algorithms (uninformed, heuristic, and adversarial game search), computational complexity, data structures, and knowledge representation methods including propositional and predicate logic.

Search (State Space Search)

The fundamental problem-solving process of systematically finding a path or sequence of actions from an initial state (초기 상태) to a goal state (목표 상태) within a state space.

Blind Search (Uninformed Search)

A search approach that explores states systematically according to predetermined rules without using additional heuristic information about the remaining distance to the goal.

Depth-First Search (DFS)

An uninformed search method that starts at the root node and explores as deeply as possible along a single branch before backtracking.

Backtracking

The procedure in tree search where the search retreats to the previous branching point (parent node) to explore alternative paths when no further exploration can be made along the current path.

Depth Limit

A predefined threshold placed on the maximum search depth in depth-first search to prevent the algorithm from searching unnecessarily deep into paths that do not contain a solution.

Stack

A Last In First Out ($\text{LIFO}$) linear data structure utilized by depth-first search (DFS) where the most recently added state is retrieved and expanded first.

Open List

A list in search algorithms that stores candidate states or nodes that have been generated but have not yet been explored or visited.

Closed List

A list in search algorithms that stores nodes or states that have already been visited and completely expanded.

Breadth-First Search (BFS)

An uninformed search algorithm that starts at the root node and systematically explores all nodes at the current depth (level) before moving down to nodes at the next depth level.

Queue

A First In First Out ($\text{FIFO}$) linear data structure utilized by breadth-first search (BFS) where new states are added to the back and the oldest states are dequeued from the front first.

Traveling Salesman Problem (TSP)

The problem of finding the shortest route that starts from a given city, visits every other city exactly once, and returns to the origin city; for $N$ cities, the number of possible routes is $(N-1)!$.

Heuristic Search (Informed Search)

A search strategy that utilizes an evaluation function based on domain experience or heuristics to estimate node promise and reach a practical solution more efficiently.

Evaluation Function

A function that estimates how promising a node is toward reaching the goal state, typically calculated based on remaining cost, distance, or time.

Hill-Climbing Algorithm

A local search algorithm that evaluates only immediate neighboring nodes of the current state and iteratively moves to the neighbor with the best evaluation function value.

Local Maximum

A state in local search that has a higher evaluation value than all of its immediate neighbors but is lower than the global maximum, causing greedy algorithms like hill climbing to stall.

Best-First Search

A heuristic search algorithm that manages candidate nodes in a priority queue and always selects the most promising open node based on an evaluation function.

A* Algorithm

An optimal pathfinding algorithm that selects nodes by minimizing $f(n) = g(n) + h(n)$, where $g(n)$ is the actual path cost from the start to node $n$ and $h(n)$ is the estimated cost from $n$ to the goal.

Game Search

A search technique that uses a game tree to explore possible moves and determine optimal strategies while accounting for alternating choices made by an opponent.

Minimax Algorithm

A decision-making algorithm for two-player zero-sum games where the player ($\text{MAX}$) selects moves that maximize the score while assuming the opponent ($\text{MIN}$) selects moves that minimize the score.

Alpha-Beta Pruning

An optimization for the minimax algorithm that cuts off branches that cannot affect the final outcome whenever $\alpha \ge \beta$, significantly reducing the number of nodes evaluated.

Alpha ($\alpha$)

In alpha-beta pruning, the best (maximum) value that the $\text{MAX}$ player has secured along the path so far, initialized at the root to $-\infty$.

Beta ($\beta$)

In alpha-beta pruning, the best (minimum) value that the $\text{MIN}$ player has secured along the path so far, initialized at the root to $\infty$.

Alpha-Cut ($\alpha$-Cut)

A pruning event occurring at a $\text{MIN}$ node when its current $\beta$ value becomes less than or equal to $\alpha$ ($\alpha \ge \beta$), halting further search of that node's remaining children.

Beta-Cut ($\beta$-Cut)

A pruning event occurring at a $\text{MAX}$ node when its current $\alpha$ value becomes greater than or equal to $\beta$ ($\alpha \ge \beta$), halting further search of that node's remaining children.

Data

Raw, unprocessed facts collected from the real world that lack assigned context and may contain errors or noise.

Information

Data that has been processed, organized, and endowed with meaning for a specific purpose so that its significance is clear.

Knowledge

Information that has been systematically structured and generalized into patterns, relationships, or rules to support problem solving and decision making.

Wisdom

The contextual and practical application of knowledge that results in insightful judgment and effective action.

Knowledge Bottleneck

A limitation in classical expert systems where expanding system knowledge is constrained because humans must manually formulate and input every fact and rule.

Symbol Grounding Problem

The fundamental dilemma in artificial intelligence where internal symbols manipulated by knowledge representation systems lack direct physical connection to the real-world objects or concepts they denote.

IF-THEN Rule

A standard knowledge representation format structured as $\text{IF (Condition)} \rightarrow \text{THEN (Conclusion/Action)}$ used to encode procedural knowledge and conditional logic.

Propositional Logic

A logical system where declarative statements are treated as atomic units, each assigned an absolute truth value of either True ($T$) or False ($F$).

Vacuous Truth

A condition in propositional logic where an implication $p \rightarrow q$ evaluates to True ($T$) simply because the antecedent $p$ is False ($F$), regardless of the truth value of the consequent $q$.

Modus Ponens

A deductive inference rule stating that if $A \rightarrow B$ is true and $A$ is true, then the conclusion $B$ must also be true.

Modus Tollens

A deductive inference rule stating that if $A \rightarrow B$ is true and $\sim B$ is true, then the conclusion $\sim A$ must also be true.

Hypothetical Syllogism

A deductive inference rule stating that if $A \rightarrow B$ is true and $B \rightarrow C$ is true, then the transitively derived statement $A \rightarrow C$ is also true.

Predicate Logic

An expressive logic system that decomposes statements into objects (terms) and predicates (properties or relationships) and supports variables and quantifiers.

Universal Quantifier ($\forall$)

A logical quantifier denoting 'for all' or 'every', indicating that a stated condition holds true for every member within the defined domain of discourse.

Existential Quantifier ($\exists$)

A logical quantifier denoting 'there exists at least one', asserting that a specified condition holds true for at least one entity within the domain of discourse.