Introduction to Reconfiguration
Introduction to Reconfiguration
复制标题
DOI：
10.3390/a11040052
复制
发表时间：
2018-04-01
期刊：
影响因子：
2.3
通讯作者：
Nishimura, Naomi
中科院分区：
文献类型：
--
作者：
Nishimura, Naomi
重新配置与解决方案之间的关系与问题实例之间的关系有关，其中一种解决方案对另一种解决方案的重新配置是一系列步骤，使每个步骤都会产生一个中间的可行解决方案。解决方案空间可以表示为重新配置图，如果可以在一个步骤中从另一个步骤形成一个，则可以相邻两个代表解决方案的顶点。该区域的工作涵盖了结构性问题（是否连接了重新配置图？）和算法（如何找到两种解决方案之间的最短步骤序列？），该调查讨论了该地区的技术，结果和未来方向。
Reconfiguration is concerned with relationships among solutions to a problem instance, where the reconfiguration of one solution to another is a sequence of steps such that each step produces an intermediate feasible solution. The solution space can be represented as a reconfiguration graph, where two vertices representing solutions are adjacent if one can be formed from the other in a single step. Work in the area encompasses both structural questions (Is the reconfiguration graph connected?) and algorithmic ones (How can one find the shortest sequence of steps between two solutions?) This survey discusses techniques, results, and future directions in the area.