C++——《算法分析与设计》实验报告——贪心算法与回溯法
| 實驗名稱: 貪心算法與回溯法 | 實驗地點： |
| 實驗目的： 1、理解貪心算法與回溯法的概念； 2、掌握貪心算法與回溯法的基本要素； 3、掌握貪心算法與回溯法的解題步驟與算法柜架； 4、通過應用范例學習貪心算法與回溯法的設計技巧與策略； ? | |
| 實驗原理 1、貪心算法 貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。貪心算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解。 2、貪心算法的基本思想 1）建立數學模型來描述問題。 2）把求解的問題分成若干個子問題。 3）對每一子問題求解，得到子問題的局部最優解。 4）把子問題的解局部最優解合成原來解問題的一個解。 3、回溯法 回溯法是一個既帶有系統性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的算法稱為回溯法，它適用于解一些組合數較大的問題。 4、回溯法的基本思想 確定了解空間的組織結構后，回溯法就從開始結點（根結點）出發，以深度優先的方式搜索整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，并成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。換句話說，這個結點不再是一個活結點。此時，應往回移動（回溯）至最近的一個活結點處，并使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。 ??? 運用回溯法解題通常包含以下三個步驟： ??? 1）針對所給問題，定義問題的解空間； ??? 2）確定易于搜索的解空間結構； ??? 3）以深度優先的方式搜索解空間，并且在搜索過程中用剪枝函數避免無效搜索； | |
| 實驗內容： 1． 使用貪心算法解決最小生成樹問題。 2． 使用回溯法解決0-1背包問題。 3． 通過上機實驗進行貪心算法與回溯算法實現。 4． 保存和打印出程序的運行結果，并結合程序進行分析，上交實驗報告。 | |
| 源程序： 1．使用貪心算法解決最小生成樹問題。 (1)Prim算法 #include <iostream>#include <cmath>using namespace std;#define MAX 100010#define LEN 105double dist[LEN];double map[LEN][LEN];bool isvisited[LEN];//點的結構體typedef struct Point{int x;int y;double z;}Point;//初始化void init(){int i,j;for(i=0;i<LEN;i++){for(j=0;j<LEN;j++){if(i==j) map[i][j]=0;?? //對a[][]進行初始化，一般都要；map[i][j]=MAX;}}}//prim算法double prim(int n){int i,j,min,pos;double sum=0;//初始化for(i=1;i<=n;i++){dist[i]=map[1][i];}//從1開始isvisited[1]=true;dist[1]=MAX;//找到權值最小點并記錄下位置for(i=1;i<n;i++){min=MAX;//pos=-1;for(j=1;j<=n;j++){if(!isvisited[j] && dist[j]<min){min=dist[j];pos=j;}}????if(min==MAX){return -1;}sum+=dist[pos];//加上權值isvisited[pos]=true;//更新權值for(j=1;j<=n;j++){if(!isvisited[j] && dist[j]>map[pos][j]){dist[j]=map[pos][j];}}}????return sum;}int main(){Point p[105];int i,j,n,nCase;cin>>nCase;double result;//總價while(nCase--){cin>>n;init();????? //初始化for(i=1;i<=n;i++){scanf("%d%d%lf",&p[i].x,&p[i].y,&p[i].z);map[p[i].x][p[i].y]=map[p[i].y][p[i].x]=p[i].z;}result=prim(n);if(result==-1){cout<<"oh!"<<endl;}else{printf("%.1lf\n",result);}}return 0;}(2)Kruskal算法 #include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <math.h>using namespace std;const int N=10000+10;int t,n,m,pre[N];struct node{int x,y,z;node(){};node(int a, int b,int c){x=a;y=b;z=c;}}point[N];struct Edge{int f,t;double l;Edge(){};Edge(int a, int b,double c){f=a;t=b;l=c;}bool operator <(const Edge &S)const{return l<S.l;}}e[N];int find(int x){int r=x;while(pre[r]!=r)r=pre[r];return r;}void join(int x,int y){int fx=find(x);int fy=find(y);if(fx!=fy)pre[fx]=fy;}int main(){scanf("%d",&t);while(t--){scanf("%d",&n);int a,b,c;int cnt=0;for(int i=1;i<=n;i++){scanf("%d%d%d",&a,&b,&c);e[++cnt]=Edge(a,b,c);}sort(e+1,e+cnt+1);for(int i=1;i<=n;i++){pre[i]=i;}double ans=0;for(int i=1;i<=cnt;i++)if(find(e[i].f)!=find(e[i].t)){join(e[i].f,e[i].t);ans+=e[i].l;}int cn=0;for(int i=1;i<=n;i++)if(pre[i]==i)cn++;if(cn-1==0)printf("%.1lf\n",ans);elsecout << "oh!" << endl;}//cout << "Hello world!" << endl;return 0;}2．使用回溯法解決0-1背包問題。 #include <iostream>#include <stdio.h>#include <algorithm>using namespace std;#define N 100010int n;double c;double cw = 0.0;double cp = 0.0;double bestp = 0.0;int put[100];struct Edge{int order;double v;double w;double perp;Edge(){};Edge(double a, int b,double c,double d){perp=a;order=b;v=c;w=d;}bool operator <(const Edge &S)const{return perp>S.perp;}}e[N];void knapsack(){int i,j;for(i=1;i<=n;i++)e[i].perp=e[i].v/e[i].w;sort(e+1,e+n);???}void backtrack(int i){??double bound(int i);if(i>n){bestp = cp;return;}if(cw+e[i].w<=c){cw+=e[i].w;cp+=e[i].v;put[i]=1;backtrack(i+1);cw-=e[i].w;cp-=e[i].v;}if(bound(i+1)>bestp)backtrack(i+1);}double bound(int i){double leftw= c-cw;double b = cp;while(i<=n && e[i].w<=leftw){leftw-=e[i].w;b+=e[i].v;i++;}if(i<=n)b+=e[i].v/e[i].w*leftw;return b;}int main(){int i;printf("請輸入物品的數量和背包的容量：");scanf("%d %lf",&n,&c);printf("請依次輸入%d個物品的重量:\n",n);for(i=1;i<=n;i++){scanf("%lf",&e[i].w);e[i].order=i;}printf("請依次輸入%d個物品的價值:\n",n);for(i=1;i<=n;i++){scanf("%lf",&e[i].v);}knapsack();backtrack(1);printf("最優價值為：%lf\n",bestp);printf("需要裝入的物品編號是：");for(i=1;i<=n;i++){if(put[i]==1)printf("%d ",e[i].order);}return 0;}? ? ? | |
| 實驗結果： 1．使用貪心算法解決最小生成樹問題。 (1)Prim算法 (2)Kruskal算法 2．使用回溯法解決0-1背包問題。 ? | |
| 心得與體會： 1、理解貪心算法與回溯法的概念； 2、掌握貪心算法與回溯法的基本要素； 3、掌握貪心算法與回溯法的解題步驟與算法柜架； 4、通過應用范例學習貪心算法與回溯法的設計技巧與策略； 5、理解Prim算法和Kruskal算法的異同； 6、掌握利用回溯法思想解決0-1背包問題。 | |
?
?
參考文章
https://blog.csdn.net/u013921430/article/details/80382916
https://blog.csdn.net/liufeng_king/article/details/8738161
https://blog.csdn.net/weixin_43272781/article/details/83589373
https://blog.csdn.net/weixin_43272781/article/details/83589394
https://blog.csdn.net/luoshixian099/article/details/51908175
總結
以上是生活随笔為你收集整理的C++——《算法分析与设计》实验报告——贪心算法与回溯法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 联想拯救者Y7000系列笔记本电脑外接显
- 下一篇： C#——WPF的菜单栏、工具栏、状态栏D