【摘 要】
：
警察与强盗博弈是一个图搜索问题,解决该问题的关键是确定能成功捕获强盗的最少警察数。在零可视警察与强盗博弈中强盗不可见:任意时刻警察都不知道强盗所在位置。通过建立顶点清理模型对三维网格图的性质进行分析,将三维网格图的顶点集划分成2个子集,导出划分中较小子集与边界的关系,并利用划分中的结论,给出三维网格图中最少警察数的下界。结合图搜索的单调性原则,给出一种可行的单调性搜索策略,确定三维网格图中最少警察数的上界。最后提出一种在三维网格图中最少警察数范围内可行的搜索算法。
论文部分内容阅读
警察与强盗博弈是一个图搜索问题,解决该问题的关键是确定能成功捕获强盗的最少警察数。在零可视警察与强盗博弈中强盗不可见:任意时刻警察都不知道强盗所在位置。通过建立顶点清理模型对三维网格图的性质进行分析,将三维网格图的顶点集划分成2个子集,导出划分中较小子集与边界的关系,并利用划分中的结论,给出三维网格图中最少警察数的下界。结合图搜索的单调性原则,给出一种可行的单调性搜索策略,确定三维网格图中最少警察数的上界。最后提出一种在三维网格图中最少警察数范围内可行的搜索算法。
其他文献
面向边缘计算环境中设备信任度评估的准确性和时间开销等问题,提出一种边缘设备动态信任度评估模型—DTEM。首先,利用时间退化因子表达直接信任度时效性,引入满意度函数修正贝叶斯方程,并结合激励机制评估边缘设备间的直接信任度。其次,利用改进的灰关联分析法确定指标权重,解决了间接信任度评估过程中推荐设备权重的问题。最后,通过信息熵融合直接信任度和间接信任度得出设备综合信任值,同时利用动态更新因子,动态更新综合信任值。仿真分析表明,相比RFSN模型,DTEM在检测恶意设备中误检率平均降低5.7%,设备间交互成功率平
针对传统图案几何纹样提取方法无法得到最优特征向量,导致提取精度低、提取时间长、提取过程抗干扰性较差的问题,提出基于Bhattacharyya(简称B氏)距离准则的图案几何纹样提取方法。分析常见的图案几何纹样特征;利用Bhattacharyya距离准则算法,非线性映射图案几何纹样样本至高维核空间,获取最优特征向量,线性映射最优图案几何纹样样本至低维特征空间,并将核函数应用于映射过程中,提升算法全局收
卷积神经网络因其对图像识别准确率高而在图像检索领域备受青睐,但处理大规模数据集时,基于卷积神经网络提取的深度特征维度高,容易引发"维度灾难"。针对图像检索中深度特征维度高的问题,提出一种基于自适应融合网络特征提取与哈希特征降维的图像检索算法。由于传统哈希处理高维特征复杂度高,因此本文在卷积神经网络中加入自适应融合模块对特征进行重新整合,增强特征表征能力的同时降低特征维度;然后应用稀疏化优化算法对深
为解决暗通道先验算法在处理图像的天空区域时容易出现颜色过饱和、亮度整体偏暗和光晕等问题,提出了一种融合亮度模型和梯度域滤波的图像去雾算法。首先,选择整幅图像中亮度最大的前0.1%像素的平均值作为大气光值;然后,利用自适应最小值滤波的改进暗通道模型和亮度模型分别对前景区域和天空区域求解透射率,在将其加权融合得到粗透射率的基础上,使用梯度域导向滤波对透射率进行细化;最后,通过大气散射模型和伽马校正复原
灰狼优化算法在优化后期易陷入局部最优,在求解高维函数时因其复杂度更高,陷入局部最优概率更大,针对上述问题提出基于醉汉漫步和反向学习的混合灰狼优化算法(DGWO)。在迭代过程中对每代种群中优势狼与最差狼进行反向学习并进行比较、重新排序后保留前3的狼,同时将采用醉汉漫步机制更新领导狼,参数A和C采用系数标量而不是GWO原始算法中的系数向量。通过10个标准测试函数(100维、500维和1000维)以及10维的CEC2013测试函数验证了算法的性能,并与PSO、GWO-CS和GWO算法进行了比较,结果表明,该混合
传统方法在进行异构数据库强制访问控制时,未有效控制授权时间,存在系统占用率过高、访问控制准确性差、授权正确率问题。提出一种量化行为的异构数据库强制访问控制方法解决以上问题。建立用户访问权限关系,根据用户内部角色初步判断是否允许操作;采用量化行为方法对用户的信任度与用户行为的信任度进行量化,定量主体行为属性,并评价访问情况的安全等级,实现了异构数据库强制访问控制。实验结果表明,此次研究的异构数据库强
行人再识别是在不同环境下再次对特定行人进行检索,近几年来受到国内外学者的广泛关注。目前行人再识别算法多采用局部特征与全局特征相结合的方法,在单一数据集上的训练和测试取得了非常好的成绩,但是在跨域测试中成绩并不理想,泛化能力较低。提出一种基于深度胶囊网络的跨域行人再识别方法,通过视角分类训练任务,模型可以学习图像中行人的有效特征,这些特征可以直接迁移到行人再识别任务中,缓解了行人再识别泛化能力不足的
针对工业生产中的PCB图像边缘信息缺失且携带有大量噪声,现有去噪算法效果不佳、计算量庞大、复杂度高等问题,提出了一种基于改进NLM的PCB图像去噪算法,旨在提高PCB图像的去噪质量。首先,采用基于形态学的权重自适应算法对PCB图像进行图像增强,使PCB图像保留较好的边缘信息;其次,引入特征匹配模型对增强后的PCB图像与原始PCB图像进行特征点匹配融合;最后,通过改进NLM算法的权重值对PCB图像进
基于k-最近邻(kNN)的分类方法是实现各种高性能模式识别技术的基础,然而这些方法很容易受到邻域参数k的影响,在完全不了解数据集特性的情况下想要得出各种数据集的邻域是比较困难的。基于上述问题,介绍了一种新的监督分类方法:扩展自然邻居(ENaN)方法,并证明了该方法在不人为选择邻域参数的情况下提供了一种更好的分类结果。与原有的基于kNN需要先验k的方法不同,ENaN方法在不同的阶段预测不同的k值。因此,无论是在训练阶段还是在测试阶段,ENaN方法都能从动态邻域信息中学习到更多的信息,从而提供更好的分类结果。
针对传统语言模型的词向量表示无法解决多义词表征的问题,以及现有情感分析模型不能充分捕获长距离语义信息的问题,提出了一种结合BERT和BiSRU-AT的文本情感分类模型BERT-BiSRU-AT。首先用预训练模型BERT获取融合文本语境的词向量表征;然后利用双向简单循环单元(BiSRU)二次提取语义特征和上下文信息;再利用注意力机制对BiSRU层的输出分配权重以突出重点信息;最后使用Softmax激励函数得出句子级别的情感概率分布。实验采用中文版本的推特数据集和酒店评论数据集。实验结果表明,结合BERT和B