第07章限界剪枝法-课件（PPT·精·选）.ppt

《算法设计与分析》第 07 章限界剪枝法第 07 章限界剪枝法基本思想?限界剪枝法与回溯法相似,也是对状态空间树进行搜索求解,不同的是限界剪枝法的求解目标是要找到使得某一目标函数极大或极小的一个解结点,即某种意义下的最优解。?在算法设计上,限界剪枝法不仅通过约束条件来控制搜索路径,还通过目标函数的限界来减少搜索规模; 限界剪枝法在搜索时,通常先进行广度扩展,将满足约束条件且不越过目标函数的子结点加入到活结点表中等待搜索; ?常见的活结点表有队列式( FIFO )、栈式( LIFO ) 和优先队列式( PQ ); 第 07 章限界剪枝法限界剪枝法?最小耗费搜索法?求解以定义在状态空间树 T的解结点集 A上的耗费函数为目标函数的最优问题,即求解 A中耗费最小的解结点。?设A中的结点 x所需的耗费为 D(x) ,在 T上构造耗费函数: C(x ) = min{D(y)| y ∈T x∩A } T x∩A≠{} C(x ) = ∞T x∩A = {} T x表示以 x为根的子树; 易见,子结点的耗费函数值不小于父结点的耗费函数; ?理想情况下,以耗费值作为优先级建立优先队列,按优先顺序扩展搜索,就可以很快找到具有最小求解耗费的解结点; ?然而在实际情况中,通常是求解过程中才能得到求解的耗费,因此可以采用一个耗费的估计值~C(x) 作为 C(x) 的近似解; 第 07 章限界剪枝法限界剪枝法?最小耗费搜索法?最小耗费搜索法的算法描述?设T为状态空间树的根结点; ~C(x) 为耗费估计函数;初始化优先队列 Q; ?计算~C(T) ,并将 T入队; ?循环,直到队列 Q空(无解): ?结点 e出队; ?若e是回答结点,则?输出解或求解路径,求解结束; ?否则?检查 e的所有子结点 x: ?若x满足约束条件,则?计算~C(x) ,并将 x入队; ?记录搜索路径; ?当~C(x) 满足: ~C(x) ≤ C(x) , C(x) 单调,解结点的~C(x)=C(x) 时,上述算法可以正确找到 C(x) 的最小耗费解; 第 07 章限界剪枝法限界剪枝法?最小耗费搜索法? 15 迷问题?用布局作为问题状态,用空格的移动来表述状态的演化; ?用根结点到解结点的路径长度作为耗费函数; ?而用根到当前结点的路径长度加上当前结点与目标解的差异量作为耗费估计函数; 13 10 98 14 11 67 12 52 15 431 15 14 13 12 11 10 9 8765 4321 第 07 章限界剪枝法限界剪枝法?最小耗费搜索法? 15 迷问题?布局结构描述?布局结点不仅包括数字位的分布情况,还包括已经推演的步数和与目标布局的差异,以及指向父结点的指针。?算法描述?初始化集合 S={} ,记录曾经出现过的布局; ?初始化优先队列 Q,以布局的~ C(x )作为权值; ?起始布局入队,并记入 S; ?循环,直至队列空?布局 T出队; ?若T为目标布局,则从 T倒推出移动步骤,求解结束; ?将T的所有未处理的可推演布局入队,并记入 S; 第 07 章限界剪枝法限界剪枝法?限界与剪枝?在解结点集合上定义目标函数 F(x ),求解解结点集上的离散最优化问题; ?类似最小耗费搜索法,定义耗费函数 C(x) : C(x ) = min{D(y)| y ∈T x∩A } T x∩A≠{} C(x ) = ∞T x∩A ={} C(x )为单调非减函数; ?同样地,由于 C(x) 无法做即时计算,引入估值函数~C(x) ,满足条件: ~C(x) ≤ C(x) ; 对解结点 x, ~C(x) = C(x) ; 第 07 章限界剪枝法限界剪枝法?限界与剪枝?为了进一步避免无效搜索,若能找到最优解的耗费上界 U,即对于最优解结点 x*,有 C(x *)≤U,则: 在进行最小耗费搜索时,对于待展开的状态结点 y,若~C(y)>U ,则由 C(x) 的单调性和~C(x) 是 C(x) 的下界可知: U<~ C(y) ≤ C(y) ≤ C(x ) x 为解结点即,在 y的子树中不会包含所要求的最优解结点 x*,因而可以放弃对该子树的搜索。第 07 章限界剪枝法限界剪枝法?限界与剪枝?基于以上思想,引入耗费函数的上界函数 u(x) , 满足: ~C(x) ≤ C(x) ≤ u(x) ;和当前最小上界值 U; ?初始时令 U=u(T) ,T为起始结点; ?在符合约束条件的结点 x入队前,检查,若~C(x)>U ,则该结点不入队(不激活); ?在结点 x入队时,检查,若 u(x)<U ,则用 u(x) 更新 U(使 U动态单调下降); ?在活动结点 x出队后,检查,若~ C(x )>U ,则不须对x进行扩展,避免无效搜索; 第 07 章限界剪枝法限界剪枝法?限界与剪枝?限界剪枝