论文部分内容阅读
状态空间搜索是解决优化问题的常用方法之一，传统的状态空间搜索求解技术有回溯法和分支限界法以及隐式图搜索这些算法策略作为理论指导。这些策略的缺点是不够具体化，对每个特定问题我们都必须设计单独的算法，设计和实现这些算法是一件繁重的工作，算法的正确性和效率很难得到保证。本文提出了将优化问题归结为状态空间最优化搜索问题的数学模型和通用算法，将传统的在显式图中求最短路的Dijstra算法与隐式图的优化搜索，隐式图搜索与隐式树搜索全部统一到同一个模型和算法中去。本文的一个重要意义是将回溯法和分支限界法这两个传统的算法策略转变为本文所提出的通用搜索算法的应用例子。这样，算法设计的五大策略可以减少到分治、贪心和动态规划三个策略，一大批复杂优化问题的算法设计与实现可以得到本质的简化。