基于DNA计算的多维分配数据关联算法①

摘要

cqvip:针对多目标跟踪中的多维分配数据关联这一NP难题，将DNA计算用于数据关联研究，利用DNA分子链生化反应的高度并行性，实现了基于DNA计算的多维分配数据关联算法。该算法利用包含限制性内切酶HaelII回文序列的DNA分子链对观测：视线进行编码，通过连接和退火操作获得所有目标关联组合，然后利用检测DNA发夹结；陶和凝胶电泳技术排除不满足约束条件的目标关联组合，筛选出多维分配数据关联的最优解。分析结果表明：基于DNA计算的多维分配数据关联算法所需的DNA分子链数即空间复杂度为O（nk!／（c-m）!），将多维分配问题的指数级复杂度降低到多项式复杂度O（mn），其中n为传感器数，m为目标数，k为目标定位点数。