互斥约束工作流可满足性决策的匹配剪枝模式回溯法

针对用于工作流可满足决策的模式回溯技术如何平衡性能与代价的问题,提出了一种对部分模式解及时进行授权匹配验证的优化方法,牺牲一定验证效率以增强剪枝能力。就仅受互斥约束的问题情形,利用实例难易程度的两极分化现象对总体时间性能进行了分析。随机生成数据集上的实验表明,这一优化极大地降低了模式回溯在难实例上的时间代价,而对易实例执行时间的影响很小,且相对于其他基于动态规划的代表性算法,优化后的算法在时间和空间性能上均有显著优势。     

Experimental evaluation of the BER performance in optical OFDM system based on discrete Hartley transform precoding

We experimentally assess the bit error rate （BER） performance of an intensity modulation/direct detection （IM/DD） optical orthogonal frequency division multiplexing （OFDM） system based on discrete Hartley transform （DHT） precoding in single-mode fiber （SMF） link for 2.5 Gbit/s quadrature phase shift keying （QPSK） OFDM symbol rate. The experimental results show that for the optical OFDM system based on DHT-precoding, the receiver sensitivity at the BER of 10-4 after 100 km SMF transmission is about 1.5 dBm better than that of the original QPSK OFDM signal, and the DHT-precoded OFDM QPSK signal can achieve approximately 1.3 dB of peak-to-average power ratio （PAPR） reduction.     

资源独立工作流可满足性的最小增量模式回溯

工作流可满足性是业务安全规划的基本问题, 正在面临高资源配比(资源数n显著大于步骤数k)造成的性能挑战. 在资源独立约束下, 其最高效求解途径是模式空间上的增量回溯法IPB. 为克服结点真实性验证的性能瓶颈, 它增量计算模式k指派(二部)图及其(左完备)匹配, 分别需要O(kn)和O(k²)时间. 利用父子模式的原子差异增量计算完全指派图, 只需O(n)时间, 特别是其实际性能, 将随模式块规模增长迅速提高. 但该图的O(kn)规模导致了同样的增量匹配时间. 进而引入完备k核心匹配概念, 证明其存在性等价于左完备匹配, 且其增量计算时间为O(k²). 由此, 建立了时间复杂度更低的最小增量模式回溯法. 在含互斥和两种全局值势约束而授权比例约为1/4的扩展公开实例集上进行实验, 结果表明: 当n/k=10(及n/k=100), 而k变化时, 该方法较IPB有平均超过2(及5)倍、最低1.5(及2.9)倍的性能优势; 当k=18(及k=36), 而n/k=2~4096(及n/k=2~2048)时, 该方法有平均超过2.6(及3.6)倍优势; 而较2021年Minizinc挑战赛的冠军求解器Google OR-Tools CP-SAT, 该方法最低有超过3倍优势.     

工作流可满足性(≠,=)计数及其#P完全性

工作流可满足性（WS）是资源分配对访问控制（AC）策略提出的基本要求.相关工作主要围绕WS决策问题展开,通过找到一个具体的解来说明AC策略的正确性.然而为了进一步验证AC策略在资源异常情况下的合理性,统计所有解的数量将更有帮助.本文对互斥和绑定约束下的WS计数问题进行研究,通过构造从典范性#P完全问题#3SAT到该问题的多项式计数归约,证明其属于#P完全问题,为其恰当地求解奠定了理论基础.     

基于回溯树分解的互斥约束工作流可满足性计数

工作流可满足性（WS）研究一定访问控制策略下的资源分配问题,其计数问题有利于判断工作流对资源异常情况的顽健性。本文研究互斥约束下的WS计数问题,通过多项式计数归约为约束可满足性计数问题,将经典的回溯树分解方法用于#WS（≠）求解。实验表明,改进后的算法降低了执行时间,相对于现有#WS（≠）算法,提出的算法对低密度约束下的工作流具有一定的综合性能优势。     

工作流可满足性的约简增量模式回溯法

在大量云/服务化资源造成的性能压力下，增量模式回溯法(Incremental Pattern Backtracking, IPB)及其k指派技术是工作流可满足性求解的首选途径，但对“欠约束”实例，其模式枚举性能显著下降，不利于大量可行解的优化选择。针对该问题提出新颖的简指派图概念，证明其可取代k指派图用于模式授权匹配验证，且尽管其块邻域大小耦合了图的整体信息，但仍可以增量方式计算。进而，分析了增量化简指派的实施条件和效果，及其主要影响因素。由此建立了约简增量模式回溯法(Reduced Incremental Pattern Backtracking, RIPB)。在资源配比为2～100的两个仿真实例集上测试，实验结果表明：在其基本子集上，RIPB较IPB有0.96～1.24倍时间性能优势；当资源比例升高或约束密度降低时，RIPB的优势有不同程度扩大；特别地，对资源配比为10而授权比例在1/2左右的两个子集，RIPB的平均优势分别可达1.29和1.61倍。