Knuth's Algorithm X
   HOME





Knuth's Algorithm X
Algorithm X is an algorithm for solving the exact cover problem. It is a straightforward recursive, nondeterministic, depth-first, backtracking algorithm used by Donald Knuth to demonstrate an efficient implementation called DLX, which uses the dancing links technique. Algorithm The exact cover problem is represented in Algorithm X by an incidence matrix ''A'' consisting of 0s and 1s. The goal is to select a subset of the rows such that the digit 1 appears in each column exactly once. Algorithm X works as follows: # If the matrix ''A'' has no columns, the current partial solution is a valid solution; terminate successfully. # Otherwise choose a column ''c'' ( deterministically). # Choose a row ''r'' such that ''A''''r'', ''c'' = 1 ( nondeterministically). # Include row ''r'' in the partial solution. # For each column ''j'' such that ''A''''r'', ''j'' = 1, #: for each row ''i'' such that ''A''''i'', ''j'' = 1, #:: delete row ''i'' from matrix ''A''. #: delete column ''j'' from ma ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use Conditional (computer programming), conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning). In contrast, a Heuristic (computer science), heuristic is an approach to solving problems without well-defined correct or optimal results.David A. Grossman, Ophir Frieder, ''Information Retrieval: Algorithms and Heuristics'', 2nd edition, 2004, For example, although social media recommender systems are commonly called "algorithms", they actually rely on heuristics as there is no truly "correct" recommendation. As an e ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Deterministic Algorithm
In computer science, a deterministic algorithm is an algorithm that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by far the most studied and familiar kind of algorithm, as well as one of the most practical, since they can be run on real machines efficiently. Formally, a deterministic algorithm computes a mathematical function; a function has a unique value for any input in its domain, and the algorithm is a process that produces this particular value as output. Formal definition Deterministic algorithms can be defined in terms of a state machine: a ''state'' describes what a machine is doing at a particular instant in time. State machines pass in a discrete manner from one state to another. Just after we enter the input, the machine is in its ''initial state'' or ''start state''. If the machine is deterministic, this means that from this point onwar ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Exact Cover
In the mathematical field of combinatorics, given a collection \mathcal of subsets of a set X, an exact cover is a subcollection \mathcal^ of \mathcal such that each element in X is contained in ''exactly one'' subset in \mathcal^. One says that each element in X ''is covered by'' exactly one subset in \mathcal^. An exact cover is a kind of cover. In other words, \mathcal^ is a partition of X consisting of subsets contained in \mathcal. The exact cover problem to find an exact cover is a kind of constraint satisfaction problem. The elements of \mathcal represent choices and the elements of X represent constraints. It is non-deterministic polynomial time (NP) complete and has a variety of applications, ranging from the optimization of airline flight schedules, cloud computing, and electronic circuit design. An exact cover problem involves the relation ''contains'' between subsets and elements. But an exact cover problem can be represented by any heterogeneous relation between a ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Torus
In geometry, a torus (: tori or toruses) is a surface of revolution generated by revolving a circle in three-dimensional space one full revolution about an axis that is coplanarity, coplanar with the circle. The main types of toruses include ring toruses, horn toruses, and spindle toruses. A ring torus is sometimes colloquially referred to as a donut or doughnut. If the axis of revolution does not touch the circle, the surface has a ring shape and is called a torus of revolution, also known as a ring torus. If the axis of revolution is tangent to the circle, the surface is a horn torus. If the axis of revolution passes twice through the circle, the surface is a Lemon (geometry), spindle torus (or ''self-crossing torus'' or ''self-intersecting torus''). If the axis of revolution passes through the center of the circle, the surface is a degenerate torus, a double-covered sphere. If the revolved curve is not a circle, the surface is called a ''toroid'', as in a square toroid. ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Doubly Linked List
In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the sequence of nodes) and one data field. The beginning and ending nodes' previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders. The two node links allow traversal of the list in either direction. While adding or removing a node in a doubly linked list requires changing more links than the same operations on a singly linked list, the operations are simpler and potentially more efficient (for nodes other than first nodes) because there is no n ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Search Tree
In computer science, a search tree is a tree data structure used for locating specific keys from within a set. In order for a tree to function as a search tree, the key for each node must be greater than any keys in subtrees on the left, and less than any keys in subtrees on the right. The advantage of search trees is their efficient search time given the tree is reasonably balanced, which is to say the leaves at either end are of comparable depths. Various search-tree data structures exist, several of which also allow efficient insertion and deletion of elements, which operations then have to maintain tree balance. Search trees are often used to implement an associative array. The search tree algorithm uses the key from the key–value pair to find a location, and then the application stores the entire key–value pair at that particular location. Types of trees Binary search tree A Binary Search Tree is a node-based data structure where each node contains a key and two su ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Nondeterministic Algorithm
In computer science and computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. Different models of computation give rise to different reasons that an algorithm may be non-deterministic, and different ways to evaluate its performance or correctness: *A concurrent algorithm can perform differently on different runs due to a race condition A race condition or race hazard is the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events, leading to unexpected or inconsistent .... This can happen even with a single-threaded algorithm when it interacts with resources external to it. In general, such an algorithm is considered to perform correctly only when ''all'' possible runs produce the desired results. *A probabilistic algorithm's behavior ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Incidence Matrix
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element of ''X'' and one column for each mapping from ''X'' to ''Y''. The entry in row ''x'' and column ''y'' is 1 if the vertex ''x'' is part of (called ''incident'' in this context) the mapping that corresponds to ''y'', and 0 if it is not. There are variations; see below. Graph theory Incidence matrix is a common graph representation in graph theory. It is different to an adjacency matrix, which encodes the relation of vertex-vertex pairs. Undirected and directed graphs In graph theory an undirected graph has two kinds of incidence matrices: unoriented and oriented. The ''unoriented incidence matrix'' (or simply ''incidence matrix'') of an undirected graph is a n\times m matrix ''B'', where ''n'' and ''m'' are the numbers of vertices and ed ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Exact Cover
In the mathematical field of combinatorics, given a collection \mathcal of subsets of a set X, an exact cover is a subcollection \mathcal^ of \mathcal such that each element in X is contained in ''exactly one'' subset in \mathcal^. One says that each element in X ''is covered by'' exactly one subset in \mathcal^. An exact cover is a kind of cover. In other words, \mathcal^ is a partition of X consisting of subsets contained in \mathcal. The exact cover problem to find an exact cover is a kind of constraint satisfaction problem. The elements of \mathcal represent choices and the elements of X represent constraints. It is non-deterministic polynomial time (NP) complete and has a variety of applications, ranging from the optimization of airline flight schedules, cloud computing, and electronic circuit design. An exact cover problem involves the relation ''contains'' between subsets and elements. But an exact cover problem can be represented by any heterogeneous relation between a ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist and mathematician. He is a professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer science. Knuth has been called the "father of the analysis of algorithms". Knuth is the author of the multi-volume work '' The Art of Computer Programming''. He contributed to the development of the rigorous analysis of the computational complexity of algorithms and systematized formal mathematical techniques for it. In the process, he also popularized the asymptotic notation. In addition to fundamental contributions in several branches of theoretical computer science, Knuth is the creator of the TeX computer typesetting system, the related METAFONT font definition language and rendering system, and the Computer Modern family of typefaces. As a writer and scholar, Knuth created the WEB and CWEB computer programming systems des ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]