算法分析與設計word版(編輯修改稿)
2025-07-11 11:49 本頁面
【文章內(nèi)容簡介】 10家庭版）如下： includectime include iostream include cstdio include ctime include algorithm include functional using namespace std。 const int maxnum = 100。 const int maxint = 99999。 typedef struct Edge{ int u, v。 // 起點，重點 int weight。 // 邊的權(quán)值 }Edge。 Edge edge[maxnum]。 // 保存邊的值 int dist[maxnum]。 // 結(jié)點到源點最小距離 int nodenum, edgenum, source。 // 結(jié)點數(shù)，邊數(shù)，源點 void init() { cin nodenum edgenum source。 // 輸入結(jié)點數(shù)，邊數(shù)，源點 for(int i=1。 i=nodenum。 ++i) dist[i] = maxint。 dist[source] = 0。 for( i=1。 i=edgenum。 ++i) { cin edge[i].u edge[i].v edge[i].weight。 if(edge[i].u == source) //注意這里設置初始情況 dist[edge[i].v] = edge[i].weight。 } } void relax(int u, int v, int weight) // 松弛計算 { if(dist[v] dist[u] + weight) dist[v] = dist[u] + weight。 } bool Bellman_Ford() { for(int i=1。 i=nodenum1。 ++i) for(int j=1。 j=edgenum。 ++j) relax(edge[j].u, edge[j].v, edge[j].weight)。 bool flag = 1。 // 判斷是否有負環(huán)路 for( i=1。 i=edgenum。 ++i) if(dist[edge[i].v] dist[edge[i].u] + edge[i].weight) { flag = 0。 break。 } return flag。 } int main() { clock_t start,finish。 init()。 start = clock()。 if(Bellman_Ford()){ for(int i = 1 。i nodenum。 i++){ cout dist[i] endl。} finish = clock()。 cout 算法的執(zhí)行時間為： (double)(finish start) / CLOCKS_PER_SEC endl。 } return 0。 } 運行結(jié)果如下： 算法執(zhí)行效率的對比分析： BellmanFord算法從理論上來說，其在求單源最短路徑問題上，可以判斷有無負權(quán)回路， 時效性也較好，時間復雜度為 O（ V*E）。該實驗的算法執(zhí)行時間為 。 分析 以上兩種算法的 代碼和實驗結(jié)果 ， 將 BellmanFord算法 和 Dijkstra算法 這兩種算法進行對比分析如下： 1. 權(quán)值 Dijkstra算法 無法對權(quán)值為負值的圖進行求解最短路徑，而 BellmanFord算 法可以判斷圖中是否存在負權(quán)回路， 然后求出最短路徑解。 因此，從算法的應用范圍 分析的話， Dijkstra算法 顯然有一定的局限性。 2. 時間復雜度 （僅考慮矩陣存儲的圖） 理論上， Dijkstra算法的時間復雜度為 O（ V*V+E）， BellmanFord算法的時間復雜度為 O(V*E)， 所以 BellmanFord算法的時效性比 Dijkstra算法的時效性 更好；從以上的實驗數(shù)據(jù)也可以看出來。 3．算法簡單性 兩個算法都是比較簡單的。由于本問題主要考慮現(xiàn)實生活中的簡單單源最短路徑問題，未涉及到負權(quán)的情形，并且兩個算法都用到了“松弛計算”的方法尋找最短路徑。所以兩個算法的簡單性相當。 4． 優(yōu)缺點的對比 算法 所屬類型 最優(yōu)解 優(yōu)點 缺點 Dijkstra算法 貪心策略 局部最優(yōu)解，但并不一定是全局最優(yōu)解 算法簡明 效率低、運算中占用空間大 BellmanFord算法 偏于動態(tài)規(guī)劃 無 代碼很容易寫 效率很低 二、 字符串匹配問題 字符串匹配（ string match)是在實際工程中經(jīng)常會碰到的問題，通常其輸入是原字符串 (String)和子串（又稱模式， Pattern)組成，輸出為子串在原字符串中的首次出現(xiàn)的位置。通常精確的字符串搜索算法包括暴力搜索 (Brute force)， KMP, BM(Boyer Moore), sunday, robinkarp 以及 bitap。下面分析這幾種方法并給出其實現(xiàn)。假設原字符串長度 M，字串長度為 N。 Brute force算法 ： 屬于一種蠻力算法， 是普通的模式匹配算法， BF算法的思想就是將目標串 S的第一個字符與模式串 T的第一個字符進行匹配，若相等，則繼續(xù)比較 S的第二個字符和 T的第二個字符；若不相等，則比較 S的第二個字符和 T的第一個字符，依次比較下去，直到得出最后的匹配結(jié)果。 該算法的主要思想： 首先 S[1]和 T[1]比較，若相等，則
畢業(yè)設計相關(guān)推薦
鄂ICP備17016276號-1