計算機(jī)算法實驗3 貪心算法 報告

1、算法設(shè)計與分析姓名： 班級：學(xué)號：課題：貪心算法指導(dǎo)教師： 2014/1/6目錄1實驗?zāi)康呐c要求12實驗內(nèi)容12.1基本題一：多機(jī)調(diào)度問題12.1.1問題概述12.1.2實驗截圖12.2提高題一：用貪心算法求解最小生成樹22.2.1問題概述22.2.2實驗截圖22.3提高題二：汽車加油問題32.3.1問題概述32.3.2實驗截圖33實驗心得4代碼附后面1實驗?zāi)康呐c要求1、熟悉多機(jī)調(diào)度問題的算法2、初步掌握貪心算法3、熟悉貪心算法的基本原理與適用范圍4、使用貪心算法編程，求解最小生成樹問題5、掌握汽車加油問題的算法2實驗內(nèi)容2.1基本題一：多機(jī)調(diào)度問題2.1.1問題概述要求給出一種作業(yè)調(diào)度方案，

2、使所給的n個作業(yè)在盡可能短的時間內(nèi)由m臺機(jī)器加工處理完成。約定，每個作業(yè)均可在任何一臺機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。提示：1、把作業(yè)按加工所用的時間從大到小排序2、如果作業(yè)數(shù)目比機(jī)器的數(shù)目少或相等，則直接把作業(yè)分配下去3、 如果作業(yè)數(shù)目比機(jī)器的數(shù)目多，則每臺機(jī)器上先分配一個作業(yè)，如下的作業(yè)分配時，是選那個表頭上s最小的鏈表加入新作業(yè)。2.1.2實驗截圖 按照書本例題數(shù)據(jù)，7個作業(yè)分給3臺機(jī)器，完成時間為17，實驗結(jié)果如下：2.2提高題一：用貪心算法求解最小生成樹2.2.1問題概述任選一種貪心算法（Prim或Kruskal），求解最小生成樹。對算

3、法進(jìn)行描述和復(fù)雜性分析。編程實現(xiàn)，并給出測試實例2.2.2實驗截圖 算法為Kruskal，選用書本例題數(shù)據(jù)，六個定點，十條邊，求解結(jié)果如下：2.3提高題二：汽車加油問題2.3.1問題概述一輛汽車加滿油后可以行駛N千米。旅途中有若干個加油站。若要使沿途的加油次數(shù)最少，設(shè)計一個有效的算法，指出應(yīng)在那些加油站?？考佑汀２⒆C明你的算法能產(chǎn)生一個最優(yōu)解。把兩加油站的距離放在數(shù)組中，a1.n表示從起始位置開始跑，經(jīng)過n個加油站，ak表示第k1個加油站到第k個加油站的距離。汽車在運行的過程中如果能跑到下一個站則不加油，否則要加油。2.3.2實驗截圖 輸入3代表加油站段目，50代表加油后最大行駛距離結(jié)果如下：

4、再換一個例子：3實驗心得這次算法實驗的主要內(nèi)容是貪心算法的使用，包括多機(jī)調(diào)度問題，最小生成樹問題（采用Kruskal算法），汽車加油問題。貪心算法是一種對某些求最優(yōu)解問題的更簡單、更迅速的設(shè)計技術(shù)。用貪婪法設(shè)計算法的特點是一步一步地進(jìn)行，常以當(dāng)前情況為基礎(chǔ)根據(jù)某個優(yōu)化測度作最優(yōu)選擇，而不考慮各種可能的整體情況，它省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大量時間，它采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優(yōu)解，雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時不一定是最優(yōu)的，所以貪婪法

5、不要回溯。貪心算法是算法的重要內(nèi)容之一，可以高效地解決許多問題。采用貪心算法會比動態(tài)規(guī)劃高效方便，如果都能解決某個問題的話?，F(xiàn)在我學(xué)習(xí)貪心算法的時間還不長，理解還很淺顯，以后要多加練習(xí)，這樣才能做到熟練運用。基本題一：多機(jī)調(diào)度問題#include<iostream> using namespace std;#define N 10 typedef struct node int ID, time;/作業(yè)所需時間 jobnode; typedef struct Node int ID, avail;/ID 機(jī)器編號 avail 每次作業(yè)的初始時間 manode; manode mac

