二分查找算法

• 前面我們講過了二分查找算法，使用遞歸的方式，下面我們講解二分查找算法的非遞歸方式
• 二分查找法只適用于從有序的數列種進行查找（比如數字和字母等），將熟練排序后再進行查找
• 二分查找法的運行時間為對數時間O（log₂n），即查找到需要的目標位置最多只需要log₂n步。假設從[0,99]的隊列（100個數，即n=100）種尋找目標數30，則需要查找步數log₂100，即最多需要查找7次（2⁶<100<2⁷）

遞歸方式

public class BinarySearch {public static void main(String[] args) {int arr[] = {1,8,10,89,1000,1000,1000,1234};int findVal = 1000;int val = binarySearch(arr,0,arr.length-1,findVal);System.out.println(val);System.out.println("---------優化后的值------------");ArrayList<Integer> list = binarySearchBetter(arr,0,arr.length-1,findVal);System.out.println(list);}/*** 該情況找到就返回 只適合一個的情況* @param arr* @param left* @param right* @param findVal* @return*/private static int binarySearch(int[] arr, int left, int right, int findVal) {int midIndex =(left+right)/2;//沒找到值if(left>right){System.out.println("沒有找到");return -1;}if(findVal>arr[midIndex]){//右遞歸return binarySearch(arr,midIndex+1,right,findVal);}else if(findVal<arr[midIndex]){//左遞歸return binarySearch(arr,left,midIndex-1,findVal);}else{System.out.println("index = "+midIndex);return arr[midIndex];}}/*** 找到后并不立即返回 而是創建數組 判斷左右相鄰的值是否也相等* @param arr* @param left* @param right* @param findVal* @return*/private static ArrayList<Integer> binarySearchBetter(int[] arr, int left, int right, int findVal) {ArrayList<Integer> list = new ArrayList<>();int midIndex =(left+right)/2;//沒找到值if(left>right){System.out.println("沒有找到");list.add(-1);return list;}if(findVal>arr[midIndex]){//右遞歸return binarySearchBetter(arr,midIndex+1,right,findVal);}else if(findVal<arr[midIndex]){//左遞歸return binarySearchBetter(arr,left,midIndex-1,findVal);}else{list.add(arr[midIndex]);System.out.println("index = "+midIndex);//判斷左邊值是否相等int index = midIndex;while(findVal==arr[index-=1]){System.out.println("index = "+index);list.add(arr[index]);}//判斷右邊值是否相等index = midIndex;while(findVal==arr[index+=1]){System.out.println("index = "+index);list.add(arr[index]);}return list;}} }

非遞歸方式

public class BinarySearch {public static void main(String[] args) {int[] arr = {1,2,3,4,5,8,27,33};int target = 27;int index = binarySearch(arr,target);System.out.println("arr["+index+"] = "+arr[index]);}//二分查找非遞歸實現private static int binarySearch(int[] arr, int target) {int left = 0;int right = arr.length-1;while(left<=right){int mid = (left+right)/2;if(arr[mid]==target){return mid;}else if(arr[mid]>target){right = mid - 1;}else{left = mid + 1;}}return -1;} }

信息打印

分治算法

分治算法介紹
分治算法是一種很重要的算法。字面上的解釋是"分而治之"，就是把一個復雜的問題分成兩個或者更多的相同或者相似的子問題，再把子問題分成更小的子問題…直到最后子問題可以簡單的直接求解，原問題的解決即子問題的解決的合并。這個技巧是很多高效算法的基礎，如排序算法（快速排序，歸并排序），傅立葉變換（快速傅立葉變換）…

分治算法可以求解的一些經典問題

• 二分搜索
• 大整數乘法
• 棋盤覆蓋
• 合并排序
• 快速排序
• 線性時間選擇
• 最接近點對問題
• 循環賽日程表
• 漢諾塔

分治算法的基本步驟
分治發在每一層遞歸上都有三個步驟

• 分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題
• 解決：若子問題規模較小而容易被解決則直接解決，否則遞歸第解決各個子問題
• 合并：將各個子問題的解合并為原問題的解

分治（divide-and-conquer）算法設計模式如下：

if|P|<=n0 then return(ADHOC(P)) //將P分解為較小的子問題P1 P2...Pk for i <- 1 to k do y1 <- divide-and-conquer(Pi) 遞歸解決Pi T <- Merge (y1,y2...yk) 合并子問題 return T

其中|P|表示問題P的規模;n0為一個閾值，表示問題P的規模不超過n0時，問題已容易直接解出，不必宅繼續分解。ADHOC§是該分治發中基本
子算法，用于直接解決小規模的問題P。因此，當P的規模不超過n0時，直接用算法ADHOC§求解。算法Merge (y1,y2…yk)是該分治發中的合并算法，
用于將P的子問題P1 P2…Pk的相應的解y1,y2…yk合并為P的解

分治算法實踐-漢諾塔

漢諾塔的傳說
漢諾塔又稱河內塔 問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三個金剛石柱子，在一根柱子上從下往上按照大小順序裸著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按照大小順便重新擺放在另一根柱子上。并且規定在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
假如沒一秒鐘一次，共需要多長時間呢？移完這些金片需要5845.54億年以上，太陽系的預期壽命據說也就是數百億年，真的過了5845.54億年，地球上的一切生命連同梵塔，廟宇等，都早已灰飛煙滅。

漢諾塔演示過程：
如果一個盤子 A->C
如果我們有n>=2情況，
我們總是可以看做是兩個盤 1 最下邊的盤 2上面的盤
先把最上面的盤 A->B
把最下邊的盤 A->C
把B塔的所有盤 從B->C

代碼實習

public class DACHannoiTower {public static void main(String[] args) {hannoiTower(5,"S","T","D");}/*** 分治算法 處理漢諾塔* @param num 金片數量* @param A S 開始位置* @param B T 中轉位置* @param C D 目的地*/private static void hannoiTower(int num, String A, String B, String C) {if(num == 1){System.out.println("第1塊從"+A+"->"+C);}else{//分為個盤子 1 最下面的一個盤子 2最上面的其他盤子看做一個// 先把最上面的盤 A->B 過程中會先放到ChannoiTower(num-1,A,C,B);//把最下邊的盤 A->CSystem.out.println("第"+num+"塊從"+A+"->"+C);//把B塔的所有盤 從B->C 過程中會先放到AhannoiTower(num-1,B,A,C);}} }

信息打印

動態規劃算法

動態規劃算法介紹

• 動態規劃（Dynamic Programming）算法的核心思想是：將大問題劃分為小問題進行解決，從而一步步獲取最優解的處理算法
• 動態規劃算法與分治算法類似，其實基本思想也是將待解決的問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解
• 與分治法不同的是，適合用動態規劃求解的問題，經過分解得到子問題往往不是互相獨立的（即下一個字階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解）
• 動態規劃可以通過填表的方式來逐步推進，得到最優解

應用場景-背包問題

背包問題：有一個背包容量為4磅，有如下物品

• 要求達到目標為裝入背包的總價值最大，并且重量不超出
• 要求裝入的物品不能重復

物品重量價格

吉他（G）	1	1500
音響（S）	4	3000
電腦（L）	3	2000

思路分析和圖解
背包問題主要是指一個給定容量的背包，若干具有一定價值和重量的物品，如何選擇物品放入背包使物品的價值最大。其中又分01背包和完全背包（完全背包指的是：每種物品都有無限件可用）這里的問題屬于01背包，即每個物品最多放一個。而無限背包可用轉化為01背包。

算法的主要思想，利用動態規劃來解決。
每次遍歷到的第i個物品，根據w[i]和v[i]來確定是否需要將該物品放入背包中。即對于給定的n個物品，設w[i]和v[i]分別為第i個物品的價值和重量，c為背包的容量。再令w[i]v[j]表示前面i個物品中能夠裝入容量為j的背包中的最大價值。則我們有下面的結果：

v[i][0] =w[0][j]=0 //表示填入表 第一行 和第一列都是0
當w[i-1]>j時： v[i][j]=v[i-1][j] // 當準備加入新增的商品的容量大于當前背包的容量時，就直接使用上一個單元格的裝入策略
當j>=w[i-1]時：v[i][j]=max(v[i-1][j],val[i-1]+[i-1][j-w[i-1]])
//當 準備加入的新商品容量小于等于當前背包的容量
//裝入方式
v[i-1][j]：上一個單元格的裝入的最大值
val[i]：表示當前商品的價值
v[i-1][j-w[i-1]]：裝入i-1商品，到剩余空間j-w[i]的最大值

代碼實現

public class DynamicKnapsackProblem {public static void main(String[] args) {int[] w = {1,4,3};//每件物品的重量int[] val = {1500,3000,2000};// 物品的價格int c = 4;//背包的容量int n = w.length;//物品的個數//創建二維數組 v[i][j] 表示在前i個物品中能夠裝入容量為j的背包中的最大值int[][] v = new int[n+1][c+1];//初始化第一行 和第一列的數據 在本案例中可以不用處理，因為默認就是0for (int i = 0; i < v.length; i++) {v[i][0]=0;}for (int i = 0; i < v[0].length; i++) {v[0][i]=0;}// 根據前面的公式來動態規劃處理for (int i = 1; i < v.length; i++) {// 不處理第一行for (int j = 1; j < v[0].length; j++) {// 不處理第一列if(w[i-1]>j){v[i][j]=v[i-1][j];}else{v[i][j]=Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]]);}}}for (int i = 0; i < v.length; i++) {System.out.println(Arrays.toString(v[i]));}} }

信息打印

以上代碼并不完全，因為并不知道裝入了什么；還需要優化處理

整體代碼

public class DynamicKnapsackProblem {public static void main(String[] args) {int[] w = {1,4,3};//每件物品的重量int[] val = {1500,3000,2000};// 物品的價格int c = 4;//背包的容量int n = w.length;//物品的個數//創建二維數組 v[i][j] 表示在前i個物品中能夠裝入容量為j的背包中的最大值int[][] v = new int[n+1][c+1];//創建二維數組 記錄存放路徑int[][] path = new int[n+1][c+1];//初始化第一行 和第一列的數據 在本案例中可以不用處理，因為默認就是0for (int i = 0; i < v.length; i++) {v[i][0]=0;}for (int i = 0; i < v[0].length; i++) {v[0][i]=0;}// 根據前面的公式來動態規劃處理for (int i = 1; i < v.length; i++) {// 不處理第一行for (int j = 1; j < v[0].length; j++) {// 不處理第一列if(w[i-1]>j){//因為i是從1開始的所有需要減一 -1 以保證 從數組第一個值開始取值v[i][j]=v[i-1][j];}else{//v[i][j]=Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]]);if(v[i-1][j]<val[i-1]+v[i-1][j-w[i-1]]){v[i][j] = val[i-1]+v[i-1][j-w[i-1]];path[i][j]=1;//修改路徑的值}else{v[i][j] = v[i-1][j];}}}}for (int i = 0; i < v.length; i++) {System.out.println(Arrays.toString(v[i]));}System.out.println("--------------");for (int i = 0; i < v.length; i++) {System.out.println(Arrays.toString(path[i]));}for (int i = 0; i < path.length; i++) {for (int j = 0; j < path[0].length; j++) {if(path[i][j]==1){System.out.println("第"+i+"個商品放入背包");}}}System.out.println("--------------");int i = path.length-1; //行的最大下標int j = path[0].length-1;//列的最大下標while(i>0&&j>0){ //逆向遍歷if(path[i][j]==1){System.out.println("第"+i+"個商品放入背包");j -= w[i-1]; //背包減去容量}i--;}} }

信息打印

KMP算法

應用場景-字符串匹配問題

字符串匹配問題：
有一個字符串 str1 = “硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好”，和一個字符串str2 =“尚硅谷你尚硅你”
現在要判斷str1是否含有str2，如果存在，就返回第一次出現的位置，如果沒有，則返回-1

暴力匹配法

暴力匹配算法
如果用暴力匹配的思路，并假設現在str1匹配到i位置，字符串str2匹配到j位置，則有

• 如果當前字符串匹配成功（str1[i]==str2[j]），則i++,j++繼續匹配下一個字符
• 如果失配（str1[i]！=str2[j]），令i=i-(j-1),j=0.相當于每次匹配失敗時，回溯，j被置為0
• 用暴力方法解決的話就會有大量的回溯，每次只移動一位，若不匹配，移動到下一位接著判斷，浪費了大量的時間。

代碼實現

public class KMPViolenceMatch {public static void main(String[] args) {String str1 = "BBC ABCDABABC DABCDABDE";String str2 = "ABCDABD";int index = violenceMatch(str1,str2);System.out.println("匹配的起始位置："+index);}private static int violenceMatch(String str1, String str2) {char[] source = str1.toCharArray();char[] target = str2.toCharArray();int i = 0; //char1的下標int j = 0; //char2的下標//確保數組不越界while (i<source.length&&j<target.length){if(target[j]==source[i]){i++;//字符串數組往后移動j++;}else{i = i-j+1; // 如果有匹配過 但沒完全匹配上 i歸位從剛進入的下一個節點開始j = 0; // j 需要從第一個位置開始重新匹配}}if(j==target.length){return i-target.length;}return -1;} }

KMP算法介紹

• Kunth-Morris-Pratt 字符串查找算法，簡稱"KMP算法"，常用于在一個文本串中查找一個模式串的出現位置，這個算法由
• KMP是一個解決模式串在文本串是否出現過，如果出現過，最早出現的位置經典算法Kunth、Morris及Pratt三個人于1977年聯合發表，故用這個方式命名算法
• KMP 方法就利用了之前判斷過信息，通過一個next數組，保存模式串中前后最長公共子序列的長度，每次回溯時，通過next數組找到，前面匹配過的位置，省去了大量的計算時間
• 參考資料：

字符串匹配問題：

• 有一個字符串str1=“BBC ABCDAB ABCDABCDABDE”，和一個字符串str2=“ABCDABD”
• 現在要判斷str1是否含有str2，如果存在，就返回第一次出現的位置，如果沒有，則返回-1
• 要求使用KMP算法完成判斷，不能使用簡單的暴力匹配算法。

思路分析圖解

• 1.首先，用str1的第一個字符串和str2的第一個字符去比較，不符合，關鍵詞向后移動一位
  
• 2。重復第一步，還是不符合，在移
  
• 3.一直重復，知道str1有一個字符與str2的第一個字符符合為止
  
• 4.接著比較字符串和搜索詞的下一個字符，還是符合。
  
• 5.遇見str1有一個字符與str2對應的字符不符合
  
• 6.這時,想到的是繼續遍歷str1的下一個字符，重復第1步。（其實是很不明智的，因為此時BCD已經比較過了，沒必要在做重復的工作，一個基本事實是，當空格與D不匹配時，你其實知道前面六個字符是“ABCDAB”。KMP算法的想法是，設法利用這個已知信息，不要把“搜索位置”一回到已經比較過的位置，繼續把它向后移，這樣就提高了效率。）
  
• 7.怎么做到把剛剛重復的步驟省略掉？可以懟str2計算出一張《部分匹配表》，這張表的產生后面會介紹
  
• 8.已知空格與D不匹配時，前面六個字符“ABCDAB”是匹配的。查表可知，最后一個匹配字符B對應的“部分匹配值”為2，因此按照下面的公司算出向后移動的位數：
  == 移動位數 = 已匹配的字符數 - 對應的部分匹配值==
  因為6 - 2 = 4 ，所有將搜索詞向后移動4位
• 9.因為空格與C不匹配，搜索詞還要繼續往后移。這時，已匹配的字符數為2（“AB”），對應的“部分匹配值”為0；所以，移動位數 =2-0=2，于是將搜索詞向后移動2位。
  
• 10.因為空格與A不匹配，繼續后移一位。
  
• 11.逐位比較，直到發現C與D不匹配，繼續將搜索詞先后移動4位
  
• 12.逐位比較，直到搜索詞最后一位，發現完全匹配，于是搜索完成。如果還要繼續搜索（即找出全部匹配），移動位數=7-0，再將搜索詞向后移動7位，這里就不在重復了。
  
• 13.介紹《部分匹配表》怎么產生的
  先介紹前綴，后綴是什么
  字符串： “bread”
  前綴： b br bre brea
  后綴： read ead ad d
  “部分匹配值”就是“前綴”和“后綴”的最長的共有元素的長度。以“ABCDABD”為列：

1 “A”的前綴和后綴都為空集，共有元素的長度為0；2 “AB”的前綴為[A]和后綴為[B]，共有元素的長度為0；3 “ABC”的前綴為[A AB]和后綴為[BC C]，共有元素的長度為0；4 “ABCD”的前綴為[A AB ABC]和后綴為[BCD CD D]，共有元素的長度為0；5 “ABCDA”的前綴為[A AB ABC ABCD]和后綴為[BCDA CDA DA A]，共有元素的長度為1；6 “ABCDAB”的前綴為[A AB ABC ABCD ABCDA]和后綴為[BCDAB CDAB DAB AB B]，共有元素的長度為2；7 “ABCDABD”的前綴為[A AB ABC ABCD ABCDA ABCDAB]和后綴為[BCDABD CDABD DABD ABD BD D]，共有元素的長度為0；

• 14.“部分匹配”的實質是，有時候，字符串頭部和尾部會有重復。比如：“ABCDAB”之中有兩個“AB”,那么他的“部分匹配”就是2（“AB的長度”）。搜索詞移動的時候，第一個“AB”向后移動4位（字符串長度-部分匹配值），就可以來到第二個“AB”的位置
  
