宽度优先反复加宽及其启发式搜索算法研究

首先针对搜索树中深度固定且目标唯一的寻优问题，指出宽度优先反复加宽的搜索效率要比深度优先反复加深的搜索效率高，基于此，提出了基于宽度优先反复加宽的启发式搜索算法ＩＷＡ＊，算法ＩＷＡ＊是可采纳的。为了保持算法ＩＷＡ＊的搜索效率高于算法ＩＤＡ＊的搜索效率，同时又使算法ＩＷＡ＊的存贮空间复杂度减低，文中基于分层技术，提出了基于深度优先的ＩＷＡ＊算法──ＩＤＷＡ＊。算法ＩＤＷＡ＊也是一个可采纳的启发式搜索算法。     

多因素问题的启发式搜索算法MFRA

本文新定义了一类多因素启妇式搜索问题，提出了适于此类问题求解的启发式搜索算法ＭＦＲＡ。文中研究了算法ＭＦＲＡ的可采纳性质，单调限制性质和比较性质等。基于算法ＩＤＡ的思想，提出了ＭＦＲＡ的改进算法ＭＦＲＡ－ＩＤＡ，这一算法具有线性存储空间这一重要特性。     

P＋P：同步时序电路的并行码和并行故障模拟器

开发的一个新的快速故障模拟器Ｐ＋Ｐ。该模拟器使用了并行码与并行故障模拟算法，实现了同步时序电路故障模拟的两路并行性，采用了全局故障分组，锥形操作，电路级化及改进的组号ＩＤ等技术。Ｐ＋Ｐ已在ＳＵＮ ＳＰＡＲＣ－２工作站上实现，运行了大部分的ＩＳＣＡＳ Ｂｅｎｃｈｍａｒｋ同步时序电路。最后给出了实验结果。     

基于自适应分类的学习搜索算法

本文给出一放弃可采纳性的分类式学习搜索算法ＳＡＬＳ，它在系统初建时就能快速地获取经验知识，该算法的空间复杂度和平均时间复杂度皆为所获解路径耗费值的线性函数。将反复加深技术运用于ＳＡＬＳ而得到的搜索算法ＩＤ－ＳＡＬＳ，在保持良好的时间和空间复杂度的同时，又能保证找到的解为次优解。文中最后给出了ＩＤ－ＳＡＬＳ的两点改进。     

Constructing M-sided Patches with NURBS

ＣＯＮＳＴＲＵＣＴＩＮＧＮ－ＳＩＤＥＤＰＡＴＣＨＥＳＷＩＴＨＮＵＲＢＳＷａｎｇＬａｚｈｕ；ＺｈｕＸｉｎｘｉｏｎｇＣＯＮＳＴＲＵＣＴＩＮＧＮ－ＳＩＤＥＤＰＡＴＣＨＥＳＷＩＴＨＮＵＲＢＳ￥ＷａｎｇＬａｚｈｕ；ＺｈｕＸｉｎｘｉｏｎｇＡｂｓｔｒａｃｔＴｈｅｐ...     

广义AND／OR图的自底向上的启发式搜索算法BHAO

本文首先根据三角模概念，定义了一类新的更具普遍意义的广义ＡＮＤ／ＯＲ图．根据新定义的启发式函数ｈ（ｎ，ｘ）以及广义ＡＮＤ／ＯＲ图的最佳解树之所有子树亦是最佳子解树的原理，提出了广义ＡＮＤ／ＯＲ图的自底向上的启发式搜索算法ＢＨＡＯ．文中证明了算法ＢＨＡＯ的可采纳性．本文还提出了两类新的启发式函数的单调限制概念，并据此研究了算法ＢＨＡＯ的单调限制性质，研究了两个ＢＨＡＯ算法间的比较性质．     

SUPERBASE：一个CIM环境下面向对象的多数据库集成系统

ＳＵＰＥＲＢＡＳＥ是一个ＣＩＭ环境下面向对象的多数据库集成系统，其目标是有效地集成分布在多个已存在的自治和异构的局部数据库中的信息，以实现各系统间的信息共享。本文首先介绍了ＳＵＰＥＲＢＡＳＥ的体系结构、模式集成机制；然后讨论了全局数据库和局部数据库间的数据副本问题，提出了相应的解决方法；最后给出了集成数据模型ＩＤＭ和集成数据语言ＩＤＬ。     

