Artificial Intelligence and Search Algorithms Flashcards

Flashcards covering heuristic search algorithms (Greedy Best-First, A*), AI foundations, classic and real-world problem formulations, and basic search strategies.

Heuristic Search

An AI search technique that employs a heuristic to make moves and reduce the number of alternatives from an exponential number to a polynomial number.

Heuristic

In a general sense, any piece of advice that is often effective but is not guaranteed to work in every case.

Heuristic Evaluation Function

A function, denoted as $f(n,g)$, that estimates the cost of an optimal path between a pair of states in a single-agent path-finding problem.

Best-First Search

An instance of the general TREE-SEARCH or GRAPH-SEARCH algorithm in which a node is selected for expansion based on an evaluation function, $f(n)$, expanding the node with the lowest evaluation first.

Heuristic Function $h(n)$

The estimated cost of the cheapest path from the state at node $n$ to a goal state.

Greedy Best-First Search

A search algorithm that tries to expand the node closest to the goal by evaluating nodes using only the heuristic function $f(n) = h(n)$.

Straight-Line Distance ($h_{SLD}$)

A heuristic function used in route-finding problems that estimates road distance between locations via direct Euclidean distance to the destination (e.g., $h_{SLD}(\text{In(Arad)}) = 366$).

Time and Space Complexity of Greedy Best-First Tree Search

In the worst-case tree version, both time and space complexity are $O(b^m)$, where $b$ is the branching factor and $m$ is the maximum depth of the search space.

Misplaced Tiles Heuristic

A heuristic function $h(x)$ for the 8-puzzle problem calculated by counting the number of tiles that are out of place relative to the goal state.

A* Search

A form of best-first search that evaluates nodes using $f(n) = g(n) + h(n)$, combining the path cost to reach the node and the estimated cost to reach the goal.

$g(n)$ in A* Search

The path cost from the start node to node $n$.

Evaluation Function $f(n)$ in A* Search

The estimated cost of the cheapest solution through node $n$, calculated as $f(n) = g(n) + h(n)$.

Completeness and Optimality of A* Search

Guaranteed properties of A* search provided that the heuristic function $h(n)$ satisfies specific conditions.

Artificial Intelligence (Russell and Norvig Definition)

The field that attempts not just to understand but also to build intelligent entities.

Artificial Intelligence (Rich and Knight Definition)

The study of how to make computers do things which, at the moment, people do better.

Artificial Intelligence (Winston Definition)

The study of the computations that make it possible to perceive, reason, and act.

Philosophy in AI Foundations

Addresses questions about formal rules for valid conclusions, how the mind arises from a physical brain, the origin of knowledge, and how knowledge leads to action.

Mathematics in AI Foundations

Addresses questions about formal rules to draw valid conclusions, what can be computed, and how to reason with uncertain information.

Economics in AI Foundations

Addresses how decisions should be made to maximize payoff, including scenarios where others may not cooperate or payoffs are far in the future.

Neuroscience in AI Foundations

Addresses the fundamental question of how biological brains process information.

Psychology in AI Foundations

Addresses how humans and animals think and act.

Computer Engineering in AI Foundations

Addresses how to build efficient computers to execute AI applications.

Control Theory and Cybernetics in AI Foundations

Addresses how artifacts can operate under their own control.

Linguistics in AI Foundations

Addresses how language relates to thought.

Mundane Tasks

Routine AI task domains including perception (vision, speech), natural language processing, commonsense reasoning, and robot control.

Formal Tasks

Systematic AI task domains including games (chess, backgammon, checkers, go) and mathematics (geometry, logic, integral calculus, proving properties of programs).

Expert Tasks

Skilled AI task domains requiring expert human knowledge, such as engineering design, medical diagnosis, scientific analysis, and financial analysis.

Properties of Knowledge in AI

Characteristics of knowledge: it is voluminous, hard to characterize accurately, constantly changing, and organized to match how it will be used.

AI Technique

A method exploiting knowledge represented such that it captures generalizations, is human-understandable, easily modified, usable in incomplete situations, and narrows search space.

8-Puzzle Problem

A classic problem consisting of a $3 \times 3$ board with eight numbered tiles and a blank space, where tiles slide into adjacent empty spaces to reach a specified goal state.

8-Queens Problem

A classic problem where the goal is to place eight queens on an $8 \times 8$ chessboard such that no queen attacks any other in the same row, column, or diagonal.

Water Jug Problem

A puzzle involving an unmarked 4-gallon jug, an unmarked 3-gallon jug, and a pump, requiring exactly 2 gallons of water in the 4-gallon jug.

Farmer, Fox, Goose, and Grain Problem

A puzzle where a farmer must ferry his fox, goose, and grain across a river one at a time without leaving the fox alone with the goose or the goose alone with the grain.

Missionaries and Cannibals Problem

A problem where three missionaries and three cannibals must cross a river using a boat carrying at most two people, without allowing cannibals to outnumber missionaries on either bank.

Route-Finding Algorithms

Algorithms used in real-world applications such as GPS driving directions, video stream routing in computer networks, military planning, and airline travel planning.

Simplified Map of Romania

A standard roadmap graph containing locations and driving distances between Romanian cities, used to demonstrate search algorithms.

Touring Problems

Search problems where the state space must include both the current location and the set of cities visited (e.g., visiting every city at least once and returning to the start).

Travelling Salesperson Problem (TSP)

A touring problem in which each city in a given map must be visited exactly once to find the shortest total tour length.

VLSI Layout Problem

An engineering optimization problem requiring placement of millions of components and connections on a microchip to minimize area, delays, and stray capacitance while maximizing yield.

Cell Layout (VLSI)

The phase in VLSI layout where primitive components are grouped into cells with fixed footprints and positioned on a chip without overlapping.

Channel Routing (VLSI)

The phase in VLSI layout that determines specific routing paths for connecting wires through the spaces between placed cells.

Robot Navigation Problem

A continuous-space generalization of route finding where a robot moves through continuous multi-dimensional states with infinite actions while dealing with sensor and control errors.

Initial State

The starting state from which an agent or search algorithm begins problem solving.

Transition Model

A formal description of what each action does, specified by the function $\text{RESULT}(s, a)$ that returns the state resulting from executing action $a$ in state $s$.

Path Cost Function

A function assigning a numeric cost to a path, measuring solution quality where an optimal solution has the lowest path cost.

State Space

The set of all states reachable from the initial state by any sequence of actions, implicitly defined by the initial state, actions, and transition model.

Expanded Node

A node in a search tree that has had all of its successor nodes generated.

Uninformed Search (Blind Search)

Search strategies that have no information about nodes beyond those already explored (e.g., Breadth-First Search, Depth-First Search).

Informed Search (Heuristic Search)

Search strategies that utilize problem-specific knowledge or heuristic evaluation functions to evaluate unexplored nodes (e.g., Best-First Search, A* Search).

Space Complexity of Breadth-First Search

A memory footprint of $O(b^d)$, where $b$ is the branching factor and $d$ is the depth of the shallowest goal node, making BFS severely space-bound in practice.