Symmetry Breaking in Graceful Graphs
Symmetry Breaking in Graceful Graphs
复制标题
优雅图形中的对称性破缺
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Barbara M. Smith
中科院分区：
文献类型：
--
作者：
K. Petrie;Barbara M. Smith
对称性经常出现在约束满足问题（CSP）中。例如，在对图的节点进行三色着色时，为每个节点分配特定颜色的 CSP 模型具有一组等效解决方案，其中三种颜色被排列。 CSP 中的对称性可能会导致搜索浪费，因为对解决方案的搜索可能会重复访问与已考虑的部分对称的部分分配。如果部分赋值不能得出解，则任何对称等价赋值也不会得出解。当搜索所有解时，对于找到的每一个解，也将找到所有对称等价的解。
Symmetry occurs frequently in Constraint Satisfaction Problems (CSPs). For instance, in 3-colouring the nodes of a graph, a CSP model that assigns a specific colour to each node has sets of equivalent solutions in which the three colours are permuted. Symmetry in CSPs can cause wasted search, because the search for solutions may repeatedly visit partial assignments symmetric to ones already considered. If a partial assignment does not lead to a solution, neither will any symmetrically equivalent assignment. When searching for all solutions, for every solution found, all the symmetrically equivalent solutions will also be found.