MIDS／BUAA的模式管理器与对象管理器的设计

本文首先回顾了ＭＩＤＳ／ＢＵＡＡ总体设计中相关的部分重要内容，ｕｎｉｖＯｂｊｅｃｔ对象定义，持久性规则、库模式和ＭＩＤＳ的功能构成等。然后重点介绍了ＭＩＤＳ／ＢＵＡＡ中两个核心模块；模式管理器ＳＭ和对象管理器ＯＭ的思想，基本任务和实现途径；最后给出了ＭＩＤＳ／ＢＵＡＡ类库的层次结构。     

模糊－PID控制器的计算机辅助设计

模糊－ＰＩＤ控制器的计算机辅助设计熊聪聪，白瑞林ＳｔｕｄｙｏｎｔｈｅＣＡＤｏｆｔｈｅＦｕｚｚｙ—ＰＩＤＣｏｎｔｒｏｌｌｅｒ￥ＸｉｏｎｇＣｏｎｇｃｏｎｇ；ＢａｉＲｕｉｌｉｎｌ引言模糊控制器与ＰＩＤ、自适应等控制器不同．它的控制规则是产生式的模糊语言规则...     

一类流体力学程序的向量化与并行化

一类流体力学程序的向量化与并行化袁国兴，张宝琳（北京应用物理与计算数学研究所）ＰＡＲＡＬＬＥＬＩＺＡＴＩＯＮＦＯＲＳＯＭＥＴＷＯ－ＤＩＭＥＮＳＩＯＮＡＬＦＬＵＩＤＤＹＮＡＭＩＣＡＬＰＲＯＧＲＡＭＳ￥ＹｕａｎＧｕｏｘｉｎｇ；ＺｈａｎｇＢａｏｌｉｎ（Ｉｎ...     

Two-agent IDA*

The article presents an algorithm that combines Minimax's alpha-beta pruning with IDA*'s depth-first iteration and forward pruning. We prove that the algorithm, which we call Two - agent IDA* (TIDA*), is correct and is guaranteed to terminate—provided its heuristic is consistent. Minimax search has been applied with other ‘forward’ pruning or selective search techniques, but none of these techniques is guaranteed to compute the correct minimax result. We also prove that TIDA*'s accuracy monotonically increases with search depth, thus avoiding certain pathologies. Empirical results with 3×3, 4×4 and 5×5 Tic-Tac-Tff grids show that TIDA* outperforms MAB, provided both algorithms use the same consistent heuristic. However, results on a more complex search space—the 3D version of Tic-Tac-Tff—show that MAB with a good inconsistent heuristic can outperform TIDA* with a consistent heuristic even though TIDA* searches 1 to 1·5 levels deeper. This result and other empirical results suggest that an algorithm that starts with MAB and an inconsistent heuristic and then shifts near the end of the game to TIDA* with a consistent heuristic can outperform either algorithm. Finally, we present results on a forward-pruning version of MAB and show that under certain conditions it can outperform TIDA*, provided both use the same consistent heuristic.     

Depth-First Branch-and-Bound versus Depth-Bounded IDA: New Results

In a real-time task an action must be executed given limited computation. One approach to limited computation is to search a tree of possible action sequences to a fixed depth and then execute an action with the lowest associated backed-up cost. The standard algorithm for such a search is Depth-First Branch-and-Bound (DFBB), also known in the Artificial Intelligence literature as Minimin with Alpha Pruning . This article shows that a depth-bounded extension of a popular iterative algorithm called IDA has a surprisingly large range of search trees on which it outperforms DFBB—something previous analytical results do not predict. We prove that the extended algorithm, which we call DIDA , is correct, is guaranteed to terminate, and is asymptotically (i.e., on its last iteration) as efficient as DFBB—assuming a consistent heuristic is used. We also prove that both algorithms are guaranteed not to decrease their accuracy with a deeper search, assuming a consistent heuristic. Because accuracy is generally correlated with decision quality, the time saved by visiting fewer states translates to deeper searches which translates to better decisions. Results from random search trees show that DIDA is most efficient when the path cost + leaf node heuristic value is distributed with low variance; as branching factor increases, the range for which DIDA is more efficient also increases. Results with Eight, Fifteen, Twenty-four, and Ninety-nine Puzzle implementations of both algorithms—all domains with low variance of path cost + leaf node heuristic value—show that DIDA significantly outperforms DFBB.     

