Interchangeability algorithm (original) (raw)
In computer science, an interchangeability algorithm is a technique used to more efficiently solve constraint satisfaction problems (CSP). A CSP is a mathematical problem in which objects, represented by variables, are subject to constraints on the values of those variables; the goal in a CSP is to assign values to the variables that are consistent with the constraints. If two variables A and B in a CSP may be swapped for each other (that is, A is replaced by B and B is replaced by A) without changing the nature of the problem or its solutions, then A and B are interchangeable variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the search space for solutions to a CSP problem may be reduced. For example, if solutions with A=1 and B=2 have be
| Property | Value |
|---|---|
| dbo:abstract | In computer science, an interchangeability algorithm is a technique used to more efficiently solve constraint satisfaction problems (CSP). A CSP is a mathematical problem in which objects, represented by variables, are subject to constraints on the values of those variables; the goal in a CSP is to assign values to the variables that are consistent with the constraints. If two variables A and B in a CSP may be swapped for each other (that is, A is replaced by B and B is replaced by A) without changing the nature of the problem or its solutions, then A and B are interchangeable variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the search space for solutions to a CSP problem may be reduced. For example, if solutions with A=1 and B=2 have been tried, then by interchange symmetry, solutions with B=1 and A=2 need not be investigated. The concept of interchangeability and the interchangeability algorithm in constraint satisfaction problems was first introduced by Eugene Freuder in 1991. The interchangeability algorithm reduces the search space of backtracking search algorithms, thereby improving the efficiency of NP-complete CSP problems. (en) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Interchangeability.png?width=300 |
| dbo:wikiPageID | 40487993 (xsd:integer) |
| dbo:wikiPageLength | 6525 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 941933674 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Constraint_satisfaction_problem dbr:Computer_science dbr:Feasible_region dbr:Artificial_intelligence dbc:Constraint_programming dbr:Graph_coloring_problem dbr:NP-completeness dbr:Backtracking_search dbr:Discrimination_tree dbr:File:Interchangeability.png |
| dbp:wikiPageUsesTemplate | dbt:Orphan dbt:Reflist dbt:Var |
| dct:subject | dbc:Constraint_programming |
| gold:hypernym | dbr:Technique |
| rdf:type | dbo:TopicalConcept |
| rdfs:comment | In computer science, an interchangeability algorithm is a technique used to more efficiently solve constraint satisfaction problems (CSP). A CSP is a mathematical problem in which objects, represented by variables, are subject to constraints on the values of those variables; the goal in a CSP is to assign values to the variables that are consistent with the constraints. If two variables A and B in a CSP may be swapped for each other (that is, A is replaced by B and B is replaced by A) without changing the nature of the problem or its solutions, then A and B are interchangeable variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the search space for solutions to a CSP problem may be reduced. For example, if solutions with A=1 and B=2 have be (en) |
| rdfs:label | Interchangeability algorithm (en) |
| owl:sameAs | freebase:Interchangeability algorithm wikidata:Interchangeability algorithm https://global.dbpedia.org/id/fNZF |
| prov:wasDerivedFrom | wikipedia-en:Interchangeability_algorithm?oldid=941933674&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Interchangeability.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Interchangeability_algorithm |
| is dbo:wikiPageRedirects of | dbr:Interchangeability_(computer_science) dbr:Interchangeability_Algorithm |
| is dbo:wikiPageWikiLink of | dbr:Interchangeability_(computer_science) dbr:Interchangeability_Algorithm |
| is foaf:primaryTopic of | wikipedia-en:Interchangeability_algorithm |
