This HTML5 document contains 79 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-shhttp://sh.dbpedia.org/resource/
dctermshttp://purl.org/dc/terms/
n16https://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n25https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-srhttp://sr.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-frhttp://fr.dbpedia.org/resource/
dbpedia-zhhttp://zh.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
dbchttp://dbpedia.org/resource/Category:
n11http://www-cs-faculty.stanford.edu/~uno/papers/
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:List_of_partition_topics
dbo:wikiPageWikiLink
dbr:Knuth's_Algorithm_X
Subject Item
dbr:Exact_cover
dbo:wikiPageWikiLink
dbr:Knuth's_Algorithm_X
Subject Item
dbr:Knuth's_Algorithm_X
rdf:type
yago:PsychologicalFeature100023100 yago:Activity100407535 yago:Rule105846932 yago:Procedure101023820 yago:Abstraction100002137 yago:WikicatSearchAlgorithms yago:YagoPermanentlyLocatedEntity yago:Act100030358 yago:Algorithm105847438 yago:Event100029378
rdfs:label
X算法 Algorithme X de Knuth Knuth's Algorithm X
rdfs:comment
在计算机科学中，X算法可用来求解精确覆盖问题。此名称最早在高德纳的论文《舞蹈链》中出现，他认为此算法是“试错法中最显而易见”的。 就技术而言，X算法是一个深度优先的回溯算法。由于X算法是一个解决精确覆盖问题的简洁方法，高德纳希望通过该算法体现舞蹈链数据结构的高效性，他把使用后者的X算法称为DLX。 X算法用由0和1组成的矩阵A来表示精确覆盖问题，目标是选出矩阵的若干行，使得其中的1在所有列中出现且仅出现一次。 X算法的步骤如下： 选择r的不确定性意味着算法将衍生出若干独立的子算法，每个子算法都从其父算法中继承了去除部分行列的A矩阵。如果其中有一列全为零，则当前情况无解，子算法返回失败，但不一定意味整个问题无解。 实际上，所有子算法形成了一棵搜索树，其中原问题为根节点，树的第k层由子算法在第k次所选择的行组成。整个算法即用回溯法对搜索树深度优先遍历。 第二步中，无论用什么方法选择列最终都可以得到解，但有的方法效率明显较高。为减少迭代次数，高德纳建议每次都选取1最少的列。 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. The exact cover problem is represented in Algorithm X by a 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: L'algorithme X de Donald Knuth est un algorithme récursif (en), de parcours en profondeur et à retour sur trace. Il permet de trouver des solutions au problème de la couverture exacte, représenté sous la forme d'une matrice contenant des 0 et des 1. L'objectif est de déterminer un sous-ensemble de lignes tel que le chiffre 1 n'apparaisse dans chaque colonne qu'une et une seule fois.
dcterms:subject
dbc:Donald_Knuth dbc:Search_algorithms
dbo:wikiPageID
3626542
dbo:wikiPageRevisionID
1121142608
dbo:wikiPageWikiLink
dbr:Algorithm dbr:Donald_Knuth dbc:Search_algorithms dbr:Search_tree dbc:Donald_Knuth dbr:Deterministic_algorithm dbr:Doubly_linked_list dbr:Backtracking dbr:Torus dbr:Dancing_links dbr:Recursion_(computer_science) dbr:Exact_cover dbr:Dancing_Links dbr:Nondeterministic_algorithm dbr:Depth-first
dbo:wikiPageExternalLink
n11:dancing-color.ps.gz n16:0011047.pdf
owl:sameAs
yago-res:Knuth's_Algorithm_X dbpedia-sr:Кнутов_алгоритам_Икс dbpedia-sh:Кнутов_алгоритам_Икс wikidata:Q6424025 dbpedia-fr:Algorithme_X_de_Knuth dbpedia-zh:X算法 dbpedia-fa:الگوریتم_اکس_کنوث freebase:m.09qv19 n25:4paqU
dbp:wikiPageUsesTemplate
dbt:Mathcal dbt:Short_description dbt:ArXiv dbt:Citation dbt:Quote_frame dbt:Reflist dbt:Sup dbt:Donald_Knuth_navbox
dbo:abstract
在计算机科学中，X算法可用来求解精确覆盖问题。此名称最早在高德纳的论文《舞蹈链》中出现，他认为此算法是“试错法中最显而易见”的。 就技术而言，X算法是一个深度优先的回溯算法。由于X算法是一个解决精确覆盖问题的简洁方法，高德纳希望通过该算法体现舞蹈链数据结构的高效性，他把使用后者的X算法称为DLX。 X算法用由0和1组成的矩阵A来表示精确覆盖问题，目标是选出矩阵的若干行，使得其中的1在所有列中出现且仅出现一次。 X算法的步骤如下： 选择r的不确定性意味着算法将衍生出若干独立的子算法，每个子算法都从其父算法中继承了去除部分行列的A矩阵。如果其中有一列全为零，则当前情况无解，子算法返回失败，但不一定意味整个问题无解。 实际上，所有子算法形成了一棵搜索树，其中原问题为根节点，树的第k层由子算法在第k次所选择的行组成。整个算法即用回溯法对搜索树深度优先遍历。 第二步中，无论用什么方法选择列最终都可以得到解，但有的方法效率明显较高。为减少迭代次数，高德纳建议每次都选取1最少的列。 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. The exact cover problem is represented in Algorithm X by a 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. 1. * Otherwise choose a column c (deterministically). 2. * Choose a row r such that Ar, c = 1 (nondeterministically). 3. * Include row r in the partial solution. 4. * For each column j such that Ar, j = 1,for each row i such that Ai, j = 1,delete row i from matrix A.delete column j from matrix A. 5. * Repeat this algorithm recursively on the reduced matrix A. The nondeterministic choice of r means that the algorithm recurses over independent subalgorithms; each subalgorithm inherits the current matrix A, but reduces it with respect to a different row r.If column c is entirely zero, there are no subalgorithms and the process terminates unsuccessfully. The subalgorithms form a search tree in a natural way, with the original problem at the root and with level k containing each subalgorithm that corresponds to k chosen rows.Backtracking is the process of traversing the tree in preorder, depth first. Any systematic rule for choosing column c in this procedure will find all solutions, but some rules work much better than others.To reduce the number of iterations, Knuth suggests that the column-choosing algorithm select a column with the smallest number of 1s in it. L'algorithme X de Donald Knuth est un algorithme récursif (en), de parcours en profondeur et à retour sur trace. Il permet de trouver des solutions au problème de la couverture exacte, représenté sous la forme d'une matrice contenant des 0 et des 1. L'objectif est de déterminer un sous-ensemble de lignes tel que le chiffre 1 n'apparaisse dans chaque colonne qu'une et une seule fois.
gold:hypernym
dbr:Knuth
prov:wasDerivedFrom
wikipedia-en:Knuth's_Algorithm_X?oldid=1121142608&ns=0
dbo:wikiPageLength
14379
foaf:isPrimaryTopicOf
wikipedia-en:Knuth's_Algorithm_X
Subject Item
dbr:Donald_Knuth
dbo:wikiPageWikiLink
dbr:Knuth's_Algorithm_X
Subject Item
dbr:Aztec_diamond
dbo:wikiPageWikiLink
dbr:Knuth's_Algorithm_X
Subject Item
dbr:Knuth
dbo:wikiPageWikiLink
dbr:Knuth's_Algorithm_X
dbo:wikiPageDisambiguates
dbr:Knuth's_Algorithm_X
Subject Item
dbr:Sudoku_solving_algorithms
dbo:wikiPageWikiLink
dbr:Knuth's_Algorithm_X
Subject Item
dbr:Knuth's_algorithm_X
dbo:wikiPageWikiLink
dbr:Knuth's_Algorithm_X
dbo:wikiPageRedirects
dbr:Knuth's_Algorithm_X
Subject Item
dbr:Knuth's_algorithm_x
dbo:wikiPageWikiLink
dbr:Knuth's_Algorithm_X
dbo:wikiPageRedirects
dbr:Knuth's_Algorithm_X
Subject Item
dbr:Algorithm_X
dbo:wikiPageWikiLink
dbr:Knuth's_Algorithm_X
dbo:wikiPageRedirects
dbr:Knuth's_Algorithm_X
Subject Item
dbr:Knuths_Algorithm_x
dbo:wikiPageWikiLink
dbr:Knuth's_Algorithm_X
dbo:wikiPageRedirects
dbr:Knuth's_Algorithm_X
Subject Item
dbr:Knuth’s_Algorithm_X
dbo:wikiPageWikiLink
dbr:Knuth's_Algorithm_X
dbo:wikiPageRedirects
dbr:Knuth's_Algorithm_X
Subject Item
wikipedia-en:Knuth's_Algorithm_X
foaf:primaryTopic
dbr:Knuth's_Algorithm_X