  到此KMP算法思想分析完畢！

代碼實現

public class KMPMatch {public static void main(String[] args) {String str1 = "BBC ABCDABABC DABCDABDE";String str2 = "ABCDABD";int[] next = KMPMatch(str2);System.out.println("部分匹配表："+ Arrays.toString(next));int index = KMPSearch(str1,str2,next);System.out.println("匹配到的起始索引："+index);}private static int KMPSearch(String str1, String str2, int[] next) {for (int i = 0,j = 0; i <str1.length(); i++) {// 需要處理 str1.charAt(i) != str2.charAt(j), 調整 j 的 大小// KMP代碼的核心點while(j>0&&str1.charAt(i)!=str2.charAt(j)){j = next[j-1];}if(str1.charAt(i)==str2.charAt(j)){j++;}if(j==str2.length()){return i-j+1;}}return -1;}private static int[] KMPMatch(String str2) {int[] next = new int[str2.length()];//i 從1開始 因為判斷的是從第二個字符串開始 與前面是否相同for (int i = 1,j = 0; i <str2.length(); i++) {// 當str.charAt(i) != str.charAt(j) 需要從next[j - 1]獲取新得節點// 直到發現有str.charAt(i) == str.charAt(j)成立時推出// KMP算法的核心while(j>0&&str2.charAt(i)!=str2.charAt(j)){j = next[j-1];}// 滿足str.charAt(i) == str.charAt(j)條件時 部分匹配值 + 1if(str2.charAt(i)==str2.charAt(j)){j++;}next[i]=j;}return next;} }

信息打印

貪心算法

貪心算法介紹

• 貪心算法是指在對問題進行求解時，在每一步選擇中都采取最好或者最優（即最有利）的選擇，從而希望能夠導致結果是最好或者最優的算法
• 貪心算法所得到的結果不一定是最優的結果（有時候回溯最優解）。但是都是相對近似（接近）最優的結果

應用場景-集合覆蓋問題

假設存在下面需要付費的廣播臺，以及廣播臺信號可以覆蓋的地區。如何選擇最少的廣播臺，讓所有的地區都可以接收到信號

廣播臺覆蓋地區

K1	“北京”，“上海”，‘天津’
K2	“廣州”，“北京”，‘深圳’
K3	“成都”，“上海”，‘杭州’
K4	“上海”，“天津”
K5	“杭州”，“大連”

思路分析

如何找到覆蓋所有地區的廣播臺的結合呢，使用窮舉法實現，列舉每個可能的廣播臺的集合，這被稱為冪集。假設總的有n個廣播臺，則廣播臺的組合總共有2ⁿ-1個，假設每秒可以計算10個子集，如圖：

廣播臺數量n子集總數2ⁿ需要的時間

5	32	3.2秒
10	1024	102.4秒
32	4294967296	13.6年
100	1.26*1003	4*1023年

使用貪心算法，效率高：

• 目前并沒有算法可以快速計算得到準備的值，使用貪心算法，則可以得到非常接近的解，并且效率高。選擇策略上，因為需要覆蓋全部地區的最小集合；
• 遍歷所有的廣播臺，找到一個覆蓋了最多未覆蓋的地區的電臺（此電臺可能包含一些已覆蓋的地區，但沒有關系）
• 將這個電臺加入到一個集合中（比如ArrayList）,想辦法把該電臺覆蓋的地區在下次比較時去掉。
• 重復第一步知道覆蓋了全部地區
  

代碼實現

public class GreedyAlgorithm {public static void main(String[] args) {Map<String, Set<String>> broadcast = new HashMap<>();Set<String> k1 = new HashSet<>();k1.add("北京");k1.add("上海");k1.add("天津");Set<String> k2 = new HashSet<>();k2.add("廣州");k2.add("上海");k2.add("深圳");Set<String> k3 = new HashSet<>();k3.add("成都");k3.add("上海");k3.add("杭州");Set<String> k4 = new HashSet<>();k4.add("上海");k4.add("天津");Set<String> k5 = new HashSet<>();k5.add("杭州");k5.add("大連");broadcast.put("k1",k1);broadcast.put("k2",k2);broadcast.put("k3",k3);broadcast.put("k4",k4);broadcast.put("k5",k5);Set<String> allArea = new HashSet<>();for (Map.Entry<String,Set<String>> entry:broadcast.entrySet()){allArea.addAll(entry.getValue());}System.out.println(allArea);//定義一個集合存儲需要選擇的電臺List<String> selects = new ArrayList<>();//定義一個臨時集合 取交集 判斷交集的大小Set<String> tempArea = new HashSet<>();//定義一個最大key的變量String maxKey = "";while(allArea.size()>0){//需要清空數據maxKey = "";for (String key:broadcast.keySet()){//需要清空臨時set元素tempArea.clear();//kn 不能直接用tempArea臨時集合結束 會清空集合Set<String> kn = broadcast.get(key);tempArea.addAll(kn);//將臨時set中的元素與所有地區的元素取交集并存放在tempArea中tempArea.retainAll(allArea);if(tempArea.size()>0&&("".equals(maxKey) || tempArea.size() > broadcast.get(key).size())){maxKey = key;}}if(!"".equals(maxKey)){selects.add(maxKey);//從所有集合中去掉已經選中的地區allArea.removeAll(broadcast.get(maxKey));}}System.out.println("選擇的電臺："+selects);} }

信息打印

貪心算法注意事項和細節

• 貪心算法所得到的結果不一定是最優的結果（有時候會是最優解），但是都是相對近似接近最優解的結果
• 比如上體的算法選出的是k1 k2 k3 k5,符合覆蓋了全部地區
• 但是我們發現 k2 k3 k4 k5 也可以覆蓋全部地區，如果k2的使用成本低于k1， 那么我們上題k1 k2 k3 k5 雖然滿足條件 但不是并不是最優解

普利姆算法

應用場景-修路問題

看一個應用場景和問題:

• 有7個村莊（A、B、C、D、E、F、G）,現在需要修路把7個村莊聯通
• 各個村莊的距離邊線表示（權），比如A-B 5公里
• 問：如何修路保證各個村莊都能連通，并且總的修建公路里程最短？
  
