精华内容
下载资源
问答
  • 关于装箱问题算法研究

    千次阅读 2021-04-15 20:15:21
    装箱问题算法研究 山东大学 赵一帆 问题描述 在箱子装载问题中,有若干个容量为c的箱子和n个待装载入箱子中的物品。物品i需占s[i]个单元(0<s[i]≤c)。所谓成功装载(feasible packing),是指能把所有物品都...

    装箱问题的算法研究

    山东大学 赵一帆

    问题描述

    在箱子装载问题中,有若干个容量为c的箱子和n个待装载入箱子中的物品。物品i需占s[i]个单元(0<s[i]≤c)。所谓成功装载(feasible packing),是指能把所有物品都装入箱子而不溢出,而最优装载(optimal packing)则是指使用了最少箱子的成功装载。

    问题分析

    这道题目是算法课设发给我要求完成的题目,给了四种基本的算法,再加上avl树和竞赛树优化(竞赛树那部分我写的还是有点满意),后续我感觉可以用模拟退火来做一下,所以就搜集资料尝试了一下,之后百度百科说遗传算法也可以做,所以就自己想象凭空捏造了一波遗传算法,欢迎指出不足点。
    其实这两种思路都是有更有目标和优化的搜索而已。

    模拟退火思路

    每次交换50个rand()对,如果替换结果就保留这个交换,否则不保留,不停在函数上面溜达,其实我也不知道这个函数长什么样子。

    遗传算法思路

    之前没有搞过这个算法,先学的,感觉很多二手博客非常不尊重达尔文同志的思想,强行忽略了遗传中很多的步骤,也有可能是他们生物没有学的很好,所以我加上了染色体交叉互换的环节,一共有n*(n/32)个染色体,每个染色体上面有32个基因,每个基因表示i和j是否进行交换,1表示为显性,0表示为隐形,这样空间最多可以表达<1000的数量,可惜最后进化效果并不是很好,大概进化的时间还是太短了,或者说这道题本身可能就不是很适合进化,因为箱子的交换有可能会走向好的方向,但是保留之后并不能显然的确定会向更好的方向进行移动。

    性能分析

    可以发现我写的退火算法和遗传算法确实不咋地,有时间再改进改进把,但是实际上我感觉真的挺难优化的。

    大物品情况:
    答案:
    源数据1答案
    运行时间:
    源数据1时间复杂度
    1000物品
    时间比对
    时间比对
    中等物品情况下:
    答案:
    答案
    运行时间:

    中物品
    时间对比1
    时间对比2
    小物品:
    答案:
    答案
    运行时间:
    时间

    优化
    小物品
    小物品

    模拟真实数据:

    代码分析

    void FF()
    {
    	LL startTime = clock();
    	int hasNumber = 0;
    	for(int i = 1;i <= n;++i)	
    	{
    		bool flag = false;
    		for(int j = 1;j <= hasNumber&&!flag;++j)
    		{
    			if(c_has[j] >= s[i]) 
    			{
    				c_has[j] -= s[i];
    				flag = true;
    			}
    		}
    		if(!flag) c_has[++hasNumber] = c - s[i];	
    	}
    	cout<<"最先匹配法耗时"<<clock()-startTime<<"毫秒,";
    	cout<<"消耗箱子"<<hasNumber<<"个"<<endl; 
    }
    
    int FFCT(int mode)	//竞赛树做法 
    {
    	LL startTime = clock(),hasNumber = 0;
    	for(int i = 1;i <= 2*n;++i) cmt[i] = c;
    	for(int i = 1;i <= n;++i)
    	{
    		int x = 1;
    		while(x < n) {
    			if(cmt[x * 2] >= s[i]) x = x * 2;
    			else x = x * 2 + 1;
    		}
    		cmt[x] -= s[i];
    		while(x > 1) {
    			x = x/2;
    			cmt[x] = max(cmt[x*2],cmt[x*2 + 1]);
    		}
    	}
    	for(int i = n;i <= 2 * n - 1;++i) 
    		if(cmt[i] != c) hasNumber++;
    	if(mode == 0)
    	{
    		cout<<"最先匹配(竞赛树优化)法耗时"<<clock()-startTime<<"毫秒,";
    		cout<<"消耗箱子"<<hasNumber<<"个"<<endl; 
    	}
    	return hasNumber;
    }
    
    
    void FFD()
    {
    	LL startTime = clock();
    	int hasNumber = 0;
    	for(int i = 1;i <= n;++i) s_max[i] = s[i];
    	sort(s_max+1,s_max+n+1,cmp);
    	for(int i = 1;i <= n;++i)	
    	{
    		bool flag = false;
    		for(int j = 1;j <= hasNumber&&!flag;++j)
    		{
    			if(c_has[j] >= s_max[i]) 
    			{
    				c_has[j] -= s_max[i];
    				flag = true;
    			}
    		}
    		if(!flag) c_has[++hasNumber] = c - s_max[i];	
    	}
    	cout<<"最先匹配递减法耗时"<<clock()-startTime<<"毫秒,";
    	cout<<"消耗箱子"<<hasNumber<<"个"<<endl; 
    }
    
    
    void FFDCT()	//竞赛树做法 
    {
    	LL startTime = clock(),hasNumber = 0;
    	for(int i = 1;i <= n;++i) s_max[i] = s[i];
    	sort(s_max+1,s_max+n+1,cmp);
    	for(int i = 1;i <= 2*n;++i) cmt[i] = c;
    	for(int i = 1;i <= n;++i)
    	{
    		int x = 1;
    		while(x < n) {
    			if(cmt[x * 2] >= s_max[i]) x = x * 2;
    			else x = x * 2 + 1;
    		}
    		cmt[x] -= s_max[i];
    		while(x > 1) {
    			x = x/2;
    			cmt[x] = max(cmt[x*2],cmt[x*2 + 1]);
    		}
    	}
    	for(int i = n;i <= 2 * n - 1;++i) 
    		if(cmt[i] != c) hasNumber++;
    	cout<<"最先匹配递减法(竞赛树优化)耗时"<<clock()-startTime<<"毫秒,";
    	cout<<"消耗箱子"<<hasNumber<<"个"<<endl; 
    }
    
    void BF()	//搜索获得大于其的最小值 
    {
    	LL startTime = clock();
    	int hasNumber = 0;
    	c_has[0] = 599999999;
    	for(int i = 1;i <= n;++i)	
    	{
    		int boxMark = 0;
    		for(int j = 1;j <= hasNumber;++j)
    			if(c_has[j] >= s[i] && c_has[j] < c_has[boxMark]) 
    				boxMark = j;
    		if(boxMark == 0)	c_has[++hasNumber] = c - s[i];
    		else 	c_has[boxMark] -= s[i]; 
    	}
    	cout<<"最优匹配法耗时"<<clock()-startTime<<"毫秒,";
    	cout<<"消耗箱子"<<hasNumber<<"个"<<endl; 
    }
    
    void BFBetter()	//使用平衡树获得大于其的最小值 
    {
    	LL startTime = clock();
    	int hasNumber = 0;
    	for(int i = 1;i <= n;++i)	
    	{
    		double findNum = find_down(rt,s[i]);
    		if(findNum < 1e8) 
    		{
    			del(rt,findNum);	//删除和插入耗时太多,所以当箱子空间小的时候 
    			Insert(rt,findNum-s[i]); //这个算法的复杂度反而会高 
    		}
    		else 
    		{
    			hasNumber ++;
    			Insert(rt,c-s[i]);
    		}
    			
    	}
    	cout<<"最优匹配法(结合平衡树)耗时"<<clock()-startTime<<"毫秒,";
    	cout<<"消耗箱子"<<hasNumber<<"个"<<endl; 
    }
    
    
    void BFD()	//搜索获得大于其的最小值 
    {
    	LL startTime = clock();
    	int hasNumber = 0;
    	c_has[0] = 599999999;
    	for(int i = 1;i <= n;++i) s_max[i] = s[i];
    	sort(s_max+1,s_max+n+1,cmp);
    	for(int i = 1;i <= n;++i)	
    	{
    		int boxMark = 0;
    		for(int j = 1;j <= hasNumber;++j)
    			if(c_has[j] >= s_max[i] && c_has[j] < c_has[boxMark]) 
    				boxMark = j;
    		if(boxMark == 0)	c_has[++hasNumber] = c - s_max[i];
    		else 	c_has[boxMark] -= s_max[i]; 
    	}
    	cout<<"最优匹配法递减耗时"<<clock()-startTime<<"毫秒,";
    	cout<<"消耗箱子"<<hasNumber<<"个"<<endl; 
    }
    
    
    void BFDBetter()	//使用平衡树获得大于其的最小值 
    {
    	LL startTime = clock();
    	int hasNumber = 0;
    	for(int i = 1;i <= n;++i) s_max[i] = s[i];
    	sort(s_max+1,s_max+n+1,cmp);
    	for(int i = 1;i <= n;++i)	
    	{
    		double findNum = find_down(rt,s_max[i]);
    		if(findNum < 1e8) 
    		{
    			del(rt,findNum);	//删除和插入耗时太多,所以当箱子空间小的时候 
    			Insert(rt,findNum-s_max[i]); //这个算法的复杂度反而会高 
    		}
    		else 
    		{
    			hasNumber ++;
    			Insert(rt,c-s_max[i]);
    		}
    			
    	}
    	cout<<"最优匹配递减法(结合平衡树)耗时"<<clock()-startTime<<"毫秒,";
    	cout<<"消耗箱子"<<hasNumber<<"个"<<endl; 
    }
    
    void Simulated()
    {
    	LL startTime = clock(),hasNumber = 0;
    	for(int i = 1;i <= n;++i) s_max[i] = s[i];
    	//sort(s+1,s+n+1,cmp);
    	int best = FFCT(1);int ans = best;
    	for(AT = 300;AT > eps;AT *= D) {
    		for(int i = 1;i <= n;++i) s_min[i] = s[i];
    		for(int i = 1;i <= 5;++i) 
    			swap(s[rand()%n+1],s[rand()%n+1]);
    		int now = FFCT(1);
    		best = min(best,now);
    		if(now < ans || exp((ans - now)/AT*600) > (double)rand()/RAND_MAX)  
    			ans = now;
    		else{
    			for(int i = 1;i <= n;++i) s[i] = s_min[i];
    		}
    			
    	}
    	cout<<"模拟退火+最先匹配递减法(竞赛树优化)耗时"<<clock()-startTime<<"毫秒,";
    	cout<<"消耗箱子"<<best<<"个"<<endl;	
    	for(int i = 1;i <= n;++i) s[i] = s_max[i];
    }
    
    //很多变量开的是unsinged int,请注意
    
    const int maxn = 1001;
    using namespace std;
    int T,n;double s[maxn],si[maxn],c;
    uint animal[46][maxn][36][2];double Value[maxn],cmt[maxn*2];
    void bir()	 
    {
    	for(int i = 1;i <= 30;i+=2)
    	{
    		int son = 30+(i+1)/2,t = (i+1)%2;
    		for(int j = 1;j <= n; ++j) 	
    			for(int k = 1;k <= (n/32)+1;++k)	//对于每一个染色体
    			{
    				int pos = rand() % 2;
    				animal[son][j][k][t] = animal[i][j][k][pos];
    				if(rand() % 2 == 0)	//染色体交叉 
    					for(int lapTimes = 1;lapTimes <= 9;++lapTimes)
    					{
    						int lapPos = rand() % 32 + 1;
    						int old = (animal[son][j][k][t]>>(lapPos - 1)) % 2;
    						int other = (animal[i][j][k][pos^1]>>(lapPos - 1)) % 2;
    						if(old != other) 
    							animal[son][j][k][t] = ((((animal[son][j][k][t]>>lapPos)<<1)
    								+ other )<<(lapPos - 1))+animal[son][j][k][t] % (1<<(lapPos - 1));
    					}
    				//染色体变异
    				for(int varTimes = 1;varTimes <= 4;++varTimes)
    				{
    					int varPos = rand() % 32 + 1;
    					animal[son][j][k][t] = ((((animal[son][j][k][t]>>varPos)<<1)
    						+ rand()%2 )<<(varPos - 1))+animal[son][j][k][t] % (1<<(varPos - 1));
    				}	 
    			} 
    	}
    }
    void clum(int x)
    {
    	for(int i = 1;i <= n; ++i) si[i] = s[i];
    	for(int j = 1;j <= n; ++j) 	
    		for(int k = 1;k <= (n/32)+1;++k)
    		{
    			int need = animal[x][j][k][0]|animal[x][j][k][1];//显性和隐形基因 
    			int times = 0,pos = (k-1)*32+times;
    			if(j >= pos||pos > n) continue;	//该部分基因无意义,不表达,减少训练次数 
    			while(++times <= 32)
    			{
    				if(need % 2 == 1) swap(si[j],si[pos]);
    				need >>= 1;
    			}
    		}
    	Value[x] = FFCT();
    	//cout<<Value[x]<<endl;
    }
    int rank[55],sel[55];
    void select()
    {
    	for(int i = 1;i <= 45;++i)
    		if(Value[i] == 0) clum(i); //进行计算 
    	
    	memset(sel,0,sizeof(sel));
    	for(int i = 1;i <= 45;++i) //获得从小到大排名
    	{
    		rank[i] = 0;
    		for(int j = 1;j <= 45;++j)
    		{
    			if(sel[j]) continue;
    			if(rank[i] == 0) rank[i] = j;
    			if(Value[j] < Value[rank[i]]) rank[i] = j;
    		}
    	}
    	//30次交换
    	for(int i = 1;i <= 45;++i)
    	{
    		int find = 0;
    		for(int j = 1;j <= 45&&find == 0; ++j)
    		{
    			if(rank[j] == i) find = j;
    		}
    		swap(Value[i],Value[find]);
    		for(int j = 1;j <= n; ++j) 	
    			for(int k = 1;k <= (n/32)+1;++k)
    			{
    				swap(animal[i][j][k][0],animal[find][j][k][0]);
    				swap(animal[i][j][k][1],animal[find][j][k][1]);
    			}
    	} 
    	for(int i = 31; i <= 45;++i) Value[i] = 0;
    }
    void solve()
    {
    	cin>>c>>n;
    	for(int i = 1;i <= n; ++i) scanf("%lf",&s[i]);
    	int startTime = clock();
    	for(int i = 1;i <= 30;++i) 
    		for(int j = 1;j <= n;++j)
    			for(int k = 1;k <= (n/32)+1;++k)
    				for(int p = 0;p < 2;++p)
    					animal[i][j][k][p] = ((uint)rand()<<17) +
    										 ((uint)rand()<<2) + (rand() % 4);
    	for(int tims = 1;tims <= 500 ;++tims)
    	{
    		bir();	//获得子代 
    		select(); //人为选择 
    	}
    	cout<<"遗传算法法耗时"<<clock()-startTime<<"毫秒,";
    	cout<<"消耗箱子"<<Value[1]<<"个"<<endl; 
    }
    
    展开全文
  • 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同。递归的解这些子问题,然后将各子问题的解合并得到原问题的解。 分治法所能解决的问题一般具有以下几个特征: ...

    算法设计与分析

    1、分治法

    分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同。递归的解这些子问题,然后将各子问题的解合并得到原问题的解。

    分治法所能解决的问题一般具有以下几个特征:
      1) 该问题的规模缩小到一定的程度就可以容易地解决
      2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。
      3) 利用该问题分解出的子问题的解可以合并为该问题的解;
      4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

    分治法的基本步骤:
    分治法在每一层递归上都有三个步骤:
      分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
      解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;
      合并:将各个子问题的解合并为原问题的解。

    平衡子问题:分治算法中,划分出的子问题的规模应基本一致  
    2、动态规划算法:

    动态规划:通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题最优子结构性质的问题。

    基本思想:若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。 通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量: 一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

    与分治法区别:动态规划算法与分治法类似,都使用了将问题实例归纳为更小的、相似的子问题,并通过求解子问题产生一个全局最优值的思路,但动态规划不是分治法:关键在于分解出来的各个子问题的性质不同。分治法要求各个子问题是独立的(即不包含公共的子问题),因此一旦递归地求出各个子问题的解后,便可自下而上地将子问题的解合并成原问题的解。如果各子问题是不独立的,那么分治法就要做许多不必要的工作,重复地解公共的子问题。动态规划与分治法的不同之处在于动态规划允许这些子问题不独立(即各子问题可包含公共的子问题),它对每个子问题只解一次,并将结果保存起来,避免每次碰到时都要重复计算
    问题特征:

    (1)最优子结构:当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质

    (2)重叠子问题:在用递归算法自顶向下解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只解一次,而后将其解保存在一个表格中,在以后尽可能多地利用这些子问题的解。

    算法步骤:

    (1)分析最优值的结构,刻画其结构特征;

    (2)递归地定义最优值;

    (3)按自底向上或自顶向下记忆化的方式计算最优

    (4)根据计算最优值得到的信息构造最优解
    3、贪心算法
    贪心选择性质的定义
    做出当前看来是最好的选择,
    根据贪心策略一步步选择最终导致最优解,也就是选择局部最优解,可得整体最优解
    (1)原理:在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

    (2)特性:贪心算法采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪婪法不要回溯。能够用贪心算法求解的问题一般具有两个重要特性:贪心选择性质和最优子结构性质。

    1)贪心选择性质

    所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素。贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。

    对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为:首先考察问题的一个整体最优解,并证明可修改这个最优解,使其以贪心选择开始。做了贪心选择后,原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择,最终可得到问题的整体最优解。其中,证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。

    2)最优子结构性质

    当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。

    (3)贪心算法与动态规划算法的差异:

    动态规划和贪心算法都是一种递推算法,均有最优子结构性质,通过局部最优解来推导全局最优解。两者之间的区别在于:贪心算法中作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解推导下一步的最优解,而上一部之前的最优解则不作保留,贪心算法每一步的最优解一定包含上一步的最优解。动态规划算法中全局最优解中一定包含某个局部最优解,但不一定包含前一个局部最优解,因此需要记录之前的所有最优解。

    (4)基本思路:

    1)建立数学模型来描述问题。
    2)把求解的问题分成若干个子问题。
    3)对每一子问题求解,得到子问题的局部最优解。
    4)把子问题的解局部最优解合成原来解问题的一个解。

    贪心算法在该问题的贪心策略不满足贪心选择性质条件时,构造出来的解是近似解

    4、回溯法

    (1)描述:回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法。

    (2)原理: 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。

    回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。有许多问题,当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时,往往要使用回溯法。
    (3)问题的解空间
    问题的解向量:回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。
    在这里插入图片描述
    在这里插入图片描述
    (5)回溯法的基本思想

    基本思想:

    用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻,算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n),则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2h(n))或O(h(n)!)内存空间。

    解题步骤:

    1)针对所给问题,定义问题的解空间;
    2)确定易于搜索的解空间结构;
    3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。

    常用剪枝函数:用约束函数在扩展结点处剪去不满足约束的子树;用限界函数剪去得不到最优解的子树

    约束函数用于选取满足条件的一个解,而限界函数用于剪除不可能存在的解
    5、分支限界法

    (1)描述:采用广度优先产生状态空间树的结点,并使用剪枝函数的方法称为分枝限界法。

    所谓“分支”是采用广度优先的策略,依次生成扩展结点的所有分支(即:儿子结点)。
    所谓“限界”是在结点扩展过程中,计算结点的上界(或下界),边搜索边减掉搜索树的某些分支,从而提高搜索效率。

    (2)原理:按照广度优先的原则,一个活结点一旦成为扩展结点(E-结点)R后,算法将依次生成它的全部孩子结点,将那些导致不可行解或导致非最优解的儿子舍弃,其余儿子加入活结点表中。然后,从活结点表中取出一个结点作为当前扩展结点。重复上述结点扩展过程,直至找到问题的解或判定无解为止。

    (3)分支限界法与回溯法

    1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。
    2)搜索方式的不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

    (4)常见的分支限界法

    1)FIFO分支限界法(队列式分支限界法)

    基本思想:按照队列先进先出(FIFO)原则选取下一个活结点为扩展结点。

    搜索策略:一开始,根结点是唯一的活结点,根结点入队。从活结点队中取出根结点后,作为当前扩展结点。对当前扩展结点,先从左到右地产生它的所有儿子,用约束条件检查,把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点(队中最先进来的结点)为当前扩展结点,……,直到找到一个解或活结点队列为空为止。

    2)LC(least cost)分支限界法==(优先队列式分支限界法)==

    基本思想:为了加速搜索的进程,应采用有效地方式选择活结点进行扩展。按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。

    搜索策略:对每一活结点计算一个优先级(某些信息的函数值),并根据这些优先级;从当前活结点表中优先选择一个优先级最高(最有利)的结点作为扩展结点,使搜索朝着解空间树上有最优解的分支推进,以便尽快地找出一个最优解。再从活结点表中下一个优先级别最高的结点为当前扩展结点,……,直到找到一个解或活结点队列为空为止。

    补充:
    1.在对问题的解空间进行搜索时,
    分支限界法中的一个活结点最多有一次机会成为活结点
    回溯法中的一个结点会有多次机会成为活结点

    数值化随机算法
    利用了概率的性质计算近似值得到的随机算法

    舍伍德算法
    得到的解不一定正确,但总会得到一个解

    拉斯维加斯算法
    有时能得到解,有时得不到解,但得到的解一定正确
    运行时以一定的概率得到正确的解

    线性时间选择问题和快速排序利用了舍伍德算法

    N后问题使用了拉斯维加斯算法

    P问题是指能够在多项式时间内解决的问题,这意味着计算机能够在有限时间内完成计算。
    NP问题是指我们能够在多项式时间内验证一个解的问题。

    对于一个问题,如果我们能够在多项式时间内解决,那么我们肯定也能在多项式时间内验证某个猜测是否为这个问题的一个解,因此P问题也属于NP问题,或者说P问题是NP问题的一个子集。

    NP完全问题也简称为NPC问题,NPC问题是NP问题中最难的一类问题,
    NPC问题是NP难问题的一个子集。

    在这里插入图片描述
    用于计算时间复杂度的方法:
    在这里插入图片描述

    展开全文
  • 基本算法思想总结

    2021-03-30 15:40:50
    算法的精髓就在于其思想,或者说是解题思路,一个清晰的解题思路,是解决问题的致胜法宝。本文就来总结一下一些基本的算法思想。 首先,我们抛出心中的疑问:算法是什么?算法,即是按照一定的步骤,一步步去解决...

    无论是在大学还是培训机构,无论是在java还是在C,算法始终贯彻其中,扮演着是不容忽视的角色。而算法的精髓就在于其思想,或者说是解题思路,一个清晰的解题思路,是解决问题的致胜法宝。本文就来总结一下一些基本的算法思想。
    首先,我们抛出心中的疑问:算法是什么?算法,即是按照一定的步骤,一步步去解决某个问题,解决问题的方法步骤称之为算法,例如数学中我们学过的做一个运算,解一个方程,等等,都需要有一个清晰的思路,一步步地去完成。当然这只是我们学习中的例子,生活中,我们结算工资也是要按一定的步骤,完成一个闭合的运算,得出结果。所以说算法是无处不在的。下面我们来介绍一下基本的算法思想:
    一、分治法
    分治,分而治之。即将一个难以直接解决的大问题,划分成一些规模较小的可以解决的子问题,以便各个击破,分而治之。
    需要注意子问题的两个规则:
    1、平衡子问题:就是是各个子问题的规模大致相同
    2、独立子问题:各子问题之间相互独立,如果不独立,还需要分解子问题。

    上图很生动地再现了分治算法的化繁为简的思想,分治算法的思想往往应用于解决和计算步骤比较复杂的问题,通过将问题简化而逐步得到结果。
    二、动态规划法
    动态规划法和分治法类似,它也是将大问题分解成子问题求解,不同的是,如果分解的子问题有很多是相同的,采用分治法相同的子问题会求解多次,是不是很影响效率;动态规划法呢,它会保存已解决的子问题的答案,再有相同的子问题直接用保存的答案就行了,节省了很多计算时间。
    通过二叉树,我们注意到,F(n)是通过计算它的两个重叠子问题 F(n-1)和F(n-2)的形式来表达的,所以,可以设计一张表填入n+1个F(n)的值。通过下面的表会发现:后一个数等于前面两个数的和。(这就是著名的斐波那契数)

    所以,使用动态规划法的情况,对于一个问题具有的性质可以总结为:最优子结构,重叠子问题。
    三、贪心算法
    贪心算法的基本思想是找出整体当中每个小的局部的最优解,并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质:
    1.整体最的优解可以通过局部的最优解来求出;
    2.一个整体能够被分为多个局部,并且这些局部都能够求出最优解。使用贪心算法当中的两个典型问题是活动安排问题和背包问题。
    下面举一个贴近我们生活的例子,我们在现实中使用纸币现金在超市购买价值X元的商品,最少要用多少张钞票?这个问题的解题思路很清晰,每一个数值大的纸币可以被若干个数值小的代替,那么可以用数值大的情况,就不要用数值小的,也就是尽量使用数值大的纸币。代码实现如下:
    #include <stdio.h>

    int main (){
    const int RMB[]={100,50,20,10,5,1};
    const int NUM=6; //6种金额
    int x=628; //假设要支付的钱数是628
    int count=0; //最后支付的货币张数
    for(int i=0;i<NUM;i++){
    int use=x/RMB[i]; //需要RMB[i]的use张
    count+=use; //总计增加use张
    x=x-RMB[i]*use; //还没有付的金额
    }
    printf(“总共需要%d张”,count);
    return 0;
    }
    很容易得出结果:i=11,即6张100元,一张20元,一张5元,三张1元
    四、回溯算法
    回溯法是一种试探求解的方法,通过对问题的归纳分析,找出求解问题的一个线索,沿着这一线索往前试探,若试探成功,即得到解;若试探失败,就逐步往回退,换其他路线再往前试探。
    回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意结点时,先判断该结点是否包含问题的解。若肯定不包含,则跳过对以该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先搜索策略搜索。回溯算法的思想即以深度优先方式系统搜索问题的解,它适用于求解组合数较大的问题。
    用回溯法的思想解题的步骤:
    1.针对所给问题,定义问题的解空间。
    2.确定易于搜索的解空间结构。
    3.以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索;若回溯法对解空间做深度优先搜索则用递归方法实现回溯法。
    五、枚举法
    枚举算法可以说是这五种算法思想中是最简单的一种,其依赖于计算机的强大计算能力来穷尽每一种可能的情况,从而达到求解问题的目的。因此,枚举算法的效率比较低,但是却适应于一些没有明显规律可循的问题。
    在使用穷举算法时,需要明确问题的答案的范围,这样才可以在指定范围内搜索答案。指定范围之后,就可以使用循环语句和条件判断语句逐步验证候选答案的正确性,从而得到需要的正确答案。
    我们可以通过经典的鸡兔同笼问题(在一个笼子里关着若干只鸡和若干只兔,从上面数共有35个头;从下面数共有94只脚。问笼中鸡和兔的数量各是多少?)来一窥枚举算法思想的全貌:
    int chickenRabbit(int head,int foot,int c,int r){
    int i,j;
    int tag=0;//标志是否有解
    for(i=0;i<=head;i++){//鸡的个数穷举
    j=head-i;//兔子的个数
    if(i
    2+j
    4==foot){//判断是否满足条件
    tag=1;
    *c=i;
    *r=j;
    }
    }
    return tag;
    }
    int main()
    {
    int c,r;
    if(chickenRabbit(35,94,&c,&r)==1){//如果有解输出
    printf(“chickens=%d,rabbits=%d\n”,c,r);
    }else{//如果无解
    printf(“无解\n”);
    }
    return 0;
    }
    这段程序运行之后,凭借计算机的强大的计算能力瞬间得出结果:
    Chicken=23,Rabbit=12
    这些基本算法思想也是数据结构当中的重要组成部分,不仅仅为我们探究数据结构提供了清晰的思路,也为计算机语言的发展贡献了自己的力量。

    展开全文
  • 递归分治 — 算法思想介绍 一.递归分治的基本概念 递归的概念:直接或间接的调用自身的算法称为递归算法.用函数自身给出定义的函数成为递归函数. 分治法的思想:将一个难以直接解决的大问题分割成一些规模较小的相同...

    递归分治 — 算法思想介绍


    一.递归分治的基本概念

    递归的概念:直接或间接的调用自身的算法称为递归算法.用函数自身给出定义的函数成为递归函数.
    分治法的思想:将一个难以直接解决的大问题分割成一些规模较小的相同问题,以便各个击破,即分而治之.

    如果原问题可分割成k个子问题, 1<k<=n, 且这些子问题都可解,并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的.有分治法产生的子问题往往是原问题的较小模式,这为使用递归技术提供了方便.在这种情况下,反复利用分治手段,可以使子问题与原问题类型一致而其规模不断缩小,最终是子问题缩小到容易求出其解,由此自然引出递归算法.

    分治与递归像一对孪生兄弟,经常同时应用在算法设计中,并由此产生许多高效算法.

    二.递归分治算法的适用条件

    我们下面利用几个例子,来看一看递归分治算法什么情况下能够使用,以及应该如何使用.

    从我们耳熟能详的阶乘函数和斐波那契数列开始,介绍一下递归思想:
    阶乘函数:可递归地定义为:

    • n! = 0, n = 1 (此为边界条件)
    • n! = n*(n-1)!, n > 0 (此为递归方程)

    边界条件与递归方程是递归函数的二个要素,递归函数只有具备了这两个要素,才能在有限次计算后得出结果.

    int Factorial(int n)
    {
    	if(n == 0) return 1;
    	else return n*Factorial(n-1);
    }
    

    Fibonacci数列:无穷数列1,1,2,3,5,8,13,21,34,55,……,称为Fibonacci数列。它可以递归地定义为:

    • F(n) = 0, n = 0
    • F(n) = 1, n = 1
    • F(n) = F(n-1) + F(n-2), n > 1
    int fibonacci(int n)
     {
         if (n <= 1) return 1;
         return fibonacci(n-1)+fibonacci(n-2);
     }
    

    阶乘函数和Fibonacci数列这两种递归可转换为非递归方式,但并不是所有递归都可以转换.

    认识了简单的递归之后,我们举一个分治算法的例子 — 二分查找:
    已知不重复且从小到大排列的m个整数的数组A[1…m],要求找到一个下标i,使得A[i] = x, 找不到返回0;

    基本思想:
    将m个元素分成个数大致相同的两半,取A[mid]与x作比较。

    • x = A[mid], 算法终止
    • x < A[mid], 在数组的左半部继续搜索
    • x > A[mid], 在数组的右半部继续搜索
    int BinarySearch(int A[], int x, int l, int r)
    {
    	while(l <= r)
    	{
    		int mid = (l+r) / 2;
    		if(A[mid] == x) return mid;
    		else if(x < A[mid])
    			r = mid - 1;		
    		else
    			l = mid + 1;
    	}
    	return 0;
    }
    

    分治法的适用条件(其实就相当于是递归算法的适用条件了,因为分治法实现起来大部分是使用了递归):

    • 该问题的规模缩小到一定的程度就可以容易地解决;
    • 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质
    • 利用该问题分解出的子问题的解可以合并为该问题的解
    • 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题

    最后一条这条特征涉及到分治法的效率,如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然也可用分治法,但一般用动态规划较好.

    注意:人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想,它几乎总是比子问题规模不等的做法要好.

    三.递归分治算法总结

    递归分治算法的模板伪代码:

    Divide-and-Conquer(P)
    	if(|P|<=n0) Adhoc(P)   //若问题规模小于阈值,直接计算   
    	divide P into smaller subinstances P1, P2, ... , Pk   //否则,将大问题划分为若干个小问题
    	for(i = 1; i<= k; i++)		//依次计算每个小问题
    		yi = Divide-and-Conquer(Pi); 
    	return Merge(y1, y2, ... , yk);	//合并每个小问题的解,得到最终答案
    

    设问题P(n)分解成k个规模为n/m的子问题,阀值n0=1,求解P(1)的时间耗费为O(1).将P(n)分解及合并成P(n)的解的时间为f(n),则分治法解规模为n的问题的最坏时间复杂性函数T(n)满足:

    • T(n) = T(1) = O(1)
    • ​ = T(n) = kT(n/m) + f(n)

    答案很复杂,总之递归算法对时间空间复杂度要求较高.
    后面我会针对具体的几个算法题来应用递归分治思想解决,欢迎继续阅读.

    参考毕方明老师《算法设计与分析》课件.

    欢迎大家访问个人博客网站—乔治的编程小屋,一起体验一下养成式程序员的打怪升级之旅吧!

    展开全文
  • if (Height(pNode->pRight) - Height(pNode->pLeft) == 2) /*AVL树不平衡*/ { if (nData > pNode->pRight->nData) { /*插入到了右树右边, 做单旋转*/ pNode = SingleRotateWithRight(pNode); } else { /*插入到...
  • r代表纵向深度 绝对有序是对最终结果而言,相对是对本身而言 动态规划:弗洛伊德算法(多点最最短路径) 分治思想:二叉树的中序遍历 外部排序:原理同归并排序(n个有序数组的归并) 进入的归并段的数量(k路)...
  • 平衡二叉树(AVL树)1.1 平衡二叉树实现原理1.2 平衡二叉树实现算法2. 总结 前言 部分内容摘自程杰的《大话数据结构》 1. 平衡二叉树(AVL树)   有一部德国人制作的叫《平衡》(英文名:Balance)的短片,它在 ...
  • 数据结构与算法之美笔记整理 为什么大多数编程语言中数组从 0 而不是从 1 开始编号? 从数组存储的内存模型上来看,“下标”最确切的定义应该是“偏移(offset)”。如果用 a 来表示数组的首地址,a[0]就是偏移为...
  • 摘要:智能优化算法又称现代启发式算法,是一种具有全局优化性能、通用性强且适合于并行处理的算法。本文主要为大家带来遗传算法和蚁群算法的详细解读。
  • [算法总结] 平衡树 !

    2021-05-16 12:36:02
    平衡树种类set,map(红黑树的变种)treap( Tree + heap -二叉搜索树+堆-)二叉搜索树(BST)TreapNode : code左旋右旋(所有的平衡树都有)Splay(竞赛用的非常多的一个平横树)sbt(暂时不了解)AVL(暂时不了解)红黑树(工程用 ...
  • 平衡算法总结&专题训练2(有旋平衡树:AVL 树,Splay)1.概述2.有旋平衡树-AVL 树 1.概述 在 平衡算法总结&专题训练1 中我们着重讲解了两种无旋平衡树:替罪羊树,FHQ Treap。 那么在这篇博文中我们将...
  • 在计算机科学中,分治法是一种很重要的算法,字面上的解释是“分而治之”,就是将一个难以直接解决的大问题,分割成 n 个规模较小的子问题,这些子问题相互独立,且与原问题相同,然后各个击破,分而治之。...
  • 遗传算法借用了生物遗传学的思想,以及自然界中的“物竞天择,适者生存”原则,将问题的解表示成“染色体”通过模拟自然选择、交叉、变异等操作,实现个体适应度的提高,不断迭代,逐步寻找最优解(或次优解)。遗传算法在...
  • 点击上方“小白学视觉”,选择加"星标"或“置顶”重磅干货,第一时间送达目录:1.什么是类别不平衡问题2.解决类别不平衡问题2.1欠采样方法(1)什么是欠采样方法(2)随机欠采样方法(3)欠...
  • 分治法常常与递归结合使用:通过反复应用分治,可以使子问题与原问题类型一致而规模不断缩小,最终使子问题缩小到很容易求出其解,由此自然导致递归算法。 3、子问题规模 根据分治法的分割原则,应把原问题分割成...
  • 模拟退火算法(Simulated Annealing,SA)的思想最早由Metropolis等人于1953年提出:Kirkpatrick于1983年第一次使用模拟退火算法求解组合最优化问题[1] 。模拟退火算法是一种基于MonteCarlo迭代求解策略的随机寻优算法...
  • 数据结构与算法必知基础知识

    千次阅读 多人点赞 2021-01-06 22:58:12
    原创公众号:bigsai ...此外数据结构也蕴含一些面向对象的思想,故学好掌握数据结构对逻辑思维处理抽象能力有很大提升。 为什么学习数据结构与算法?如果你还是学生,那么这门课程是必修的,考研基本也.
  • 1、整数规划问题 整数规划问题在工业、经济、国防、医疗等各行各业应用十分广泛,是指规划中的变量(全部或部分)限制为整数,属于离散优化问题(Discrete Optimization)。 线性规划问题的最优解可能是分数或小数。...
  • 基于机器学习的数据不平衡问题处理为什么要处理数据不平衡问题数据不平衡问题的处理方法欠采样过采样单分类算法其它 为什么要处理数据不平衡问题 数据不平衡问题是现实生活中十分常见的一个问题,如上市公司的破厂...
  • 将集合S分成两个子集S1和S2,根据平衡子问题原则,每个子集中的点数大致都为n/2。这样分治后,最近点对将会出现三种情况:在S1中,在S2中或者最近点对分别在集合S1和S2中。利用递归分析法分别计算前两种情况,第三种...
  • p(n)表示一个规模为n的问题P,可以把它分解成k个规模较小的子问题,这些问题相互独立,并且与原来的问题结构相同。在解决这些子问题时,又用相同的方式对每一个子问题进行进一步的分解,直到某个阈值n0为止。递归的...
  • C语言七大算法

    2021-06-10 09:34:31
    本文简单概括性的介绍了常见的七种查找算法,说是七种,其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在...
  • 二叉排序树:二叉树中的任何一个节点,它的左子树中所有的节点都比该节点要小,它的右树中所有的节点都比该节点要大。(注意二叉排序树中应尽量避免重复的值,如果有重复的值,可以选择不插入,或者添加一个属性...
  • Python算法详解

    2021-01-30 01:11:42
    目 录第 1章 算法概述 11.1 算法的基础 21.1.1 算法的特征 21.1.2 何为算法 21.2 计算机中的算法 31.2.1 认识计算机中的算法 31.2.2 为什么说算法是程序的灵魂 41.3 计算机中表示算法的方法 41.3.1...
  • 二、模拟退火算法简介 1 引言 模拟退火算法(Simulated Annealing,SA)的思想最早由Metropolis等人于1953年提出:Kirkpatrick于1983年第一次使用模拟退火算法求解组合最优化问题[1] 。模拟退火算法是一种基于...
  • 为了提高建图和定位的精度,使用后端算法优化3D位姿信息是必不可少的环节。 Bundle Adjustment (BA) 是一种常用于 SfM 和 SLAM 系统的优化方法。同时,位姿图是 SLAM 系统中常用的另一种优化方法。与同时优化位姿和...
  • 而面对大规模的集成优化问题,先贤们发表了各种自己的高谈阔论,并有了许多种行之有效的解决方案。这些方案更是被广泛地运用在诸如:图像处理、任务分配、信号处理等方面。而在其中,如何更加高效得取得在可接受范围...
  • 模拟退火算法(Simulated Annealing,SA)的思想最早由Metropolis等人于1953年提出:Kirkpatrick于1983年第一次使用模拟退火算法求解组合最优化问题[1] 。模拟退火算法是一种基于MonteCarlo迭代求解策略的随机寻优算法...
  • 图划分算法

    千次阅读 2021-03-12 14:36:40
    图划分算法 目前调研的几种对于有向无环图的划分算法的大致思路: 启发式算法(单级算法):以拓扑排序作为初始划分,在局部邻域分区之间移动节点,得到更加优化的划分。 多级算法:对不同级别的图,逐级用启发式...
  • 平衡树之红黑树思想及实现 前言 之前我们学习过二叉查找树,发现它的查询效率比单纯的链表和数组的查询效率要高很多,大部分情况下,确实是这样的,但不幸的是,在最坏情况下,二叉查找树的性能还是很糟糕。 例如...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 37,057
精华内容 14,822
热门标签
关键字:

平衡子问题思想算法