6、hineN; jobnode jobN; /* 找出下個作業(yè)執(zhí)行機(jī)器 */manode* Find_min(manode a, int m) manode* temp = &a0; for (int i = 1; i<m; i+) if (ai.avail<temp->avail) temp = &ai;return temp; /* 對作業(yè)時間由大到小進(jìn)行排序 */void Sort(jobnode t, int n) jobnode temp;for (int i = 0; i<n - 1; i+) for (int j = n - 1; j>

7、i; j-) if (jobj.time>jobj - 1.time) temp = jobj;jobj = jobj - 1; jobj - 1 = temp;void main() int n, m, temp, i; manode* ma;printf("輸入作業(yè)數(shù)目(作業(yè)編號按輸入順序處理)n"); cin>>n;printf("輸入相應(yīng)作業(yè)所需處理時間:n"); for (i = 0; i<n; i+) cin>>jobi.time; jobi.ID = i + 1;printf("輸入機(jī)器數(shù)目(機(jī)

8、器編號按輸入順序處理)n"); cin>>m;for (i = 0; i<m; i+)/給機(jī)器進(jìn)行編號并初始化 machinei.ID = i + 1; machinei.avail = 0;putchar('n'); if (n <= m) printf("為每個作業(yè)分配一臺機(jī)器,可完成任務(wù)!n"); return;Sort(job, n);for (i = 0; i<n; i+) ma = Find_min(machine, m);printf("將機(jī)器: M%d 從 %d -> %d 的時間段分配

9、給作業(yè): %dn",ma->ID,ma->avail,ma->avail+jobi.time,jobi.ID); ma->avail+=jobi.time; temp = machine0.avail; for (i = 1; i<m; i+) if (machinei.avail>temp) temp = machinei.avail;putchar('n');printf("該批作業(yè)處理完成所需加工時間為: %dn", temp); 2提高題一：用貪心算法求解最小生成樹/*該程序用貪心算法來求解最小生成樹問題

10、采用貪婪準(zhǔn)則：每次選擇邊權(quán)值最小邊。如果該邊加入后不構(gòu)成環(huán)，則加入。*/#include <iostream> #include <string.h> using namespace std;int const CNST_Numgrphedge = 100;struct TTreeEdge/最小生成樹的邊類型 long v1, v2;/邊的起點與終點編號 float weight;/邊權(quán) ;/*全局變量*/int ty = 0;/紀(jì)錄返回邊的個數(shù)（作為引用參數(shù)中數(shù)組的下標(biāo)） /*該函數(shù)通過貪心算法求出最小生成樹，返回值為最小生成樹中的邊（起點與終點編號與邊權(quán)），通過引用

11、參數(shù)edge返回值*/void minspanningTree(TTreeEdge treeedge, int n, int e, TTreeEdge* edge)/*treeedge為圖最初的起點與終點編號與邊權(quán)n為頂點數(shù)e為邊數(shù)引用參數(shù)edge為最小最小生成樹中的邊（起點與終點編號與邊權(quán)）*/int i, j, u, v, p;int tempaCNST_Numgrphedge;/臨時數(shù)組，該數(shù)組存儲連通變量 long temp1, temp2;/改進(jìn)的冒泡排序中所用參數(shù) float temp3;/改進(jìn)的冒泡排序中所用參數(shù) int m, kk;/改進(jìn)的冒泡排序中所用參數(shù) /*按照邊的權(quán)值從

12、小到大排序(采用改進(jìn)的冒泡排序)*/m = e - 1;while (m>0)kk = 0;for (j = 0; j<m; j+)if (treeedgej.weight>treeedgej + 1.weight)temp1 = treeedgej.v1;treeedgej.v1 = treeedgej + 1.v1;treeedgej + 1.v1 = temp1;temp2 = treeedgej.v2;treeedgej.v2 = treeedgej + 1.v2;treeedgej + 1.v2 = temp2;temp3 = treeedgej.weight;tr

