.png){kind=icon}
返回
Indexed Subset Construction: A Structured Algorithmic Framework
.png){kind=icon}
PRE
AI
DOI：10.3390/a19050397.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
本文从组合搜索空间的结构化探索视角研究了NP完全问题中的子集构造。传统方法依赖子集的穷举枚举，导致时间和内存需求呈指数增长。为解决此局限，我们引入了一种基于有限集与其关联索引集之间对应关系的索引框架。在此框架中，子集被表示为有序的索引序列，使得子集构造可重新表述为在索引空间上进行的约束引导搜索过程。候选子集通过其索引导出的数值描述符（称为索引凭证）进行表征，这些描述符引导并筛选构造过程。子集生成进一步通过可接受的索引区间进行组织，这些区间限制可行转换并减小有效搜索空间。该框架基于索引表示和成对索引组合的结构化遍历。在代表性实例上的计算实验说明了索引构造过程的行为，并表明其在小规模和中等规模实例上相对于传统基于枚举的方法的效率。所提出的方法为组合搜索提供了结构化视角，并为基于子集结构约束探索的算法进一步发展奠定了基础。
Keyword:
combinatorial search
subset construction
indexed representation
constraint-guided search
subset sum problem
NP-complete problems