A decision problem asks for one of two answers, conventionally encoded as zero and one. Equivalently, it asks whether an input belongs to a formal language.
A search problem asks for a witness satisfying a specified relation rather than only whether one exists.
A search problem whose states are words of fixed length, with a transition changing exactly one letter and requiring the resulting word to belong to a specified dictionary. Unit path costs make a shortest graph path a minimum-mutation solution. Hamming distance to the target is a consistent heuristic: one transition changes this distance by at most one. Dictionary restrictions may force a longer solution or make the target unreachable.
A state satisfying a problem's goal test. Whether its generation or its later selection terminates a search algorithm affects optimality for algorithms such as A-star search. A goal state's remaining optimal cost is zero, whereas its accumulated path cost need not be zero.
The sum of step costs along the action history represented by a search node. Positive costs give lower bounds on search depth, and the same physical state can have different path costs when reached along different histories. Uniform-cost search orders by accumulated cost; A-star search adds an estimate of remaining cost.
A step cost is the cost of one action or transition in a search problem. The accumulated path cost is the sum of the step costs along its action history. A uniform positive lower bound on step costs makes every bounded-cost action history have bounded search depth; positivity of each individual term alone does not establish such a bound.
Exploration of a game tree containing choices by competing decision makers. A maximizing node chooses the largest successor value; a minimizing opponent chooses the smallest. Known random outcomes instead require chance nodes and expected values, as in expectimax. A game tree representation can combine controlled choices and chance without assuming that chance maliciously chooses its worst outcome.
Backward induction on a finite game tree containing maximizing choices, minimizing choices and chance nodes. Terminal utilities are backed up by , and , respectively. Exact chance node evaluation generally needs every positive-probability outcome; ordinary alpha-beta pruning does not transfer unchanged because one child's value does not bound the full weighted sum.
A game tree evaluation rule using maxima at the controlled player’s decision nodes and expected values at chance nodes:respectively. Terminal utilities fix the boundary values. These rules exactly optimize a finite-horizon expected utility objective by backward induction. For cyclic infinite-horizon reachability problems, a finite Markov decision process formulation and value iteration replace naive expansion of an infinite game tree. Start with one at successful terminal states and zero elsewhere, keep terminal values fixed, and apply the maximizing/expectation backups repeatedly. The th iterate is the greatest success probability achievable within transitions, by backward induction. These values are nondecreasing and bounded by one. For every policy, eventual success is the increasing set union of success within finite horizons, so its probability is the limit of those finite-horizon probabilities. Taking the supremum over policies and horizons in either order proves that the iterates converge to the optimal eventual-success probability. The limiting fixed-point equations can also admit larger solutions, so the initialization from terminal-success indicators matters.
Two controlled walkers on the same connected undirected graph can each traverse one edge or wait in each unit-cost step. If they meet only by occupying the same vertex at the same time, their minimum meeting time iswhere is the shortest path distance. A common meeting point after steps implies by the triangle inequality. Conversely, choose a middle vertex of a shortest connecting graph path; both walkers reach it within steps, and the earlier arrival waits. The wait is essential when the path length is an odd integer. This distance on the joint Cartesian product state space is a consistent heuristic: each joint move changes the walkers’ separation by at most two. Replacing by an obstacle-free Manhattan distance preserves admissible heuristic and consistent heuristic guarantees.
A search problem in which the available observations need not identify the current physical state. The controller must choose the same action for physical states that its observed history cannot distinguish. A belief state summarizes those possibilities; contingent planning selects future actions according to subsequent observations.
Sensorless planning chooses one action sequence that succeeds from every possible initial physical state without receiving distinguishing observations during execution. A belief state is a set of possibilities. For a deterministic search transition model , an applicable action maps to ; for nondeterministic outcomes, take the union of all possible successors. Applicability must hold for every member of , and success requires the resulting belief state to be a subset of the physical goal set.
Every fixed action sequence preserves inclusion of the initial belief states. Consequently, a successful plan for also succeeds for every subset of . Success on a superset is an additional requirement, so cannot be inferred from success on alone. This property supports incremental belief-state search.
An incremental belief-state search initially plans for a small subset of the possible initial states, then tests the candidate plan on the full initial belief state . If a state in makes an action inapplicable or fails the final goal test, add that counterexample to and solve the enlarged problem. The new search may need to revise the entire plan, rather than append actions to the previous candidate.
With finitely many initial states and a complete finite-model solver for each restricted problem, at most state additions are required. Failure to find a plan even for a restricted subset proves that none can work for the whole belief state. A candidate that passes full validation is a genuine plan for sensorless planning. The advantage is selective tracking: a small number of representative initial states may force a universally successful plan without constructing the full power set search space.
Without a prior probability distribution, a belief state is the set of physical states still compatible with an observed history. If the physical search transition model is deterministic, , and the sensor map is , action followed by observation givesFor a set-valued outcome relation, replace the image by the set union of all possible successors before filtering. A guaranteed-success goal test requires every member of the surviving belief state to satisfy the physical goal. A probabilistic belief is instead a posterior probability distribution, requiring a specified prior and observation law.
A heuristic function obtained by solving an easier problem that permits every original transition and possibly additional ones, with original transitions costing no more in the easier problem. Every original solution remains available, so the easier optimum is an admissible heuristic.
If is the exact distance to the relaxed goal set, each original transition also gives by taking that transition and then a relaxed optimal continuation. Thus this construction gives a consistent heuristic when original goals have relaxed distance zero. For a four-direction grid walk, deleting obstacles gives Manhattan distance; deleting a pursuer's capture constraint supplies another relaxation. The resulting estimate can remain finite when the original goal is unreachable.
Map original states to simpler abstract states, include every projected original transition at no greater cost, and map original goals to abstract goals. An original goal-reaching graph path then projects to an abstract goal-reaching walk, so the exact abstract distance is an admissible heuristic. A pattern database stores such distances for repeated lookup.
A table of precomputed exact abstract goal distances used as an abstraction heuristic. Retaining a subset of the disks of a Tower of Hanoi instance gives a smaller abstract puzzle: moving an ignored disk does not change the abstract state, and moving a retained disk projects to a legal abstract move. Taking maxima of pattern database estimates preserves admissibility; summing them requires an additional cost-partition argument.
For positive-precondition STRIPS with a positive conjunctive goal, remove every delete effect and use the exact shortest relaxed plan cost. Every original plan still succeeds in the relaxed model because facts can only accumulate, so its relaxed optimum is an admissible heuristic. The cost of an arbitrary relaxed plan is an upper bound on the relaxed optimum and need not be an admissible heuristic for the original problem.
A heuristic function is consistent if at every goal andfor every permitted transition with step cost . Summing these inequalities along a finite route to a goal gives its total cost. Taking the minimum over such routes proves that every consistent heuristic is an admissible heuristic.
A heuristic function bounded above by the minimum remaining goal cost . When no goal is reachable, take . Admissibility is a lower-bound guarantee, rather than a statement that the estimate is usually numerically accurate. Ignoring constraints can produce a relaxation heuristic because it enlarges the available solution set.
If , their pointwise minimum, pointwise maximum and each convex combination with are admissible heuristics. Each inequality follows directly by comparison with . The maximum has heuristic dominance over the minimum and every such convex combination.
A sum need not be an admissible heuristic: two exact estimates of the same cost-one remaining action sum to two. A sufficient condition for a valid additive construction is separate nonnegative action-cost allocations with , and estimates bounded by the corresponding optimal allocated costs. Every goal-reaching graph path then costs at least under its original costs. Taking the minimum proves admissibility without counting the same work twice.
If are consistent heuristics, their maximum, minimum and fixed convex combinations are also consistent heuristics. For the maximum, choose an index attaining it at the source and bound its successor by the successor maximum. For the minimum, choose an index attaining it at the successor and bound the source minimum by that component. For a convex combination, multiply the two consistency inequalities by their nonnegative weights and add them. All these combinations vanish at goals when the inputs do.
A function estimating the remaining cost from a state to a goal in a search problem. The estimate is an admissible heuristic when it never exceeds the true minimum remaining cost. A consistent heuristic satisfies an additional local inequality along each permitted transition.
The exact minimum remaining path cost from a state to a goal state, with value when no goal is reachable. For nonnegative step costs, at goals and on every transition. Thus a perfect heuristic is a consistent heuristic and an admissible heuristic. It measures remaining cost; a greedy best-first search decision using only this number can still take an excessively costly incoming edge.
A comparison oracle revealing the ordering of remaining optimal costs without returning their magnitudes. It supplies enough information for greedy best-first search. Its ordering alone does not provide the numerical differences needed to compare sums with independently varying accumulated costs. For , , remaining costs and have the same pairwise order but give opposite orderings of .
A heuristic function dominates if everywhere. When both are admissible heuristics, the larger estimate is at least as informative for A-star search: for a fixed accumulated path cost and optimal solution cost , implies . This compares the compulsory search region, not arbitrary tie handling at , evaluation overhead or wall-clock time.
A condition deciding whether a state successfully completes a search problem. Its timing must agree with the search transition model: arriving at a destination before an adversary's compulsory response need not be a successful terminal state.
The rule giving the successor state of each permitted state-action pair in a search problem. A compound action may include deterministic environmental responses. If a game state is sampled at full-turn boundaries, its search transition model must still detect terminal events occurring inside the turn. Otherwise an intermediate failure can be incorrectly hidden by the final position. All information needed for future successors and the goal test must be encoded in the state or supplied as fixed problem data.
A rooted tree whose nodes are partial search states and whose children are possible next choices. Leaves represent completed candidates or terminated branches. Backtracking traverses this tree while storing the current path, and search pruning removes branches that cannot yield a useful completion.
The number of action edges between a search node and the root of its search tree. It is zero at the root. When every step costs more than , a positive-depth node satisfies , connecting depth finiteness to path cost bounds.
An entry in a search tree representing a particular action history. It normally stores the current state, its parent, its last action and accumulated path cost . Distinct search nodes can represent the same state; identifying them changes tree search into a form of graph search and requires an appropriate repeated-state policy.
The generated but unexpanded search nodes maintained by a search algorithm. Best-first search selects the next expansion from this frontier using a priority queue or an equivalent ordering operation. A lower-bound argument about a frontier node on an optimal path is central to A-star search correctness.
The number of children of a node in a search tree, or an upper bound on that number over the tree. With branching factor at most and depth at most , a complete traversal visits at most nodes.
Assign values from specified domains to variables so that all stated constraints hold simultaneously. A partial assignment can be rejected when it violates a constraint or leaves an unassigned variable with no permissible value. Backtracking applies this test during a depth-first search.
The hypergraph whose vertices are the variables of a constraint satisfaction problem and whose hypergraph edges are its constraint scopes. Several constraints can have the same scope. An incidence drawing uses extra scope nodes for display; these do not become extra variables of the original problem. Ordinary treewidth of a constraint hypergraph refers to treewidth of its primal graph, equivalently to a tree decomposition covering each whole scope, not to generalized hypergraph width measures.
The graph with one vertex per variable and an edge between distinct variables occurring in a common constraint scope. Each hypergraph edge of the constraint hypergraph becomes a clique. A constraint satisfaction problem consisting only of all-different constraints on a common constraint domain is exactly a proper graph colouring problem on this primal graph.
A cardinality constraint restricts how many members of a specified collection are selected or satisfy a property. For Boolean variables, exactly selected entries gives the displayed sum; upper and lower bounds give at-most and at-least variants. Constraint propagation can maintain the number already selected and the number still available. A requirement involving many variables is a global constraint, even when it has a compact arithmetic description.
Choose distinct squares of an chessboard so that no chosen pair has absolute coordinate differences or . One constraint satisfaction problem representation has square-valued variables, requiring distinctness and pairwise nonattack. Another has one Boolean variable per square, a cardinality constraint fixing their sum to , and one mutual-exclusion constraint for every edge of the knight attack graph. The first has fewer variables when is small but represents each unlabelled placement up to times; the second uses only binary constraint domains and sparse local attack restrictions.
The knight attack graph has one vertex per chessboard square and an edge between squares linked by a knight move. A nonattacking placement is an independent set. Colouring squares by the parity of the coordinate sum makes this a bipartite graph, because every knight move changes that parity. Every vertex has degree at most eight, with fewer attacks near the boundary.
Represent each original value choice by a Boolean variable and impose an exactly-one constraint for each original variable. For every forbidden tuple of a constraint with scope , add the Boolean clause . A complete original assignment satisfies every constraint exactly when its one-hot indicators satisfy all these Boolean clauses: each forbidden-tuple Boolean clause excludes precisely that joint choice. A satisfying assignment decodes by reading the unique true indicator for each original variable.
For constraint domain sizes , pairwise uniqueness requires Boolean clauses. If a constraint has forbidden tuples and arity , its contribution is Boolean clauses and literal occurrences. Thus bounded arity gives a polynomial-size encoding in explicitly listed domains, whereas enumerating a succinct high-arity relation can be exponential in its description length. Unit propagation on this encoding can be weaker than arc consistency on the original binary constraints.
Enumerate assignments to a cycle cutset, reject internal violations, filter all crossing binary constraints, and solve the residual forest by tree-structured constraint satisfaction. A full solution restricts to one enumerated cutset assignment; the residual tree passes preserve all its values. Conversely, a consistent cutset assignment combined with supported residual solutions satisfies every constraint. These observations prove completeness and soundness.
With variables, maximum constraint domain size and cutset size , there are at most assignments and residual tree work per assignment. Internal cutset and crossing-constraint tests require additional accounting. The method is attractive when a small cycle cutset is available.[ref]
Choose an unassigned variable constrained to the greatest number of other unassigned variables. This is commonly a tie-breaker after minimum remaining values. The relevant vertex degree is computed in the remaining constraint graph, rather than counting neighbors already assigned. It aims to make each decision constrain many future decisions without changing the solution set.
A restriction on the value of one variable. In a finite-domain constraint satisfaction problem, it can be applied by deleting disallowed values from that variable's constraint domain before search. It introduces no edge in the binary constraint graph.
Place queens on an chessboard so that none share a row, column or diagonal. One constraint satisfaction problem encoding uses a column variable for each row, with and whenever . The pigeonhole principle explains why one queen per row loses no solutions. Prescribed occupied cells give the queens completion problem.
Complete a prescribed subset of occupied cells to a solution of the N-queens problem while retaining every prescribed queen. In a row-variable constraint satisfaction problem, a clue gives the singleton constraint domain . Conflicting clues prove impossibility immediately, but nonattacking clues need not extend to a full solution. Backtracking decides the finite problem; hill climbing can search large candidate boards without an exhaustive guarantee.
A binary constraint satisfaction problem whose constraint graph is a tree. Restrict constraint domains by unary conditions first. Choose a rooted tree orientation and process children before parents. For each child of , retain in only values having a compatible value in the already reduced . Thus every retained parent value has support in each child subtree.
If the root constraint domain becomes empty, no solution exists. Otherwise choose any root value, then recursively choose supported child values. A child-to-parent arc consistency pass need not enforce full arc consistency in both directions; the chosen directional condition suffices for this construction.
The proof uses mathematical induction on subtrees. A retained leaf value satisfies its unary requirements. Each retained parent value has a supported value in every child subtree. Those subtree solutions can be combined because the tree has no edges between different child subtrees. Therefore every retained parent value extends to a whole subtree solution, and every retained root value extends to a complete solution without backtracking.
For variables and maximum constraint domain size , scanning all value pairs once per edge costs time complexity in Big O notation, when one binary constraint evaluation has unit cost. If a constraint requires summing bundle values, its evaluation cost must also be counted.
A directed requirement for a binary constraint : every remaining has at least one support with . Revising the arc deletes unsupported values from ; it does not directly delete values from . Full arc consistency requires the condition in both directions on every edge of the constraint graph. On general graphs, it need not imply that a complete solution exists.
Compute an arc-consistency closure by revising every directed constrained pair in complete sweeps until one sweep deletes nothing. The first sweep is unconditional. With variables, maximum constraint domain size , and constrained pairs, at most deletions permit at most sweeps. At per revision plus per emptiness scan, a direct time complexity bound is . AC-3 uses a work list to avoid scanning unrelated arcs after each local change.
The greatest componentwise subdomains of given finite initial constraint domains satisfying every directed arc consistency condition, allowing empty subdomains. Repeated sound revisions to a fixed point produce this same closure regardless of revision order, provided every affected arc is eventually reconsidered.
For the proof, fix subdomains of the initial satisfying arc consistency. If all current contain , every value in has a support in , so revising preserves . Mathematical induction shows that every revision preserves every such family . At termination the current domains themselves satisfy arc consistency, so they are the greatest such family. Algorithms that stop immediately on the first empty constraint domain need not finish computing the closure, but correctly establish that no complete solution exists.
An arc consistency algorithm maintaining a work list of directed constrained variable pairs. Revising deletes each value of with no compatible value in . If shrinks, incoming arcs are reconsidered; the just-used neighbor need not be included, since deleted values had no support in and hence supported no surviving value there. Initially empty constraint domains are rejected before processing.
Each deletion preserves every complete solution: a solution using the removed value would supply its missing support. Therefore an empty constraint domain certifies impossibility. Successful termination establishes arc consistency but need not establish satisfiability. A triangle of two-valued inequality constraints supplies a counterexample: all values have pairwise support, but no assignment can satisfy all three inequalities.
For variables, constrained pairs and maximum constraint domain size , assume constant-time compatibility tests for combined pair relations. A revision costs , and each shrinking source constraint domain can cause at most rounds of reconsideration of its incoming arcs. Thus there are revisions and time complexity . Fixed , including two-valued constraint domains, gives linear time in .
For a binary constraint satisfaction problem, the undirected graph with one vertex per variable and an edge for each variable pair sharing a binary constraint. Unary conditions restrict constraint domains but add no edges. A more general constraint can be represented in a primal constraint graph by joining every pair of variables in its scope; such edges do not make a genuinely many-variable constraint binary.
After restricting constraint domains, a binary constraint can become automatically satisfied for every remaining pair of values. Removing such constraints can reveal a tree and enable tree-structured constraint satisfaction.
A set of vertices whose deletion leaves a forest. For a binary constraint satisfaction problem, fixing these variables and filtering the remaining constraint domains leaves independent instances of tree-structured constraint satisfaction. A valid cutset need not be minimum; smaller cutsets reduce the exponential enumeration in cutset conditioning.
A restriction involving two variables in a constraint satisfaction problem, represented by the allowed value pairs . Multiple restrictions on the same pair can be combined by intersection. For bundle allocation, disjointness and the two directional envy-free allocation inequalities together define one compatibility relation.
The set of values permitted for a variable in a constraint satisfaction problem. All assignments before relational constraints form the Cartesian product , whose cardinality is for finite domains. Unary restrictions can be incorporated directly into the constraint domain by deleting forbidden values.
A finite constraint satisfaction problem on a array. Each entry must be one of the integers , and every row, column, and designated box must contain each value once. Given entries constrain the possible completions; backtracking searches those completions.
Repeatedly apply a constraint propagation operation that only deletes values from finite constraint domains, preserves their order, and preserves every valid assignment. The sum of domain sizes is a nonnegative loop variant at every changing step, so repetition reaches a fixed point. For initial candidate values there are at most changing steps. An empty domain proves failure; a non-singleton fixed point may still require backtracking or explicit enumeration. Preservation of solutions, rather than mere deletion, is essential.
Choose an unassigned variable with the fewest currently legal values. No legal values detects failure immediately; exactly one legal value forces a choice. This ordering can reduce the search tree without changing the set of solutions.
Articles by others on the same topic
A computational problem refers to a task that can be formalized in terms of inputs, outputs, and a specific method or algorithm to transform the inputs into the outputs. In more technical terms, a computational problem consists of defining a set of instances, where each instance is associated with a specific input, and specifying the desired output for those inputs.
