C++——《算法分析与设计》实验报告——单源最短路径问题
生活随笔
收集整理的這篇文章主要介紹了
C++——《算法分析与设计》实验报告——单源最短路径问题
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
| 實驗名稱: 單源最短路徑問題 | 實驗地點： |
| 實驗目的： 1、? 理解分支限界法的剪枝搜索策略； 2、? 掌握分支限界法的算法柜架； 3、? 掌握分支限界法的算法步驟； 4、? 通過應用范例學習動態規劃算法的設計技巧與策略； ? | |
| 實驗原理 1. 基本思想 分支是使用廣度優先策略，依次生成擴展結點的所有分支。 限界是在結點擴展過程中，計算結點的上界，搜索的同時剪掉某些分支。 分支限界法就是把問題的可行解展開，再由各個分支尋找最佳解。 與回溯法類似，分支限界法也是在解空間中搜索得到解； 不同的是，分支限界法會生成所有擴展結點，并舍棄不可能通向最優解的結點，然后根據廣度優先/最小耗費優先，從活結點中選擇一個作為擴展結點，使搜索向解空間上有最優解的分支推進。 2. 搜索策略 分支限界法首先生成當前擴展結點的所有分支，然后再從所有活結點中選擇一個作為擴展結點。每一個活結點都要計算限界，根據限界情況判斷是否剪枝，或選擇最有利的結點。 | |
| 實驗內容： 1、使用分支限界法解決單源最短路徑問題。 2、通過上機實驗進行算法實現。 3、保存和打印出程序的運行結果，并結合程序進行分析，上交實驗報告。 | |
| 源程序： 方法一： //單源最短路徑class Graph{ //帶權有向圖 private:int n; //頂點個數int **c; //鄰接矩陣int *dist; //記錄路徑 public:void shortestPaths(int);Graph(); //根據情況構造圖 };class MinHeapNode{ //最小堆的結點friend Graph; private:int i; //結點對應的頂點編號int length; //結點記錄的最短路徑 public:int getI(){ return i; }void setI(int i){ this->i = i; }int getLength(){ return length; }void setLength(int length){ this->length = length; } };class MinHeap{ //最小堆(雖然叫堆，但其實并不是用堆實現的)friend Graph; private:int length; //最小堆的長度，等同于頂點個數MinHeapNode *nodes; //結點數組 public:MinHeap(int n){this->length = n;nodes = new MinHeapNode[n];}void deleteMin(MinHeapNode&); //令當前節點出隊列，并給出下一個擴展結點void insertNode(MinHeapNode N) //結點入隊列，將原結點的內容替換即可{nodes[N.getI()].setI(N.getI());nodes[N.getI()].setLength(N.getLength());}bool outOfBounds() //檢查隊列為空{for(int i = 0;i < length;i++)if(nodes[i].getI() != -1)return false;return true;} };void MinHeap::deleteMin(MinHeapNode &E) {int j = E.getI();nodes[j].setI(-1);nodes[j].setLength(-1); //標記為出隊列int tmp = INT_MAX;for(int i = 0;i < length;i++){ //給出路徑最短的結點作為擴展結點if(nodes[i].getI() != -1 && nodes[i].getLength() < tmp){E.setI(i);E.setLength(nodes[i].getLength());tmp = nodes[i].getLength();}} }void Graph::shortestPaths(int start) {MinHeap heap = MinHeap(n); MinHeapNode E = MinHeapNode(); //別問，一開始還加了new，太久不寫C++了E.i = start; E.length = 0;dist[start] = 0; //初始為源點V,對應編號startwhile(true){for(int j = 0;j < n;j++){ //檢查所有鄰接頂點if(c[E.i][j] != 0){ //是否鄰接if(E.length + c[E.i][j] < dist[j]){ //是否滿足限界，當前路徑小于記錄的最短路徑dist[j] = E.length + c[E.i][j]; //更新if(/*填入判斷表達式*/){ //沒有鄰接頂點的點不入隊，按情況調整，沒有也可以，但會造成無效開銷MinHeapNode N = MinHeapNode(); //創建一個新的結點，并令其入隊列N.i = j;N.length = dist[j];heap.insertNode(N);}}}}if(heap.outOfBounds()) //隊列為空，結束break;heap.deleteMin(E); //該結點已經生成全部分支，出隊列并取得下一擴展結點} }方法二： #include <iostream> #include<queue> using namespace std;typedef struct ArcCell{int adj;//保存權值int info;//存儲最短路徑長度 }ArcCell,AdjMaxtrix[100][100];typedef struct{int data;int length; }VerType;typedef struct{VerType vexs[100];//頂點向量AdjMaxtrix arcs;int vexnum;//頂點數int arcnum;//弧數 }Graph;Graph G; queue<int> q;void CreateGraph() {int m,n,t;printf("輸入頂點數和弧數:");scanf("%d%d",&G.vexnum,&G.arcnum);printf("輸入頂點:");for(int i=1;i<=G.vexnum;i++){scanf("%d",&G.vexs[i].data);G.vexs[i].length=10000;}for(int i=1;i<=G.vexnum;i++)for(int j=1;j<=G.vexnum;j++){G.arcs[i][j].adj=0;}printf("輸入弧及權重:\n");for(int i=1;i<=G.arcnum;i++){scanf("%d%d%d",&m,&n,&t);G.arcs[m][n].adj=1;G.arcs[m][n].info=t;}}int NextAdj(int v,int w) {for(int i=w+1;i<=G.vexnum;i++)if(G.arcs[v][i].adj)return i;return 0;//not found; }void ShortestPaths(int v) {int k=0;//從首個節點開始訪問int t;G.vexs[v].length=0;q.push(G.vexs[v].data);while(!q.empty()){t=q.front();k=NextAdj(t,k);while(k!=0){if(G.vexs[t].length+G.arcs[t][k].info<=G.vexs[k].length)//減枝操作{G.vexs[k].length=G.vexs[t].length+G.arcs[t][k].info;q.push(G.vexs[k].data);}k=NextAdj(t,k);}q.pop();} }void Print() {for(int i=1;i<=G.vexnum;i++)printf("%d------%d\n",G.vexs[i].data,G.vexs[i].length); }int main() {CreateGraph();ShortestPaths(1);Print();return 0; }方法三： #include <iostream> #include<vector> #include<queue> using namespace std;typedef struct ArcCell{int u;//保存權值int info;//存儲最短路徑長度ArcCell(int a,int b):u(a),info(b){} }ArcCell,AdjMaxtrix[100][100];typedef struct{int data;int length; }VerType;typedef struct{VerType vexs[100];//頂點向量vector<ArcCell>arcs[1001];int vexnum;//頂點數int arcnum;//弧數 }Graph;Graph G; queue<int> q;void CreateGraph() {int m,n,t;printf("輸入頂點數和弧數:");scanf("%d%d",&G.vexnum,&G.arcnum);printf("輸入頂點:");for(int i=1;i<=G.vexnum;i++){scanf("%d",&G.vexs[i].data);G.vexs[i].length=10000;}printf("輸入弧及權重:\n");for(int i=1;i<=G.arcnum;i++){scanf("%d%d%d",&m,&n,&t);G.arcs[m].push_back({n,t});}}void ShortestPaths(int v) {int k=0;//從首個節點開始訪問int t;G.vexs[v].length=0;q.push(G.vexs[v].data);while(!q.empty()){t=q.front();for(int i=0,j=G.arcs[t].size(); i<j; i++){k=G.arcs[t][i].u; printf("%d------%d\n",t,k);if(G.vexs[t].length+G.arcs[t][i].info<=G.vexs[k].length)//減枝操作{G.vexs[k].length=G.vexs[t].length+G.arcs[t][i].info;q.push(G.vexs[k].data);}}q.pop();} }void Print() {for(int i=1;i<=G.vexnum;i++)printf("%d------%d\n",G.vexs[i].data,G.vexs[i].length); }int main() {CreateGraph();ShortestPaths(1);Print();return 0; }? | |
| 實驗結果： ? | |
| 心得與體會： 算法分析： 生成根節點的所有分支，全部入隊列并記錄路徑； 在隊列中選擇路徑最短的分支作為擴展結點 逐個生成分支，并判斷分支的路徑是否小于記錄的最短路徑； 若不小于，舍棄該分支； 若小于，該分支入隊列； 生成所有分支后，回到2； 當隊列為空時，算法結束。 ? 體會： 1、? 理解分支限界法的剪枝搜索策略； 2、? 掌握分支限界法的算法柜架； 3、? 掌握分支限界法的算法步驟； 4、? 通過應用范例學習動態規劃算法的設計技巧與策略； 5、? 使用分支限界法解決單源最短路徑問題。 ? | |
參考文章
https://blog.csdn.net/weixin_44712386/article/details/105532881
https://blog.csdn.net/gzj_1101/article/details/48955177
https://www.jianshu.com/p/372dc2571784
總結
以上是生活随笔為你收集整理的C++——《算法分析与设计》实验报告——单源最短路径问题的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： JavaScript + Tamperm
- 下一篇： Tensorflow——[Attribu