13、eeedgej.weight = treeedgej + 1.weight;treeedgej + 1.weight = temp3;kk = j;m = kk;/while /*初始化臨時數(shù)組，該數(shù)組存儲連通變量*/for (i = 0; i<e; i+)tempai = i;p = 1;for (j = 0; p<n; j+)/生成的邊數(shù)如果小于頂點數(shù)，繼續(xù)執(zhí)行循環(huán) u = treeedgej.v1; /邊的起點 v = treeedgej.v2;/邊的終點 /*如果起點與終點的連通變量不相等，則加入，將這條邊的起點與終點編號與邊權(quán)存入引用參數(shù)edge中,并改變臨時數(shù)組的值*/

14、if (tempau != tempav)edgety.v1 = u;/將選中邊的起點編號存入引用參數(shù)edge中 edgety.v2 = v;/將選中邊的終點編號存入引用參數(shù)edge中 edgety.weight = treeedgej.weight;/將選中邊的邊權(quán)存入引用參數(shù)edge中 ty+;/邊數(shù)加1 p+; /邊數(shù)加1 for (i = 0; i<n; i+)if (tempai = tempav)tempai = tempau;/改變臨時數(shù)組的值 void main()int i, e, n;int b;int Again = 0;char yn;TTreeEdge tree

15、edgeCNST_Numgrphedge;TTreeEdge edgeCNST_Numgrphedge;cout << "*" << endl;cout << "該程序用貪心算法來求解最小生成樹問題。" << endl;cout << "采用貪婪準(zhǔn)則：每次選擇邊權(quán)值最小邊。" << endl;cout << "如果該邊加入后不構(gòu)成環(huán)，則加入。" << endl;cout << "*" &l

16、t;< endl;while (!Again)cout << "-" << endl;cout << "請輸入圖的頂點數(shù):"cin >> n;/*判斷輸入圖的頂點數(shù)的合法性！*/b = 0;while (!b)if (n<3)cout << "輸入錯誤!頂點數(shù)不能小于3個!" << endl;cout << "請重新輸入圖的頂點數(shù)："cin >> n;elseb = 1;/while cout <<

17、; "請輸入圖的邊數(shù)(最多" << CNST_Numgrphedge << " 個）："cin >> e;/*判斷輸入圖的邊數(shù)的合法性！*/b = 0;while (!b)if (e>(n*(n - 1) / 2)cout << "輸入錯誤!頂點數(shù)為" << n << "的圖其邊數(shù)不能超過" << n*(n - 1) / 2 << "個!" << endl;cout <<

18、 "請重新輸入圖的邊數(shù)(最多" << CNST_Numgrphedge << " 個）："cin >> e;elseb = 1;/while cout << "請輸入圖的各條邊的起點位置、終點位置、邊權(quán)（起/終點位置用數(shù)字輸入）：" << endl;for (i = 0; i<e; i+)cin >> treeedgei.v1 >> treeedgei.v2 >> treeedgei.weight;/*判斷輸入圖的各條邊的起點位置、終

19、點位置、邊權(quán)的合法性！*/b = 0;while (!b)if (treeedgei.v1<0 | treeedgei.v2<0 | treeedgei.weight<0)cout << "輸入錯誤!邊的起點位置、終點位置、邊權(quán)不能小于0!" << endl;cout << "請重新輸入該條邊的起點位置、終點位置、邊權(quán)（起/終點位置用數(shù)字輸入）：" << endl;cin >> treeedgei.v1 >> treeedgei.v2 >> treeed

20、gei.weight;elseb = 1;/while /*調(diào)用函數(shù)*/minspanningTree(treeedge, n, e, edge);/*輸出引用參數(shù)edge中存儲的邊的起點位置、終點位置、邊權(quán)*/cout << "最小生成樹所包含的邊為：（依次為邊的起點位置、終點位置、邊權(quán)）" << endl;for (i = 0; i<ty; i+)cout << edgei.v1 << " " << edgei.v2 << " " << ed

21、gei.weight << endl;/*是否進(jìn)行下一個最小生成樹問題的求解*/cout << "n繼續(xù)進(jìn)行另一個最小生成樹問題的解答嗎?(Y/N)"cin >> yn;if (yn = 'Y' | yn = 'y')Again = 0;elseif (yn = 'N' | yn = 'n')Again = 1;else break;3提高題二：汽車加油問題#include<iostream>using namespace std;int main()int OilStationNum;/加油站的數(shù)目int MaxDist; /汽車加滿油以后行駛的最大距離int DiscOfCar; /汽車一次加油后已經(jīng)行駛的距離int Count;int * OilStationDist;printf("請