  思路：將10條邊連接即可，但是總里程不是最小的
  正確的思路，就是盡可能的選擇少的線路，并且每條路線最小，保證總里程數最少

最小生成樹

修路問題本質就是最小生成樹問題，先介紹一下最下生成樹（Min Cost Spanning Tree）,簡稱MST
給定一個帶權的無向連接圖，如何選取一顆生成樹，使樹上所有邊上權的總和為最小，這叫最小生成樹

• N個頂點，一定有N-1條邊
• 包含全部頂點
• N-1條邊都在圖中
• 求最下生成樹的算法主要是普利姆算法和克魯斯卡爾算法

普利姆算法介紹

普利姆（prim）算法求最小生成樹，也就是在包含n個頂點的連通圖中，找出只有（n-1）條邊包含所有n個頂點連通子圖，也就是所謂的極小連通子圖
普利姆算法如下：

• 設G=（V,E）是連通網，T=（U,D）是最小生成樹，V，U是頂點集合，E,D是邊的集合
• 若從頂點u開始構造最小生成樹，則從集合V中取出頂點u放入集合U中，標記頂點v的 visited[u]=1、個人的年度工作任務完成情況及存在的不足；
• 若集合U中頂點ui與集合V-U的頂點vj之間存在邊，則尋找這些邊中權值最小的邊，但不能構成回路，將頂點vj加入集合U中，將邊（ui，vj）加入集合D中，標記visited[vj]=1
• 重復步驟②，直到U與V相等，即所有頂點都被標記為訪問過，此時D中有n-1條邊
• 提示：單獨看步驟很難理解，我們通過代碼來講解，比較好理解

圖解普利姆算法

代碼實現

public class PrimAlgorithm {public static void main(String[] args) {char[] data = new char[]{'A','B','C','D','E','F','G'};int verxs = data.length;//鄰接矩陣的關系使用二維數組表示,10000 這個大數，表示兩個點不聯通int [][]weight=new int[][]{{10000,5,7,10000,10000,10000,2}, // A{5,10000,10000,9,10000,10000,3}, // B{7,10000,10000,10000,8,10000,10000}, // C{10000,9,10000,10000,10000,4,10000}, // D{10000,10000,8,10000,10000,5,4}, // E{10000,10000,10000,4,5,10000,6}, // F{2,3,10000,10000,4,6,10000}}; // GMGraph mGraph = new MGraph(verxs);MinTree minTree = new MinTree();minTree.createGraph(mGraph,verxs,data,weight);minTree.showGraph(mGraph);minTree.prim(mGraph,0);} }class MinTree{/**** @param mGraph 圖對象* @param verxs 圖的個數* @param data 圖的頂點值* @param weight 圖的鄰接矩陣*/public void createGraph(MGraph mGraph,int verxs,char[] data, int[][] weight){for (int i = 0; i < verxs; i++) {mGraph.data[i] = data[i];for (int j = 0; j < verxs; j++) {mGraph.wight[i][j] = weight[i][j];}}}public void showGraph(MGraph mGraph){for(int[] col:mGraph.wight){System.out.println(Arrays.toString(col));}}/**** @param mGraph 圖* @param v 表示從第幾個頂點開始生產 傳入0 表示從A 開始*/public void prim(MGraph mGraph, int v) {int[] visited = new int[mGraph.verxs];visited[v] = 1;//記錄兩個頂點的下標int h1 = -1; //開始位置int h2 = -1; //結束位置//記錄最小的權值int minWeight = 10000;for (int n = 1; n < mGraph.verxs; n++) {//大循環表示選擇多少條邊 有n個頂點 連接只需要n-1個邊 所有n 從1開始for (int i = 0; i < mGraph.verxs; i++) {// 表示被訪問過的for (int j = 0; j < mGraph.verxs; j++) {//表示為訪問的if(visited[i]==1&&visited[j]==0&&mGraph.wight[i][j]<minWeight){minWeight = mGraph.wight[i][j];h1=i;h2=j;}}}//找到一條邊System.out.println("<"+mGraph.data[h1]+","+mGraph.data[h2]+"> => "+minWeight);minWeight = 10000;visited[h2] = 1;}} }class MGraph{int verxs;char[] data;int[][] wight;public MGraph(int verxs){this.verxs = verxs;data = new char[verxs];wight = new int[verxs][verxs];} }

打印信息

克魯斯卡爾算法

應場景-公交站問題

看一個應用場景和問題

• 某個市新增7個終點（A，B，C，D，E，F，G）,現再需要修路把7個站點連通
• 各個站點的距離用邊線表示權，比如A-B距離12公里
• 問：如果修路保證各個站點都能連通，并且修路總公里數最短。

克魯斯卡爾算法介紹

• 克魯斯卡爾算法，是用來求加權連通圖的最小生成樹算法
• 基本思想：按照權值從小到大的順序選擇n-1條邊，并保證這n-1條邊不構成回路
• 具體做法：首先構造一個只含n個頂點的森林，然后依權值從小到大從連通網中選擇邊加入到森林中，并使森林中部產生回路，直到森林編程一顆樹為止

克魯斯卡爾算法圖解說明

以城市公交問題來圖解說明 克魯斯卡爾算法原理與步驟
在含有n個頂點的聯調圖中選擇n-1條邊，構成一顆極小連通子圖，并使用該連通子圖中n-1條邊上權值之和達到最小，則稱其為連通網的最小生成樹。

1 將邊<E,F>加入R中
邊<E,F>的權值最小，因此將它加入到最小生成樹結果R中

2 將邊<C,D>加入R中
上一步操作后，邊<C,D>的權值最小，因此將它加入到最小生成樹結果R中

3 將邊<D,E>加入R中
上一步操作后，邊<D,E>的權值最小，因此將它加入到最小生成樹結果R中

4 將邊<B,F>加入R中
上一步操作后，邊<C,E>的權值最小，但<C,E>會和已有的邊構成回路；因此跳過<C,E>,同理跳過<C,F>。將邊<B,F> 加入到最小生成樹結果R中

5 將邊<E,G>加入R中
上一步操作后，邊<E,G>的權值最小，將邊<E,G> 加入到最小生成樹結果R中

6 將邊<A,B>加入R中
上一步操作后，邊<F,G>的權值最小，但<F,G>會和已有的邊構成回路；因此跳過<F,G>,同理跳過<B,C>。將邊<A,B> 加入到最小生成樹結果R中
此時最小生成樹構造完成！它包括的邊依次是<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>

總結：
根據前面介紹的克魯斯卡爾算法介紹，我們了解到克魯斯卡爾需要解決2個問題：

• 對圖的所有邊按照權值進行排序
• 將邊添加到最小生成樹時，怎么判斷是否形成了回路。
  問題1很好解決，問題2處理方式是：記錄頂點在"最小生成樹"中的終點，頂點的終點是"在最小生成樹中與它連通的最大頂點"。
  然后每次需要將一條邊添加到最小生成樹時，判斷該邊的兩個頂點的終點是否重合，重合的話則會構成回路

舉例說明：

在將<E,F> <C,D> <D,E> 加入到最小生成樹R中之后，這幾天邊的頂點就都有了終點：
1 C的終點是F
2 D的終點是F
3 E的終點是F
4 F的終點是F

關于終點的說明：
就是將所有頂點安裝從小到大的順序排列好之后：某個頂點的終點是"與它連通的最大頂點"
因此，接下來，雖然<C,E>是權值最小的邊。但是C和E的終點都是F，即他們的終點相同，因此，將<C,E>加入最小生成樹的話，就會形成回路。
這就是判斷回路的方式，也就是說，我們加入的邊的兩個頂點不能都指向同一個終點，否則將構成回路。

代碼實現

public class KruskalAlgoritm {private int[][] matrix;private char[] vertex;private int edgeNum;private static final int INF = Integer.MAX_VALUE;public static void main(String[] args) {char[] vertex = new char[]{'A','B','C','D','E','F','G'};//克魯斯卡爾算法的鄰接矩陣( 其實真正的有效值僅為一般 <AB><BA>是一樣的)int matrix[][] = { // 自己和自己為0/*A*//*B*//*C*//*D*//*E*//*F*//*G*//*A*/ { 0, 12, INF, INF, INF, 16, 14},/*B*/ { 12, 0, 10, INF, INF, 7, INF},/*C*/ { INF, 10, 0, 3, 5, 6, INF},/*D*/ { INF, INF, 3, 0, 4, INF, INF},/*E*/ { INF, INF, 5, 4, 0, 2, 8},/*F*/ { 16, 7, 6, INF, 2, 0, 9},/*G*/ { 14, INF, INF, INF, 8, 9, 0}};KruskalAlgoritm kruskal = new KruskalAlgoritm(vertex,matrix);kruskal.showMatrix();EData[] edgeData = kruskal.getEdgeData();System.out.println("未排序："+Arrays.toString(edgeData));kruskal.sortEData(edgeData);System.out.println("已排序："+Arrays.toString(edgeData));kruskal.kruskal(edgeData);}/*** 克魯斯卡爾算法* @param edgeData 傳入已經排序好的數組*/private void kruskal(EData[] edgeData) {int index = 0;// 最后結果數組的索引// 用于保存"已有最小生成數" 中的每個頂點 在最小生成數中的每個終點int[] ends = new int[edgeNum];//創建結果數組 保存最后的生成數EData[] res = new EData[vertex.length-1];// 遍歷edges 數組, 將邊添加到最小生成樹中, 判斷是準備加入的邊是否形成回路, 如果沒有 則加入resint p1;int p2;for (int i = 0; i < edgeNum; i++) {p1 =getPosition(edgeData[i].start); // 獲取到第i條邊的第一個頂點 (起點)p2 =getPosition(edgeData[i].end);// 獲取到第i條邊的第二個頂點 (終點)// 獲取 p1 這個頂點在已有的最小生成數中的終點是哪個int m = getEnd(ends,p1);int n = getEnd(ends,p2);// 判斷是否構成回路if(m!=n){ends[m]=n; // 設置m在"當前最小生成數" 中的終點為 nres[index++] = edgeData[i];}}System.out.println(Arrays.toString(res));}/*** 根據頂點獲取索引* @param ch* @return*/private int getPosition(char ch){for (int i = 0; i < vertex.length; i++) {if(vertex[i]==ch){return i;}}return -1;}/*個人理解判斷回路的方法還可以通過判斷是否訪問的節點來實現 如圖普利姆算法當中一樣 后期自己會嘗試實現看看*//*** 獲取下班為i的頂點的終點 用于判斷兩個頂點終點是否相同* @param ends 記錄了各個頂點對應的終點的下標是哪個* @param i 傳入的頂點對應的下標* @return 返回下標為i 的頂點的終點對應的下標*/private int getEnd(int[] ends,int i){while(ends[i]!=0){i = ends[i];}return i;}/*** 排序* @param edgeData*/public void sortEData(EData[] edgeData){for (int i = 0; i < edgeData.length; i++) {for (int j = i+1; j < edgeData.length; j++) {if(edgeData[i].weight>edgeData[j].weight){EData temp = edgeData[i];edgeData[i] = edgeData[j];edgeData[j] = temp;}}}}/*** 通過matrix鄰接矩陣來 獲取圖中的邊 EData[]放入數組中 后面需要遍歷該數組** @return EData[] 形式 [['A', 'B', 12],['B', 'F', 7] .....]*/public EData[] getEdgeData(){EData[] data = new EData[edgeNum];int index = 0;//該方式求出的值會將<AB><BA> 看著不同的值 // for (int i = 0; i < matrix.length; i++) { // for (int j = 0; j < matrix[i].length; j++) { // if(matrix[i][j]!=INF && matrix[i][j]!=0 ){ // data[index++] = new EData(vertex[i],vertex[j],matrix[i][j]); // } // } // }for (int i = 0; i < vertex.length; i++) {for (int j = i+1; j < vertex.length; j++) {if(matrix[i][j]!=INF && matrix[i][j]!=0 ){data[index++] = new EData(vertex[i],vertex[j],matrix[i][j]);}}}return data;}public KruskalAlgoritm(char[] vertex,int[][] matrix){this.vertex= vertex;this.matrix= matrix;for (int i = 0; i < vertex.length; i++) {for (int j = i+1; j < vertex.length; j++) {if(matrix[i][j]!=INF && matrix[i][j]!=0){edgeNum++;}}}}public void showMatrix(){for (int i = 0; i < matrix.length; i++) {System.out.println(Arrays.toString(matrix[i]));}} }/*** 創建一個類EData 它的對象實例就表示一條邊*/ class EData implements Comparable<EData>{public char start;// 邊的一個點 可以理解為起點public char end; // 邊的另外一個頂點 可以理解為終點public int weight;// 邊的權值public EData(char start,char end,int weight) {this.start = start;this.end = end;this.weight = weight;}@Overridepublic String toString() {return "EData<" + start + "," + end +"> = " + weight ;}@Overridepublic int compareTo(EData o) {//從小到大return this.weight-o.weight;} }

信息打印

迪杰斯特拉算法

應用場景-最短路徑問題

看一個應用場景和問題：

• 戰爭時期，某村有7個村莊（A，B，C，D，E，F，G）現有六個郵差，從G點出發，需要分別把郵件分別送到A，B，C，D，E，F，G六個村莊
• 各個村莊的距離用邊線表示（權），比如A-B距離5公里
  如何計算出G村莊到其他各個村莊的最短距離？

迪杰斯特拉算法介紹

迪杰斯特拉（Dijkstra）算法是典型最短路徑算法，用于計算一個節點到其他節點的最短路徑。它的主要特點是以起始為中心層層擴散（廣度優先搜索思想），直到擴散到終點為止
迪杰斯特拉算法過程

• 設置出發點為v，頂點集合V{v1,v2,vi…}，v到V中各墊點的距離構成距離構成距離集合dis,dis{d1，d2，di…},
  dis集合記錄著v到圖中各頂點的距離（到自身可以看作0，v到vi距離對應為di）
• 從dis中選擇值最小的di并移出dis,同時移出V集合中對應的頂點vi，此時的v到vi即為最短路徑
• 更新dis集合，更新規則為：比較v到V集合中頂點的距離值，與v通過vi到V集合中頂點的距離值，保留值較小的一個（同時也應該更新頂點的前驅節點為vi,表明是同vi達到的）
• 重復執行兩步驟，直到最短路徑頂點為目標頂點即可結束。

圖解過程

代碼實現

public class DijkstraAlgorithm {public static final int INF = 65535;public static void main(String[] args) {char[] vertexs = {'A','B','C','D','E','F','G'};int[][] matrix = new int[vertexs.length][vertexs.length];matrix[0]=new int[]{INF,5,7,INF,INF,INF,2};matrix[1]=new int[]{5,INF,INF,9,INF,INF,3};matrix[2]=new int[]{7,INF,INF,INF,8,INF,INF};matrix[3]=new int[]{INF,9,INF,INF,INF,4,INF};matrix[4]=new int[]{INF,INF,8,INF,INF,5,4};matrix[5]=new int[]{INF,INF,INF,4,5,INF,6};matrix[6]=new int[]{2,3,INF,INF,4,6,INF};Graph graph = new Graph(vertexs,matrix);graph.showGraph();graph.dijkstra(6);graph.showDijkstra();} }class Graph{private char[] vertexs;private int[][] matrix;private VisitedVertex visitedVertex;public Graph(char[] vertexs,int[][] matrix){this.vertexs = vertexs;this.matrix = matrix;}public void showGraph(){for (int i = 0; i < matrix.length; i++) {System.out.println(Arrays.toString(matrix[i]));}}/*** 迪杰斯特拉算法實現* @param index*/public void dijkstra(int index){this.visitedVertex = new VisitedVertex(vertexs.length,index);update(index);//更新index頂點 到周圍頂點的距離和前驅頂點for (int i = 0; i < vertexs.length; i++) {index = visitedVertex.updateArr(); //選擇并返回新的訪問頂點update(index);//更新index頂點 到周圍頂點的距離和前驅頂點}}public void showDijkstra(){visitedVertex.show();}/*** 更新index下標周圍頂點的距離 和頂點的前驅頂點* @param index*/private void update(int index){int d = 0;for (int i = 0; i < matrix[index].length; i++) {//出發頂點到index頂點的距離+從index頂點到距離到i頂點的距離d = visitedVertex.getDis(index)+matrix[index][i];//如果頂點i沒有被訪問過 且 小于出發點到i的距離就需要更新if(!visitedVertex.in(i) && d < visitedVertex.getDis(i)){visitedVertex.updatePre(i,index);//更新i頂點的前驅為index頂點visitedVertex.updateDis(i,d); // 更新出發頂點的j節點的距離}}} }class VisitedVertex{// 記錄每個頂點是否訪問過 1 訪問過 0 未訪問public int[] alreadyArr;// 每個下標對應的值為第一個頂點的下標public int[] preVisited;// 記錄出頂點到其他所有頂點的距離public int[] dis;/**** @param length 頂點數組長度* @param index 出發頂點對應的下標*/public VisitedVertex(int length,int index){this.alreadyArr = new int[length];this.preVisited = new int[length];this.dis = new int[length];//初始化dis為 最大值Arrays.fill(dis,DijkstraAlgorithm.INF);//設置起點為開始值alreadyArr[index] = 1;// 自己到自己的距離為0dis[index] = 0;}/*** 判斷index下標是否被訪問過* @param index* @return 訪問過 返回true 否則false*/public boolean in(int index){return alreadyArr[index] == 1;}/*** 更新index下標的距離* @param index 下標* @param d 距離*/public void updateDis(int index,int d){dis[index] = d;}/*** 更新pre為索引的頂點的前驅為index索引的節點* @param index 下標* @param pre 距離*/public void updatePre(int pre,int index){preVisited[pre] = index;}/*** 返回出發頂點到index頂點的距離* @param index* @return*/public int getDis(int index){return dis[index];}/*** 繼續選擇并返回新的訪問節點* 比如這里的G完后 就是A作為新的訪問頂點（不是出發點）* @return*/public int updateArr(){int min = DijkstraAlgorithm.INF;int index = 0;for (int i = 0; i <alreadyArr.length; i++) {if(alreadyArr[i]==0&&dis[i]<min){min = dis[i];index = i;}}alreadyArr[index] = 1;return index;}public void show(){System.out.println("alreadyArr");for (int i = 0; i < alreadyArr.length; i++) {System.out.print(alreadyArr[i] + " ");}System.out.println();System.out.println("preVisited");for (int i = 0; i < preVisited.length; i++) {System.out.print(preVisited[i] + " ");}System.out.println();System.out.println("dis");for (int i = 0; i < dis.length; i++) {System.out.print(dis[i] + " ");}System.out.println();System.out.println("------打印信息調整------");// 為了便于好看最短距離 打印信息調整 2 3 9 10 4 6 0char[] vertexs = {'A','B','C','D','E','F','G'};for (int i = 0; i < vertexs.length; i++) {System.out.print(vertexs[i]+"（"+dis[i]+")");}} }

信息打印

佛洛伊德算法

佛洛伊德算法介紹

• 和Dijkstra算法一樣，佛洛佛洛伊德算法也是一種用于尋找給定的加權圖中頂點間最短路徑的算法。該算法名稱以創始人之一命令
• 佛洛伊德算法計算圖中各個頂點之間的最短路徑
• 迪杰斯特拉算法用于計算圖中某一個頂點到其他頂點最短路徑
• 佛洛伊德算法VS迪杰斯特拉算法：迪杰斯特拉算法利用通過選定的訪問頂點，求出從出發訪問頂點到其他頂點的最短路徑：佛洛伊德算法中每個頂頂啊都是出發訪問點，所以需要將每一個頂點看做被訪問頂點，求出從每一個頂點到其他頂點的最短路徑。

佛洛伊德算法圖解分析

• 設置頂點vi到頂點vk的最短路徑已知lik,頂點vk到vj的最短路徑已知為lkj，頂點vi到vj的路徑為lij,則vi到vj的最短路徑為：min(lik+lkj)，vk的取值為圖中所有頂點，則可獲得vi到vj的最短路徑
• 至于vi到vk的最短路徑lik或者vk到vj的最短路徑lkj,是以同樣的方式獲得

佛洛伊德算法步驟
第一輪循環中，以A（下標為：0）作為中間頂點【即把A作為中間頂點的所有情況都進行遍歷，就會得到更新距離表 和前驅關系】；
分析如下：

• 以A頂點作為中間頂點是B->A->C的距離由N->9，同理C到B：C->A->G的距離由N->12，同理G到C
• 更換中間頂點，循環執行操作，知道所有頂點都作為中間頂點更新后，計算結束

代碼實現

public class FloydAlgorithm {public static void main(String[] args) {char[] vertex = {'A','B','C','D','E','F','G'};//創建鄰接矩陣int[][] matrix = new int[vertex.length][vertex.length];final int N = 65535;matrix[0] = new int[] { 0, 5, 7, N, N, N, 2 };matrix[1] = new int[] { 5, 0, N, 9, N, N, 3 };matrix[2] = new int[] { 7, N, 0, N, 8, N, N };matrix[3] = new int[] { N, 9, N, 0, N, 4, N };matrix[4] = new int[] { N, N, 8, N, 0, 5, 4 };matrix[5] = new int[] { N, N, N, 4, 5, 0, 6 };matrix[6] = new int[] { 2, 3, N, N, 4, 6, 0 };GraphFloyd floyd = new GraphFloyd(vertex.length,matrix,vertex);floyd.showGraph();floyd.floyd();System.out.println("-----算法計算后----------");floyd.showGraph();} }class GraphFloyd{private char[] vertex;//存放頂點的數組private int[][] dis;//存放從各個頂點出發 到其他頂點的距離private int[][] pre;//保存到達目標節點的前驅節點public GraphFloyd(int length,int[][] matrix,char[] vertex){this.vertex = vertex;this.dis = matrix;this.pre = new int[length][length];// 對pre數組初始化, 存放的是前驅頂點的下標 初始化每一行都是當前節點的下標for (int i = 0; i < length; i++) {Arrays.fill(pre[i],i);}}public void showGraph(){for (int k = 0; k < dis.length; k++) {for (int i = 0; i < dis.length; i++) {System.out.print(vertex[pre[k][i]]+" ");}System.out.println();}System.out.println("----到各個頂點的距離--");for (int k = 0; k < dis.length; k++) {for (int i = 0; i < dis.length; i++) {System.out.print(vertex[k]+"->"+vertex[i]+"("+dis[k][i]+") ");}System.out.println();}}public void floyd(){int len;//距離//從中間頂點的變量 k 是中間頂點下標for (int k = 0; k <vertex.length; k++) {//從i頂點開始出發for (int i = 0; i < vertex.length; i++) {// 到大j頂點for (int j = 0; j < vertex.length; j++) {// 從i ->k ->j 的距離len = dis[i][k]+dis[k][j];if(len<dis[i][j]){//小于當前的值dis[i][j]=len;//更新距離表pre[i][j]=pre[k][j];// 更新前驅頂點}}}}} }

信息打印

馬踏棋盤算法

馬踏棋盤算法介紹和游戲演示

• 馬踏棋盤算法也被稱為騎士周游問題
• 將馬隨機放在國際象棋8X8棋盤中Board[0_7][07]的某個方格中，馬按走棋規則（馬走日子）進行移動，要求每個方格只進入一次，走遍棋盤上全部64個方格
• 游戲演示：http://www.4399.com/flash/146267_2.html
  

圖解馬踏棋盤游戲實現

• 馬踏棋盤問題實際上是圖的深度優先搜索（DFS）的應用
• 如果使用回溯（就是深度優先搜索）來解決，假如馬兒踏了53個點，如圖：走到了第53個，坐標（1,0），發現已經走到盡頭，沒辦法，那就只能回退，
  查看其它的路徑，就在棋盤上不停的回溯…
  