A SIMD approach to parallel heuristic search

Serial search algorithms often exhibit exponential run times and may require an exponential amount of storage as well. Thus, the design of parallel search algorithms with limited memory is of obvious interest. This paper presents an efficient SIMD parallel algorithm, called IDPS (for iterative-deepening parallel search). At a broad level IDPS is a parallel version of IDA*. While generically we have called our algorithm an IDPS, performance of four variants of it has been studied through experiments conducted on the well-known test-bed problem for search algorithms, namely the Fifteen Puzzle. During the experiments, data were gathered under two different static load balancing schemes. Under the first scheme, an unnormalized average efficiency of approximately 3/4 was obtained for 4K, 8K, and 16K processors. Under the second scheme, unnormalized average efficiencies of 0.92 and 0.76, and normalized average efficiencies of 0.70 and 0.63 were obtained for 8K and 16K processors, respectively. We show (as shown previously only for MIMD machines) that for admissible search, high average speedup can be obtained for problems of significant size. We believe that this research will enhance AI problem solving using parallel heuristic search algorithms.     

PRA*: Massively Parallel Heuristic Search

In this paper we describe a variant of A* search designed to run on the massively parallel, SIMD Connection Machine (CM-2). The algorithm is designed to run in a limited memory by the use of a retraction technique which allows nodes with poor heuristic values to be removed from the open list until such time as they may need reexpansion, more promising paths having failed. Our algorithm, called PRA* (for Parallel Retraction A*), is designed to maximize use of the Connection Machine′s memory and processors. In addition, the algorithm is guaranteed to return an optimal path when an admissible heuristic is used. Results comparing PRA* to Korf′s IDA* for the fifteen puzzle show significantly fewer node expansions for PRA*. In addition, empirical results show significant parallel speedups, indicative of the algorithm′s design for high processor utilization.     

基于遗传算法车间流控制中调度问题的研究

提出了实现车间调度的混合遗传算法的设计方案，把经典的启发式算法、自适应算法与遗传算法相结合，将启发式搜索运用于初始种群的生成，充分发挥遗传算法良好的全局搜索能力和启发式搜索结构简单搜索速度快的特性，采用自适应方法改进交叉概率与变异概率，并通过实验验证了算法的有效性、     

一类基于启发式搜索的激励学习算法

激励学习已被证明是在控制领域中一种可行的新方法。相比其他的方法,它能较好地处理未知环境问题,但它仍然不是一种有效的方法。幸运的是,在现实世界中,智能体总是会有一些环境的先验知识,这些能形成启发式信息。启发式搜索是一种常用的搜索方法,有很快的搜索速度,但需要精确的启发式信息,这在有些时候难以得到。文中分析比较了启发式搜索和激励学习的各自特点,提出一类新的基于启发式搜索的激励学习算法,初步的实验结果显示了较好的性能。     

基于启发式Bi-RRT算法的虚拟手臂运动规划

为提高虚拟人手臂在复杂多障碍物空间进行维修时的运动路径规划效率,提出一种基于启发式Bi-RRT的路径规划算法。在运用Bi-RRT算法的基础上,结合启发式搜索思想对腕关节进行路径规划,通过比较多个随机搜索点与目标点的距离,保留距离目标点最近的随机搜索点,使随机树有方向地进行扩展,减少无效的搜索。仿真实验结果表明,启发式Bi-RRT算法较传统的RRT算法和Bi-RRT算法有更好的搜索效果,搜索效率更高,对于7自由度虚拟手臂的运动路径规划也有较好的效果。     

两级定位-路径问题的变邻域人工蜂群算法

建立了两级定位-路径问题的数学模型,提出了一种求解该问题的人工蜂群算法。针对该算法容易出现早熟现象,将近年来国外出现的一种新颖的轨迹式启发式算法--变邻域搜索融入其中,由此提出三种变邻域搜索策略。基于不同变邻域搜索策略的人工蜂群算法和人工鱼群算法的求解效果进行对比仿真。实验结果表明,变邻域人工蜂群算法能有效求解两级定位-路径问题。