【摘要】 本文对Wong和Morris提出的一种基于划分搜索空间的局部搜索多初始点选择的新策略—划分策略进行了严格的理论分析．文中定义了划分类的均匀性偏序关系，定义了划分类的平均划分性能和最坏划分性能两个性能标准，证明了对于任一个实例，划分类越均匀，相应的初始点策略性能就越好，给出了作为最优划分策略的均分策略的性能上下界，完整彻底地解决了对划分策略的评价问题．更多还原

【Abstract】 This paper gives a thorough theoretical analysis of a new approach to choosing multipleinitial points in local search, namely, the partition--based strategy proposed by Wong and Moms in1989. First, a partial order in partition types and two performance measures of the partition--basedinitial point strategy, i. e., the expected and the worst performance of a partition type, are defined.Second, it is proved that on any instance, the more uniform the partition type, the better theperformance of the corresponding initial point strategy. Third, the lower and upper bounds to theperformance of initial point strategy based on the even partition type, the best of the kind, are given. Itis concluded that the partition--based strategy is not a promising approach to choosing multiple initialpoints in local search.更多还原