  解決步驟與思路
• 創建棋盤chessBoard,是一個二維數組
• 將當初位置設置為已經訪問，然后根據當前位置，計算馬兒還能能走那些位置，并放入到一個集合中ArrayList，最多有8個位置，每走一步就使用step+1
• 遍歷ArrayList中存在的所有位置，看看那個是可以走通，如果可以走通，就繼續，走不通，就回溯
• 判斷馬兒是否完成了任務，使用step和應該走的步數比較，如果沒有達到數量，則表示沒有完成任務，將整個棋盤置0

注意：馬的不同做法（策略），會得到不同的結果，效率也會有影響

代碼實現

public class HorseChess {private static int x;//棋盤的列private static int y;//棋盤的行//標記各個位置是否被訪問過private static boolean[] visited;//標記棋盤所有位置是否被訪問過private static boolean finished;public static void main(String[] args) {//棋盤大小x = 6;y = 6;//其實位置int row = 2;int col = 4;int[][] chessBoard = new int[x][y];visited = new boolean[x*y];long start = System.currentTimeMillis();traversalChessBoard(chessBoard,row-1,col-1,1);long end = System.currentTimeMillis();System.out.println("功共耗時 " + (end - start) + "毫秒");for (int[] rows:chessBoard) {System.out.println(Arrays.toString(rows));}}private static void traversalChessBoard(int[][] chessBoard, int row, int col, int step) {//馬的其實位置設置chessBoard[row][col] = step;//記錄該空格為訪問過visited[row*x+col] = true;ArrayList<Point> listPoint = nextList(new Point(row, col));//遍歷集合while (!listPoint.isEmpty()){//取出走一步Point remove = listPoint.remove(0);//如果沒有被訪問就繼續 y 為行 x 為列if(!visited[remove.y*x+remove.x]){traversalChessBoard(chessBoard,remove.y,remove.x,step+1);}}//判斷是否成功走完// step < x * y 情況有兩種 棋盤到目前位置棋盤未走完 棋盤處于回溯過程if(x*y>step&&!finished){chessBoard[row][col]=0;visited[row*x+col] = false;}else{finished = true;}}/*** 根據當前位置point 計算馬兒 還能走那些位置* @param current* @return*/private static ArrayList<Point> nextList(Point current){ArrayList<Point> list = new ArrayList<Point>();Point point = new Point();//棋盤5的位置if((point.x=current.x-2)>=0&&(point.y=current.y-1)>=0){list.add(new Point(point));}//棋盤6的位置if((point.x=current.x-1)>=0&&(point.y=current.y-2)>=0){list.add(new Point(point));}//棋盤7的位置if((point.x=current.x+1)< x &&(point.y=current.y-2)>=0){list.add(new Point(point));}//棋盤0的位置if((point.x=current.x+2)< x &&(point.y=current.y-1)>=0){list.add(new Point(point));}//棋盤1的位置if((point.x=current.x+2)< x &&(point.y=current.y+1)<y){list.add(new Point(point));}//棋盤2的位置if((point.x=current.x+1)< x &&(point.y=current.y+2)<y){list.add(new Point(point));}//棋盤3的位置if((point.x=current.x-1)>=0 &&(point.y=current.y+2)<y){list.add(new Point(point));}//棋盤3的位置if((point.x=current.x-2)>=0 &&(point.y=current.y+1)<y){list.add(new Point(point));}return list;} }

信息打印

用貪心算法優化代碼：

public class HorseChess {private static int x;//棋盤的列private static int y;//棋盤的行//標記各個位置是否被訪問過private static boolean[] visited;//標記棋盤所有位置是否被訪問過private static boolean finished;public static void main(String[] args) {//棋盤大小x = 8;y = 8;//其實位置int row = 2;int col = 4;int[][] chessBoard = new int[x][y];visited = new boolean[x*y];long start = System.currentTimeMillis();traversalChessBoard(chessBoard,row-1,col-1,1);long end = System.currentTimeMillis();System.out.println("功共耗時 " + (end - start) + "毫秒");for (int[] rows:chessBoard) {System.out.println(Arrays.toString(rows));}}private static void traversalChessBoard(int[][] chessBoard, int row, int col, int step) {//馬的其實位置設置chessBoard[row][col] = step;//記錄該空格為訪問過visited[row*x+col] = true;ArrayList<Point> listPoint = nextList(new Point(row, col));sort(listPoint);//遍歷集合while (!listPoint.isEmpty()){//取出走一步Point remove = listPoint.remove(0);//如果沒有被訪問就繼續 y 為行 x 為列if(!visited[remove.y*x+remove.x]){traversalChessBoard(chessBoard,remove.y,remove.x,step+1);}}//判斷是否成功走完// step < x * y 情況有兩種 棋盤到目前位置棋盤未走完 棋盤處于回溯過程if(x*y>step&&!finished){chessBoard[row][col]=0;visited[row*x+col] = false;}else{finished = true;}}/*** 根據當前位置point 計算馬兒 還能走那些位置* @param current* @return*/private static ArrayList<Point> nextList(Point current){ArrayList<Point> list = new ArrayList<Point>();Point point = new Point();//棋盤5的位置if((point.x=current.x-2)>=0&&(point.y=current.y-1)>=0){list.add(new Point(point));}//棋盤6的位置if((point.x=current.x-1)>=0&&(point.y=current.y-2)>=0){list.add(new Point(point));}//棋盤7的位置if((point.x=current.x+1)< x &&(point.y=current.y-2)>=0){list.add(new Point(point));}//棋盤0的位置if((point.x=current.x+2)< x &&(point.y=current.y-1)>=0){list.add(new Point(point));}//棋盤1的位置if((point.x=current.x+2)< x &&(point.y=current.y+1)<y){list.add(new Point(point));}//棋盤2的位置if((point.x=current.x+1)< x &&(point.y=current.y+2)<y){list.add(new Point(point));}//棋盤3的位置if((point.x=current.x-1)>=0 &&(point.y=current.y+2)<y){list.add(new Point(point));}//棋盤3的位置if((point.x=current.x-2)>=0 &&(point.y=current.y+1)<y){list.add(new Point(point));}return list;}private static void sort(ArrayList<Point> list){list.sort((p1,p2)->{ArrayList<Point> list1 = nextList(p1);ArrayList<Point> list2 = nextList(p2);if(list1.size()>list2.size()){return 1;}else if(list1.size()<list2.size()){return -1;}else {return 0;}});} }

8X8優化前等了很久還是沒有打印信息

8X8優化后打印信息

至此花了近3個月終于學習完了數據結構與算法這部分知識，希望能入個門。

總結

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

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