软考系列——求最优算法盘点

比眉伴天荒 2022-08-09 12:58 209阅读 0赞

算法中经常用到的除了排序算法之外，还有一类是用来求最优的算法。五大常用求最优的算法是：分治法，回溯法，贪心法，动态规划法，分支限界法。从求解思想，求解过程，算法实例的过程让大家复习一下几个算法。

#       一.分治法 #

1）求解思想

把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题。直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。**各个击破，分而治之。**

**    **  适用于：问题可分解为规模较小的相同问题，最重要的是问题分解可以合并。

2）求解过程

> > 1.  分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
> > 2.  解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
> > 3.  合并：将各个子问题的解合并为原问题的解。

3）算法实例

归并排序是应用分治法的一个完美的例子，归并排序的基本例子是将元素分半，对子序列排序，在将排好的子序列进行合并。下面是C代码。

![SouthEast][]

#include<stdlib.h>   
    typedef int RecType;//要排序元素类型  
    void Merge(RecType *R,int low,int m,int high)  
    {  
        //将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的子文件R[low..high]  
        int i=low,j=m+1,p=0;                //置初始值  
        RecType *R1;                        //R1是局部向量  
        R1=(RecType *)malloc((high-low+1)*sizeof(RecType));  
        if(!R1)  
        {  
            return;                         //申请空间失败  
        }  
      
        while(i<=m&&j<=high)                //两子文件非空时取其小者输出到R1[p]上  
        {  
            R1[p++]=(R[i]<=R[j])?R[i++]:R[j++];  
        }  
      
        while(i<=m)                         //若第1个子文件非空，则复制剩余记录到R1中  
        {  
            R1[p++]=R[i++];  
        }  
        while(j<=high)                      //若第2个子文件非空，则复制剩余记录到R1中  
        {  
            R1[p++]=R[j++];  
        }  
      
        for(p=0,i=low;i<=high;p++,i++)  
        {  
            R[i]=R1[p];                     //归并完成后将结果复制回R[low..high]  
        }  
    }  
      
    void MergeSort(RecType R[],int low,int high)  
    {     
        //用分治法对R[low..high]进行二路归并排序  
        int mid;  
        if(low<high)  
        {   //区间长度大于1   
            mid=(low+high)/2;               //分解  
            MergeSort(R,low,mid);           //递归地对R[low..mid]排序  
            MergeSort(R,mid+1,high);        //递归地对R[mid+1..high]排序  
            Merge(R,low,mid,high);          //组合，将两个有序区归并为一个有序区  
        }  
    }

#       二.贪心法 #

1）求解思想

在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。通过**解局部最优**策略。

适用于：局部最优策略可以导致全局最优。

2）求解过程

> > 1.  把求解的问题分成若干个子问题
> > 2.  对每一子问题求解，得到子问题的局部最优解
> > 3.  把子问题的解局部最优解合成原来解问题的一个解

3）算法实例

背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。

#include "stdafx.h"
    #include <iostream> 
    using namespace std; 
    
    const int N = 3;
    
    void Knapsack(int n,float M,float v[],float w[],float x[]);
    
    int main()
    {
    	float M = 50;//背包所能容纳的重量
    	//这里给定的物品按单位价值减序排序
    	float w[] = {0,10,20,30};//下标从1开始
    	float v[] = {0,60,100,120};
    
    	float x[N+1];
    
    	cout<<"背包所能容纳的重量为："<<M<<endl;
    	cout<<"待装物品的重量和价值分别为："<<endl;
    	for(int i=1; i<=N; i++)
    	{
    		cout<<"["<<i<<"]:("<<w[i]<<","<<v[i]<<")"<<endl;
    	}
    	
    	Knapsack(N,M,v,w,x);
    
    	cout<<"选择装下的物品比例如下："<<endl;
    	for(int i=1; i<=N; i++)
    	{
    		cout<<"["<<i<<"]:"<<x[i]<<endl;
    	}
    
    	return 0;
    }
    
    void Knapsack(int n,float M,float v[],float w[],float x[])
    {
    	//Sort(n,v,w);//这里假定w[],v[]已按要求排好序
    	int i;
    	for (i=1;i<=n;i++)
    	{
    		x[i]=0;//初始化数组x[]
    	}
    
    	float c=M;
    	for (i=1;i<=n;i++)//物品整件被装下,x[i]=1
    	{
    		if (w[i]>c)
    		{
    			break;
    		}
    		x[i]=1;
    		c-=w[i];
    	}
    
    	//物品i只有部分被装下
    	if (i<=n)
    	{
    		x[i]=c/w[i];
    	}
    }

#       三.动态规划法 #

