现在的位置: 首页 > 综合 > 正文

回溯法1–算法框架

2018年04月03日 ⁄ 综合 ⁄ 共 749字 ⁄ 字号 评论关闭
    回溯法有“通用解题法”之称。用它可以系统的搜索问题的所有的解。它既是一个类似蛮力法的系统算法,即所有的情况都考虑的到。同时它也是一个带有跳跃性的搜索算法,它可以在搜索的过程中排出一些不可能的解,提高搜索效率。
    基本思想:它在问题的解空间树中案深度优先策略,从根节点出发搜索空间数。算法搜索至解空间的任一节点时,先判断此节点下是否可能包含问题的解。如果不可能就跳过此节点,搜寻下一个节点。如果可能,则进入该子树搜索策略(即递归)。当到达叶子结点时,如果是解,则记录下来。然后回溯。(这里将在下面的伪代码中看到具体的过程)
   

int *x;//当前的解方案
int *bestx;//最优的解方案
int v;//当前的目标值
int bestv;//最优的目标值
void BackTrack(int i)
{
	if(i > n)//到达叶子结点
	{
		v=value(x); //计算当前的目标值
		if(v > bestv)//找到一个最优的目标值
		{
			bestx = x;
			bestv = v;
		}
	}
	else if() //解空间是排列数,如旅行售货员问题
	{
		for(int j=i; j <= n; j++)//排列组合各种可能方案
		{
			swap(x[i],x[j]);
			if()//可能存在解
			{
                BackTrack(i+1);
			}
			
			swap(x[i],x[j]);
		}
	}
	else//解空间是子集树,如0-1背包问题
	{
		for(int j=i; j <= n; j++)//排列组合各种可能方案
		{
			x[i] = 0;
			if()//可能存在解
			{
                BackTrack(i+1);
			}
			x[i] = 1;
			if()//可能存在解
			{
                BackTrack(i+1);
			}
		}
		
	}
}

  在回溯法中,如求解问题的所有解时,要回溯到根,且根节点的所有子树都被搜索到。若是只是求解一个解时,只要搜索到问题的一个解时,即可结束遍历。

抱歉!评论已关闭.