算法學習之蠻力法

文章目錄

• 算法學習之蠻力法
• • 蠻力法的思想
  • 蠻力法的基本
  • 蠻力法的優點
  • 蠻力法的解題步驟
  • 蠻力法的經典查找問題
  • • 順序查找
    • 改進的順序查找
    • 串匹配問題
  • 蠻力法的經典排序問題
  • 蠻力法的經典組合問題
  • • 生成排列對象
    • 生成子集
    • 0/1背包問題
    • 任務分配問題
  • 蠻力法的經典圖問題
  • • 哈密頓回路
    • TSP問題

蠻力法的思想

蠻力法是指采用遍歷技術，使用一定的策略將待求解問題的所有元素依次處理一次，其關鍵為依次處理所有元素，要使已處理過的元素不再被訪問

蠻力法的基本

基本技術——遍歷
關鍵——依次處理所有元素
基本的遍歷對象：（1）集合（2）線性表（3）樹（4）圖

蠻力法的優點

邏輯清晰，編寫程序簡潔，容易編寫

對于一些問題（排序、查找、矩陣乘法、字符串匹配），可以配合著產生一些合理算法

當遍歷空間很小時，可以使用較小的代價

可以解決小規模問題（畢竟優化算法本身就有一定的復雜度，不如蠻力法來的簡潔明了）

可以為其他高效算法做衡量

蠻力法的解題步驟

找出枚舉范圍：分析問題所涉及的各種情況

找出約束表達式：分析問題的解需要滿足的條件，并應邏輯表達式表示

蠻力法的經典查找問題

順序查找

從表的第一端向另一端逐個將元素與既定值進行對比，若相等，則查找成功，給出元素在表中位置；若無相等值，則查找失敗，返回NULL；

PS：我覺得這個東西就是循環遍歷外加一個跳出判斷，就不放代碼了

改進的順序查找

對于順序查找有兩個結束條件：（1）跳出條件，即滿足條件時立刻跳出循環（2）結束條件，即查找超出既定范圍后結束循環
對此每次循環會產生兩次比較，對此可作出改進，將范圍邊界設為跳出條件時，可以減少一個判斷條件

//1、普通的順序查找 int SeqSearch1(int r[], int n, int k) {i=n;while(i>0&&r[i]!=k){i--;}return i; } //2、改進的順序查找 int SeqSearch1(int r[], int n, int k) {r[0]=k;i=n;while(r[i]!=k){i--;}return i; }

串匹配問題

也稱模式匹配，即在主串S中查找子串T

需要注意的是（1）此算法的依次執行時間不容忽視：當問題規模n很大時，常常需要在大量的信息中進行匹配（2）算法改進所取得的積累效益不容忽視：串匹配操作經常被調用，執行頻率是極其高的

---

注：串匹配的匹配算法為BF算法，以及略有些難以理解的KMP算法，再次不在多做描述，可以參考網上的解釋博客（PS：疫情期間，很是頹廢）

蠻力法的經典排序問題

（1）選擇排序 （2）冒泡排序

注：這個也是最基礎的兩個排序問題，在此也不再過多描述（PS：我覺得這個大家應該都會）

蠻力法的經典組合問題

生成排列對象

假設已經生成了所有的(n-1)!個排列，可以把n插入到n-1個元素的每一種排列中去，來得到問題規模為n的所有排列（PS：在此之前我從未接觸過這個問題，細想之后發現不知如何通過書上的三重循環來實現全排列嘗試，因此轉載此篇文章以供參考：排列算法c++實現）

生成子集

n個元素的集合A={$a_1,a_2,\dots \dots ,a_n$}的所有$2^n$個子集和長度為n的所有$2^n$個比特串之間的意義對應關系（PS：簡單的來說就是類似于數電的交并集，001={$a_3$}，011={$a_2,a_3$}依次類推）

注：這個代碼還沒寫過目測可寫，但是疫情期間有點懶，日后如果能記起來就寫

0/1背包問題

在給定的所有的元素中選出小于容量c的最有價值的子集，本質仍然是找出所有子集，然后計算每個子集的總價值，找到價值最大的子集，但是其復雜度仍然是O($2^n$)

任務分配問題

問題描述：假設有n個任務需要分配給n個人執行，每個人物只分配給一個人，每個人只分配一個任務，且第j個任務分配給第i個人的成本是C[i,j]，要求找出總成本最小的分配方案

此方案需要考慮全排列，算出每個排列的成本，排列數量為n!，復雜度很高，除非問題規模很小，否則蠻力法基本與此無緣】

蠻力法的經典圖問題

哈密頓回路

適用蠻力法尋找哈密頓回路也是尋找排列，當排列內所有元素的邊都連通時即可

TSP問題

就是變相加權哈密頓回路的尋找！！！

注：蠻力法終究還是蠻力法，一般情況下，即使進行一定程度的改進后，也只能改變其時間復雜度的系數，而不是數量級。（PS：個人感覺有點虎頭蛇尾，畢竟所有例子如果都要用到的話代碼量會很大，所以我決定不寫代碼，簡單的將思路寫一下，畢竟后續中基本不可能用蠻力法來實現）

總結

以上是生活随笔為你收集整理的算法学习之蛮力法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。