1）求解思想

将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。在动态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问题是否具有**最优子结构性质**。

2）求解过程

> > 1.  分析问题最优解，找出特性，刻画结构特征。
> > 2.  递归的定义最优解。
> > 3.  自底向上计算问题最优解。
> > 4.  找到最优决策子序列。

3）算法实例

0-1背包问题：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

#include<stdio.h>
    int c[10][100];/*对应每种情况的最大价值*/
    int knapsack(int m,int n)
    {
     int i,j,w[10],p[10];
     printf("请输入每个物品的重量,价值：\n");
     for(i=1;i<=n;i++)
            scanf("%d,%d",&w[i],&p[i]);
     for(i=0;i<10;i++)
          for(j=0;j<100;j++)
               c[i][j]=0;/*初始化数组*/
     for(i=1;i<=n;i++)
          for(j=1;j<=m;j++)
               {
                if(w[i]<=j) /*如果当前物品的容量小于背包容量*/
                         {
                          if(p[i]+c[i-1][j-w[i]]>c[i-1][j])
                               /*如果本物品的价值加上背包剩下的空间能放的物品的价值*/
                             /*大于上一次选择的最佳方案则更新c[i][j]*/
                                c[i][j]=p[i]+c[i-1][j-w[i]];
                                else
                                c[i][j]=c[i-1][j];
                         }
                  else c[i][j]=c[i-1][j];
                }
     return(c[n][m]);
    }

#       四.回溯法 #

1）求解思想

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种**走不通就退回重新选择**的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

适用于：复杂，规模较大。

2）求解过程

> > 1.  定义问题的解空间
> > 2.  确定易于搜索的空间结构
> > 3.  以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索

3）算法实例

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    class PackBackTrack
    {
    
    protected:
    	vector<int> m_p; //N个背包的价格
    	vector<int> m_w; //N个背包的重量
    	int			m_c; //背包的容量
    	int			m_num; //物品的件数
    	int			bestValue;			//背包最大价值
    	int			currentValue;		//当前背包中物品的价值
    	int			currentWeight;		//当前背包中物品的重量
    
    private:
    	//辅助函数，用于回溯搜索
    	void BackTrack(int depth)
    	{
    		if(depth >= m_num)    //达到最大深度
    		{
    			if(bestValue < currentValue)  //保存最优解
    				bestValue = currentValue;
    			return ;
    		}
    
    		if(currentWeight +m_w[depth] <= m_c)  //是否满足约束条件
    		{
    			currentWeight += m_w[depth];
    			currentValue += m_p[depth];
    			
    			//选取了第i件物品
    			BackTrack(depth+1); //递归求解下一个结点
    			
    			//恢复背包的容量和价值
    			currentWeight -= m_w[depth];
    			currentValue  -= m_p[depth];
    		}
    		//不取第i件物品
    		BackTrack(depth+1);
    	}
    
    public:
    	//构造函数
    	PackBackTrack();
    	PackBackTrack(vector<int>& p,vector<int>& w, int c,int n)
    		:m_p(p),m_w(w),m_c(c),m_num(n)
    	{
    		bestValue =0;
    		currentValue =0;
    		currentWeight =0;
    	}
    
    	//获取背包内物品的最大值
    	int GetBestValue()
    	{
    		BackTrack(0);
    		return bestValue;
    	}
    };
    
    
    int main(void)
    {
    	//测试程序
    	int n;
    	int c;
    
    	cout << "请输入物品的件数" << endl;
    	cin >>n;
    	cout << "请输入背包的容量" << endl;
    	cin >>c;
    	vector<int> w(n);
    	vector<int> p(n);
    
    	cout << "请输入物品的重量:" << endl;
    	for(int i=0;i<n;++i)
    		cin >> w[i];
    	cout << "请输入物品的价格:" << endl;
    	for(int j=0;j<n;++j)
    		cin >> p[j];
    
    	PackBackTrack pack(p,w,c,n);
    
    	int bestValue = pack.GetBestValue();
    
    	cout << "背包内的物品的最大价值为：" << bestValue << endl;
    
    	return 0;
    }

#    总结 #

应对软考中的算法题，很多是在循环体中出一个填空，弄清楚这几层的循环很容易就可以蒙几道题上去的。求最优解系列的算法了解基本思想，做题的时候一定要先想一边基本思路，应该可以蒙对几个的....

排序算法的总结，请移步上一篇：《[软考系列——排序算法盘点][Link 1]》

[SouthEast]: /images/20220731/82cd263d998a4515920bb9952c0b8aaa.png
[Link 1]: http://blog.csdn.net/zhou2s_101216/article/details/48948297