c++最短路徑算法，分支限界算法c語言_算法分析

算法分析

作者: times 時間: 2019/3/11

算法分析與分析基礎

計算機系統中的任何軟件都是按個個特定的算法來予以實現的。用什么方法來設計算法，如何判定一個算法的性能， 設計的算法需要多少運行時間、多少存儲空間，這些問題都是在開發一個軟件時必須考 慮的。算法性能的好壞，直接決定了軟件性能的優劣。
本章將主要介紹算法、算法設計、算法分析的基本概念，以及常見重要問題的類型和常用算法的設計方法。

==算法設計常見的重要問題類型==

排序 查找 圖 組合 幾何 數值 其他

遞歸算法

遞歸算法是一種通過自身調用自身或間接調用自身來達到問題解決的算法。遞歸的基本思想是把個要求解的問題劃分成一一個或多個規模更小的子問題， 這些規模更小的子問題應該與原問題保持同一類型， 然后用同樣的方法求解規模更小的子問題。例如在”件產品中有1件次品的存在，所有產品的外形樣而重量有差異，如何能盡快通過稱重的方法將次品找出呢?最直觀的解題思路是先將產品分為相等或相近的兩組，進行稱重后必然有一端重端輕， 此時還無法判斷次品所在;然后繼續對每部分的n12個產品再進行分組和稱重，如果平衡則這部分的n2個產品都為正品，即次品在另外那部分中，否則次品就在這n/2個產品中。這樣尋找次品的范圍就減少了-半。依照這種方法不斷縮小次品的范圍，直到最后一對一找出次品。
處理重復性計算時,遞歸往往使函數的定義和算法的描述簡單明了、易于理解、容易編程和驗證。任何利用計算機求解的問題所需的計算時間與其規模是相關的。問題的規模越小，解題所需的時間通常也越小，從而較容易處理。因此很多復雜問題使用了遞歸技術能夠給出非常直觀的解法，結構簡潔清晰，易于算法分析。在計算機軟件領域，遞歸算法是不可或缺的。

漢諾塔問題

描述

漢諾塔問題（又稱為河內塔問題），是一個大家熟知的問題。在A，B，C三根柱子上，有n個不同大小的圓盤（假設半徑分別為1-n吧），一開始他們都疊在我A上（如圖所示），你的目標是在最少的合法移動步數內將所有盤子從A塔移動到C塔。游戲中的每一步規則如下：

1. 每一步只允許移動一個盤子（從一根柱子最上方到另一個柱子的最上方）
2. 移動的過程中，你必須保證大的盤子不能在小的盤子上方（小的可以放在大的上面，最大盤子下面不能有任何其他大小的盤子)

圖示：

樣例

樣例 1:

輸入:n = 2
輸出: ["from A to B","from A to C","from B to C"]

樣例 2:

輸入:n = 3
輸出:["from A to C","from A to B","from C to B","from A to C","from B to A","from B to C","from A to C"]

參考答案

public class Solution {/*** @param n: the number of disks* @return: the order of moves*/List<String> step;public List<String> towerOfHanoi(int n) {// write your code hereList<String> result = new ArrayList<>();step = new ArrayList<>();step.add("from A to B");step.add("from A to C");step.add("from B to A");step.add("from B to C");step.add("from C to A");step.add("from C to B");hanoi(result, n, 'A', 'B', 'C');return result;}private void hanoi(List<String> result, int n, char a, char b, char c) {if (n == 1) {move(result, a, c);} else {hanoi(result, n - 1, a, c, b);move(result, a, c);hanoi(result, n - 1, b, a, c);}}private void move(List<String> result, char m, char n) {switch (m) {case 'A': result.add(step.get(n == 'B' ? 0 : 1)); break;case 'B': result.add(step.get(n == 'A' ? 2 : 3)); break;case 'C': result.add(step.get(n == 'A' ? 4 : 5)); break;}}
}

相關問題 N皇后問題 N皇后問題 II

分治算法

在計算機科學中，分治法是建基於多項分支遞歸的一種很重要的算法範式。 字面上的解釋是“分而治之”，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。 這個技巧是很多高效算法的基礎，如排序算法（快速排序、歸并排序）、傅立葉變換（快速傅立葉變換）。
分治算法的基本思想和一般原則及它在排序問題、查找問題和組合問題中的應用。

常見的問題類型

歸并排序 快速排序 折半排序 選擇問題 最大字段和問題 棋盤覆蓋問題

相關問題 第k大元素 擺動序列

貪心算法

又稱貪婪算法，是一種在每一步選擇中都采取在當前狀態下最好或最優（即最有利）的選擇，從而希望導致結果是最好或最優的算法。 比如在旅行推銷員問題中，如果旅行員每次都選擇最近的城市，那這就是一種貪心算法。

常見的問題類型

背包問題 多機調度問題 單源最短路徑問題 最小代價生成樹

相關問題 無向圖中的最短路徑 平面最大矩形

動態規劃算法

是一種在數學、管理科學、計算機科學、經濟學和生物信息學中使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。
動態規劃常常適用于有重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少于樸素解法。
動態規劃背后的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再根據子問題的解以得出原問題的解。
通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定子問題的解已經算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重復子問題的數目關于輸入的規模呈指數增長時特別有用。

常見的問題類型

最優二叉搜索樹 近似串匹配問題 多段圖問題 最長公共子序列 流水作業調度

相關問題 最大矩形 我能贏嗎

回溯算法

回溯算法實際上一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就“回溯”返回，嘗試別的路徑。 回溯法是一種選優搜索法，按選優條件向前搜索，以達到目標。

常見的問題類型

裝載問題 0/1 背包問題 n 皇后問題 圖的m著色問題 子集和數問題 深度優先搜索 貨郎（TSP）問題 最大團（MCP）問題 哈密頓環問題

相關問題 單詞接龍 II 貼紙拼單詞

分支限界算法

與貪婪算法一樣，這種方法也是用來為組合優化問題設計求解算法的，所不同的是它在問題的整個可能解空間搜索，所設計出來的算法雖其時間復雜度比貪婪算法高，但它的優點是與窮舉法類似，都能保證求出問題的最佳解，而且這種方法不是盲目的窮舉搜索，而是在搜索過程中通過限界，可以中途停止對某些不可能得到最優解的子空間進一步搜索（類似于人工智能中的剪枝），故它比窮舉法效率更高。

常見的問題類型

FIFO分支限界算法 LC分支限界算法 0/1 背包問題 帶期限的作業排序 旅行商問題 單源點最短路徑問題

相關問題 單詞計數 (Map Reduce版本)

更多有趣題目

LintCode leetcode