行业来风
Industry Express
最少配对数算法研究
余峰 中国金融期货交易所 技术中心，上海 200120 E-mail ： yufeng@cffex.com.cn
摘　要 ： 期货市场中的实物交割是期货交易中非常重要的环节。一个合理的交割配对算法，对提高交割效率起到巨大 的作用。目前中金所仿真国债期货的交割采用与商品交割配对类似的贪心算法，可在 o（nlogn）时间复杂度内求得近 似解，但由于未全面搜索组合，容易导致配对结果不精确。本文证明了“最少配对数”问题是 NPC 问题（完全多项 式非确定性问题） ，全遍历搜索算法复杂度可达 o（n! ），并探讨了一种新的启发式剪枝搜索算法，可在较短时间内 最大范围地搜索近似 实验证明，假设交割数据呈（μ=o，σ=2O）半 分布时，本算法相比原贪心算法能减少 约 0.8 ～ 5.3% 配对数。也从另一个角度证明了当前使用的贪心算法在数据呈半 分布时非常接近于最优解。 最少配对数 ； 贪心算法 ； NPC 问题 ； 启发式剪枝搜索 关键词 ：
2
1 引言
“最少配对数”问题是一个典型的组合优化问题， 其可以被证明是一个 NP-complete（non-deterministic poly-nominal complete）难题。 “最少配对数”问题是 指在交割日将多空双方的交割持仓进行两两配对轧差， 以获得最少配对数量为目标。对于商品期货交割，其 减少了卖方开具增值税发票总数量，对于国债期货交 割则减少了债券划转的总笔数。为简化问题描述，本 算法不涉及多个交割库的情况。 “最少配对数”问题可描述为 ： 给定两个 数集合 A、B，其元素和相等。从两 集合中各取一元素进行配对，若有余数则放回原所在 集合，直至所有数取完。求最少配对数量及对应的配 对方案。 （问题描述 1） “最少配对数”问题易于陈述但难于求解，其方法 可分为精确算法和近似算法。可证明精 法时间复杂 （假设集合 A、B 数量规模都为 n） 。因此 度为 o（n! ） 随着配对数量的增加，算法复杂度呈指数级上升。在 n=10 时已不可能在合理时间内完成计算。本文通过归
2
并相同数、启发式剪枝搜索等方式，扩大了多个数配 对的搜索范围，并能快速降 题规模，在合理的时 间复杂度内计算近似解。经过实验数据证明，该算法 能在较短时间内快速收敛，找到优于当前使用贪心算 法的近似最少配对数量。
2 “最少配对数”问题研究
2.1 现有算法描述 现有交割系统采用了贪心算法，其伪 可描述 为（见表 1） ： 由 此 可 见， 现 使 用 贪 心 算 法 的 时 间 复 杂 度 为 o （nlogn）。本算法采用了一轮“1 对 1”的配对，而后 采用贪心算法，以局部最优解 近似 但因为此算 法并未对所有元素组合进行搜索，因此在某些情况下 并不能计算得到最少配对数。 数组 {7,5,1} 与 {6,4,3}， 如： 若使用贪心算法会过早地判断 7 与 6 的配对，而未尝 试 7 与 3,4 的配对，得到的配对数为 5，而非最优解 4。 若要精 解，必须搜索所有可能的组合。 2.2 规约 NPC 问题 在计算复杂度理论的世界中，NPC 问题，又称 NP
56
Industry Express
行业来风
初始化数组 A,B; Sort(A); // 复杂度 O(n*logn) Sort(B); // 复杂度 O(n*logn) 对 A,B 中相同的数进行配对删除 ; // 复杂度 O(n*logn)，使用堆排序或二分查找 while( 两队列都非空 ) { 取两个数组最大的数配对 ; if( 余数 == 对方队列中某数）// 复杂度 O(n*logn), 二分查找 将余数与该数配对 ; else 将余数按顺序放回原队列 ; }
表 1 现有算法伪代码描述 完全问题或 NP 完备问题， NP 是 （非决定性多项式时间） 中最难的决定性问题。因此 NPC 问题是最不可能被化 简为 P（多项式时间可决定）的决定性问题的集合。许 多人推测 P 与 NPC 没有交集。理由是若任何 NPC 问 题得到多项式时间的解法， 就可应用在所有 NP 问题上。此命题就是知名的 P=NP? 若一问题被证 明为 NPC 问题后，若要精 解只能使用指数级算法。 为了证明某个 NP 问题 A 是 NPC 问题，必须将 A 规约为一个已知的 NPC 问题。而“最少配对数”问题 可被规约为一个已知的 NPC 问题 ： 子集和问题，子集 和问题的描述如下 ： 对于 (S，t)，其中 S 是一个正整数的集合 {x1，X2， t X3…Xn}， 为一个正整数。判断是否存在一个 S 的子集， 使得其中的数的和为目标值 t。更普遍的一个问题是， 求 S 的所有子集中，元素和最接近但不超过 t 的那个子 集的元素和，如果答案就是 t，那么上面一个问题的答 案就是肯定的，否则就是否定的。 我们首先将“最少配对数”问题转化为如下描述 ： 将 两 正 整 数 集 合 A（ 包 含 m 个 数 ） ，B（ 包 含 n 个 数 ） 各 分 成 k 份， 使 得 其 对 应 的 子 集 和 都 相 等，配对数量即为 m+n-k，求使得 k 为最大的分法。 （问题描述 2） 证明“最少配对数”问题为 NPC 问题 ： 构 造 如 下 两 集 合 ： 为 任 意 一 个 集 合， 包 含 m X （m>=2）个数 ； Y 集合只包含两个数 ： 与 。则两 而 t 集合的“最少配对数”为 m+1 还是 m+2 就可转换为 在 X 的所有子集中是否存在元素和为 t 的集合。 “最 因此 少配对数”可以规约为子集和问题，也即证明“最少 配对数”问题是 NPC 问题。

下一页