一种基于Stirling图枚举算法的分球入盒问题求解

• 作者: 彭哲也 谢民主
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 分球入盒问题 第二类Stirling数 枚举算法 Stirling图 均匀采样
• 年，卷（期）: 2017,（10）
• 所属期刊栏目: 算法
• 页码范围: 248-251,274
• 页数: 5页
• 分类号: TP306.1
• 字数: 4139字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386x.2017.10.044

摘要

已有的分球入盒问题解法通常只关注分球的总方案数,目前尚没有公开的计算机算法来枚举出所有具体的分球方案,而方案的枚举是生物信息学中一些分区优化算法的基础.受第二类Stirling数的递推公式的启发,提出一个新的数据结构——Stirling图.在此基础上设计一个算法来枚举p个不同球分配到g个相同盒子里的所有不同的方案.当p和q较大,枚举出所有的方案不可行时,设计另一个算法在整个方案空间实现均匀采样,输出指定个数的方案.测试结果表明,这些算法在内存为8 GB的普通PC上可在合理的时间内枚举出上百万组不同的方案.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谢民主	湖南师范大学物理与信息科学学院	16	88	4.0	9.0
2	彭哲也	湖南师范大学物理与信息科学学院	2	6	1.0	2.0