摘要：极小不可满足子式能够为可满足性模理论(SMT)公式的不可满足的原因提供精确的解释,帮助自动化工具迅速定位错误.针对极小SMT不可满足子式的求解问题,提出了SMT公式搜索树及其3类结点的概念,并给出了不可满足子式、极小不可满足子式与3类结点之间的映射关系.基于这种映射关系,采用宽度优先的搜索策略提出了宽度优先搜索的极小SMT不可满足子式求解算法.基于业界公认的SMT Competition2007测试集进行实验的结果表明,该算法能够有效地求解极小不可满足子式.

摘要：本文通过研究AI领域中常用的状态空间法,结合特定规则下逻辑推理问题(LIBFR)的具体特征,建立了相应的状态空间表示模型。在此基础上分析设计了此类逻辑问题的宽度优先搜索算法,并借助开发工具VC++6.0和SQLServer2000在WindowsXP系统下结合数学软件Matlab6.0编程实现。

摘要：图作为一种灵活表达对象之间关系的数据结构,广泛地应用于各类重要的现实场景.近年来,随着性能提升速度放缓,通用处理器逐渐无法满足图计算应用的需求,并成为限制图计算发展的主要瓶颈.因此,面向图计算的领域专用加速器成为近年来的研究热点.通过定制化的硬件设计,图计算加速器可以在图计算应用中取得通用处理器数十倍的性能.然而,现有的图计算加速器在运行宽度优先算法时会频繁地重复访问幂律顶点的相关数据,进而导致了严重的冗余访存问题.在特定场景下,现有的图计算加速器的性能甚至低于通用CPU.为了解决该问题,本文提出一种冗余感知的高能效图计算加速器JiFeng.当幂律顶点完成迭代计算时,JiFeng通过跳过剩余的相邻边大幅减少其被重复访问的次数.JiFeng实现了一系列软硬件协同设计,在保证负载均衡的同时提升硬件的执行效率.为了验证JiFeng的有效性,本文采用FPGA原型系统对相关设计进行性能评估.JiFeng在典型的生成图和现实图上实现最高每秒遍历4612亿条边的性能和每秒每瓦特遍历125亿条边的能效比,并在2023年11月的图计算超算排行榜GreenGraph500的小数据集榜单上取得第2名的成绩.

摘要：为了提高基于蒙特卡罗(Monte Carlo)方法的供水管网抗震可靠性分析效率,以低偏差Sobol点列替代伪随机数序列对供水管网节点和管段破坏概率进行抽样,结合宽度优先搜索算法,提出基于拟Monte Carlo方法和统一计算设备架构(CUDA)的供水管网抗震可靠性分析并行算法,并从内存、执行配置和指令等方面优化并行算法.以某城市供水管网系统为例,对比串行和并行计算方法的精度及效率,分析Sobol点列和伪随机数序列对管网可靠性分析的影响.结果表明,并行和串行方法计算结果的误差最大为0.52%,并行方法最高加速比为串行算法的96倍,在保证结果精度的同时大幅度提高计算效率.基于Sobol点列进行1000次并行模拟及基于伪随机数序列进行5000次并行模拟,2种模拟结果与基于模糊数学法的解析值的最大误差分别为0.2%、0.4%,表明基于拟Monte Carlo的并行方法具有更高的精确度,更快的收敛速度.

摘要：舰艇生命力分析是指根据当前船体和装备的损伤状态,计算舰艇生命力指标值及对应的损伤等级,是进行生命力评估的关键一步。技术设计阶段,舰艇生命力评估对象较多,评估对象之间的功能逻辑关系呈现复杂的网络状,因此以往方案设计阶段使用的损伤树分析方法将不再适用。针对该问题,首先分析了技术设计阶段生命力分析模型的构成,它包含3类分析模型;然后,使用图模型和宽度优先搜索算法构建了第1类分析模型;使用功能树模型构建了第2类分析模型;使用组合合成原则描述了第3类分析模型;最后,通过案例说明了上述分析方法的实用性。该分析方法具有较强的通用性,标准化程度高,为生命力评估系统的模块化开发奠定了理论基础。

摘要：针对日益突出的网页访问问题,设计了一种新型分布式WebSpider。该分布式WebSpider采用中央控制节点来协调各个webspider的行为,利用宽度优先搜索来获得高质量的网页,通过对DNS缓存来提高访问webserver的速度,以增加并行线程数量的方式来增加网页下载速度,并能动态地加入webspider节点和子中央控制节点,具有很强的灵活性和扩张能力。实验结果表明该分布式WebSpider作为搜索引擎的前端能够快速有效地下载网页,具有较好的性能。

摘要：为解决解码过程中存在误删正确解码路径概率较高、解码速度较慢的问题,提出一种基于深度优先搜索的分布式算术码(distributed arithmetic coding,DAC)解码算法。综合考虑码流内在特性、码流外在特性及解码路径长度等因素对解码路径权重的影响,得到新的路径权重计算公式;用部分搜索代替全局搜索,减少算法的搜索量。将该算法用于生物信息安全认证系统,仿真结果表明,该算法比传统基于宽度优先搜索的算法具有明显的优越性。

摘要：为降低进行文档搜索时对系统资源的占用,提出了一种实现对主机内文档进行快速高效搜索的方法,采用基于宽度优先非递归搜索算法实现对主机内文档的遍历搜索;采用基于改进的BF算法和改进的KMP算法分别进行文档名和文档关键词匹配;采用降低线程优先级和定时暂停程序的方法控制搜索效率;采用压缩存储的方法对搜索结果进行处理。设计并实现了原型系统,测试结果表明,系统具有较高的准确率和召回率,且对主机内存、CPU、硬盘等资源占用少,降低了在进行文档搜索时对计算机其他进程的影响。

摘要：针对八数码求解问题,对宽度优先搜索算法进行分析,在VS2008开发环境下,设计并实现了解决八数码难题的BSF算法。实验结果表明,BSF算法具有可获取最优解的优点。

摘要：舰艇消防系统战时受损后,快速准确地对其消防能力进行评估是制定损管方案的基础.文中使用数学中的"图",对舰艇消防系统进行了数学建模;设计了消防能力智能评估算法和抢修方案智能化生成算法;在VB编程环境下建立了消防能力智能化评估及智能抢修决策系统,提高了评估和决策的速度和精度.