Java常用的算法有哪些

本文小編為大家詳細(xì)介紹“Java常用的算法有哪些”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“Java常用的算法有哪些”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來(lái)學(xué)習(xí)新知識(shí)吧。

貪心算法（greedy algorithm）  

經(jīng)典的應(yīng)用：比如霍夫曼編碼（Huffman Coding）、Prim 和 Kruskal 最小生成樹算法、還有 Dijkstra 單源最短路徑算法。  

貪心算法解決問(wèn)題的步驟  

第一步，當(dāng)我們看到這類問(wèn)題的時(shí)候，首先要聯(lián)想到貪心算法：針對(duì)一組數(shù)據(jù)，我們定義了限制值和期望值，希望從中選出幾個(gè)數(shù)據(jù)，在滿足限制值的情況下，期望值最大。  

類比到剛剛的例子，限制值就是重量不能超過(guò) 100kg，期望值就是物品的總價(jià)值。這組數(shù)據(jù)就是 5 種豆子。我們從中選出一部分，滿足重量不超過(guò) 100kg，并且總價(jià)值最大。  

第二步，我們嘗試看下這個(gè)問(wèn)題是否可以用貪心算法解決：每次選擇當(dāng)前情況下，在對(duì)限制值同等貢獻(xiàn)量的情況下，對(duì)期望值貢獻(xiàn)最大的數(shù)據(jù)。  

類比到剛剛的例子，我們每次都從剩下的豆子里面，選擇單價(jià)最高的，也就是重量相同的情況下，對(duì)價(jià)值貢獻(xiàn)最大的豆子。  

第三步，我們舉幾個(gè)例子看下貪心算法產(chǎn)生的結(jié)果是否是最優(yōu)的。大部分情況下，舉幾個(gè)例子驗(yàn)證一下就可以了。嚴(yán)格地證明貪心算法的正確性，是非常復(fù)雜的，需要涉及比較多的數(shù)學(xué)推理。  

貪心算法不工作的主要原因是，前面的選擇，會(huì)影響后面的選擇。  

貪心算法實(shí)戰(zhàn)分析  

1. 分糖果  

我們有 m 個(gè)糖果和 n 個(gè)孩子。我們現(xiàn)在要把糖果分給這些孩子吃，但是糖果少，孩子多（m<n），所以糖果只能分配給一部分孩子。每個(gè)糖果的大小不等，這 m 個(gè)糖果的大小分別是 s1，s2，s3，……，sm。除此之外，每個(gè)孩子對(duì)糖果大小的需求也是不一樣的，只有糖果的大小大于等于孩子的對(duì)糖果大小的需求的時(shí)候，孩子才得到滿足。假設(shè)這 n 個(gè)孩子對(duì)糖果大小的需求分別是 g1，g2，g3，……，gn。如何分配糖果，能盡可能滿足最多數(shù)量的孩子？  

我們可以把這個(gè)問(wèn)題抽象成，從 n 個(gè)孩子中，抽取一部分孩子分配糖果，讓滿足的孩子的個(gè)數(shù)（期望值）是最大的。這個(gè)問(wèn)題的限制值就是糖果個(gè)數(shù) m。  

我們每次從剩下的孩子中，找出對(duì)糖果大小需求最小的，然后發(fā)給他剩下的糖果中能滿足他的最小的糖果，這樣得到的分配方案，也就是滿足的孩子個(gè)數(shù)最多的方案。  

2. 錢幣找零  

這個(gè)問(wèn)題在我們的日常生活中更加普遍。假設(shè)我們有 1 元、2 元、5 元、10 元、20 元、50 元、100 元這些面額的紙幣，它們的張數(shù)分別是 c1、c2、c5、c10、c20、c50、c100。我們現(xiàn)在要用這些錢來(lái)支付 K 元，最少要用多少?gòu)埣垘拍兀?  

生活中，我們肯定是先用面值最大的來(lái)支付，如果不夠，就繼續(xù)用更小一點(diǎn)面值的，以此類推，最后剩下的用 1 元來(lái)補(bǔ)齊。在貢獻(xiàn)相同期望值（紙幣數(shù)目）的情況下，我們希望多貢獻(xiàn)點(diǎn)金額，這樣就可以讓紙幣數(shù)更少，這就是一種貪心算法的解決思路。  

3. 區(qū)間覆蓋  

假設(shè)我們有 n 個(gè)區(qū)間，區(qū)間的起始端點(diǎn)和結(jié)束端點(diǎn)分別是 [l1, r1]，[l2, r2]，[l3, r3]，……，[ln, rn]。我們從這 n 個(gè)區(qū)間中選出一部分區(qū)間，這部分區(qū)間滿足兩兩不相交（端點(diǎn)相交的情況不算相交），最多能選出多少個(gè)區(qū)間呢？  

這個(gè)處理思想在很多貪心算法問(wèn)題中都有用到，比如任務(wù)調(diào)度、教師排課等等問(wèn)題。  

這個(gè)問(wèn)題的解決思路是這樣的：我們假設(shè)這 n 個(gè)區(qū)間中最左端點(diǎn)是 lmin，最右端點(diǎn)是 rmax。這個(gè)問(wèn)題就相當(dāng)于，我們選擇幾個(gè)不相交的區(qū)間，從左到右將 [lmin, rmax] 覆蓋上。我們按照起始端點(diǎn)從小到大的順序?qū)@ n 個(gè)區(qū)間排序。  

我們每次選擇的時(shí)候，左端點(diǎn)跟前面的已經(jīng)覆蓋的區(qū)間不重合的，右端點(diǎn)又盡量小的，這樣可以讓剩下的未覆蓋區(qū)間盡可能的大，就可以放置更多的區(qū)間。這實(shí)際上就是一種貪心的選擇方法。  

如何用貪心算法實(shí)現(xiàn)霍夫曼編碼？  

霍夫曼編碼用這種不等長(zhǎng)的編碼方法，編碼字符。要求各個(gè)字符的編碼之間，不會(huì)出現(xiàn)某個(gè)編碼是另一個(gè)編碼前綴的情況。把出現(xiàn)頻率比較多的字符，用稍微短一些的編碼；出現(xiàn)頻率比較少的字符，用稍微長(zhǎng)一些的編碼。  

假設(shè)我有一個(gè)包含 1000 個(gè)字符的文件，每個(gè)字符占 1 個(gè) byte（1byte=8bits），存儲(chǔ)這 1000 個(gè)字符就一共需要 8000bits，那有沒(méi)有更加節(jié)省空間的存儲(chǔ)方式呢？  

假設(shè)我們通過(guò)統(tǒng)計(jì)分析發(fā)現(xiàn)，這 1000 個(gè)字符中只包含 6 種不同字符，假設(shè)它們分別是 a、b、c、d、e、f。而 3 個(gè)二進(jìn)制位（bit）就可以表示 8 個(gè)不同的字符，所以，為了盡量減少存儲(chǔ)空間，每個(gè)字符我們用 3 個(gè)二進(jìn)制位來(lái)表示。那存儲(chǔ)這 1000 個(gè)字符只需要 3000bits 就可以了，比原來(lái)的存儲(chǔ)方式節(jié)省了很多空間。不過(guò)，還有沒(méi)有更加節(jié)省空間的存儲(chǔ)方式呢？  

a(000)、b(001)、c(010)、d(011)、e(100)、f(101)  

霍夫曼編碼是一種十分有效的編碼方法，廣泛用于數(shù)據(jù)壓縮中，其壓縮率通常在 20%～90% 之間。  

霍夫曼編碼不僅會(huì)考察文本中有多少個(gè)不同字符，還會(huì)考察每個(gè)字符出現(xiàn)的頻率，根據(jù)頻率的不同，選擇不同長(zhǎng)度的編碼?；舴蚵幋a試圖用這種不等長(zhǎng)的編碼方法，來(lái)進(jìn)一步增加壓縮的效率。如何給不同頻率的字符選擇不同長(zhǎng)度的編碼呢？根據(jù)貪心的思想，我們可以把出現(xiàn)頻率比較多的字符，用稍微短一些的編碼；出現(xiàn)頻率比較少的字符，用稍微長(zhǎng)一些的編碼。  

編碼不等長(zhǎng)，如何讀出來(lái)解析？  

對(duì)于等長(zhǎng)的編碼來(lái)說(shuō)，我們解壓縮起來(lái)很簡(jiǎn)單。比如剛才那個(gè)例子中，我們用 3 個(gè) bit 表示一個(gè)字符。在解壓縮的時(shí)候，我們每次從文本中讀取 3 位二進(jìn)制碼，然后翻譯成對(duì)應(yīng)的字符。但是，霍夫曼編碼是不等長(zhǎng)的，每次應(yīng)該讀取 1 位還是 2 位、3 位等等來(lái)解壓縮呢？這個(gè)問(wèn)題就導(dǎo)致霍夫曼編碼解壓縮起來(lái)比較復(fù)雜。為了避免解壓縮過(guò)程中的歧義，霍夫曼編碼要求各個(gè)字符的編碼之間，不會(huì)出現(xiàn)某個(gè)編碼是另一個(gè)編碼前綴的情況。  

假設(shè)這 6 個(gè)字符出現(xiàn)的頻率從高到低依次是 a、b、c、d、e、f。我們把它們編碼下面這個(gè)樣子，任何一個(gè)字符的編碼都不是另一個(gè)的前綴，在解壓縮的時(shí)候，我們每次會(huì)讀取盡可能長(zhǎng)的可解壓的二進(jìn)制串，所以在解壓縮的時(shí)候也不會(huì)歧義。經(jīng)過(guò)這種編碼壓縮之后，這 1000 個(gè)字符只需要 2100bits 就可以了。  

盡管霍夫曼編碼的思想并不難理解，但是如何根據(jù)字符出現(xiàn)頻率的不同，給不同的字符進(jìn)行不同長(zhǎng)度的編碼呢？  

利用大頂堆，根據(jù)頻率放字符。  

分治算法  

分治算法（divide and conquer）的核心思想其實(shí)就是四個(gè)字，分而治之 ，也就是將原問(wèn)題劃分成 n 個(gè)規(guī)模較小，并且結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題，遞歸地解決這些子問(wèn)題，然后再合并其結(jié)果，就得到原問(wèn)題的解。  

分治算法是一種處理問(wèn)題的思想，遞歸是一種編程技巧。實(shí)際上，分治算法一般都比較適合用遞歸來(lái)實(shí)現(xiàn)。分治算法的遞歸實(shí)現(xiàn)中，每一層遞歸都會(huì)涉及這樣三個(gè)操作：  

• 分解：將原問(wèn)題分解成一系列子問(wèn)題；

• 解決：遞歸地求解各個(gè)子問(wèn)題，若子問(wèn)題足夠小，則直接求解；

• 合并：將子問(wèn)題的結(jié)果合并成原問(wèn)題。

分治算法能解決的問(wèn)題，一般需要滿足下面這幾個(gè)條件：  

• 原問(wèn)題與分解成的小問(wèn)題具有相同的模式；

• 原問(wèn)題分解成的子問(wèn)題可以獨(dú)立求解，子問(wèn)題之間沒(méi)有相關(guān)性

• 具有分解終止條件，也就是說(shuō)，當(dāng)問(wèn)題足夠小時(shí)，可以直接求解；

• 可以將子問(wèn)題合并成原問(wèn)題，而這個(gè)合并操作的復(fù)雜度不能太高，否則就起不到減小算法總體復(fù)雜度的效果了。

分治算法應(yīng)用舉例分析  

如何編程求出一組數(shù)據(jù)的有序?qū)€(gè)數(shù)或者逆序?qū)€(gè)數(shù)呢？  

拿每個(gè)數(shù)字跟它后面的數(shù)字比較，看有幾個(gè)比它小的。我們把比它小的數(shù)字個(gè)數(shù)記作 k，通過(guò)這樣的方式，把每個(gè)數(shù)字都考察一遍之后，然后對(duì)每個(gè)數(shù)字對(duì)應(yīng)的 k 值求和，最后得到的總和就是逆序?qū)€(gè)數(shù)。不過(guò)，這樣操作的時(shí)間復(fù)雜度是 O(n^2)。  

我們可以將數(shù)組分成前后兩半 A1 和 A2，分別計(jì)算 A1 和 A2 的逆序?qū)€(gè)數(shù) K1 和 K2，然后再計(jì)算 A1 與 A2 之間的逆序?qū)€(gè)數(shù) K3。那數(shù)組 A 的逆序?qū)€(gè)數(shù)就等于 K1+K2+K3。借助歸并排序算法  

給 10GB 的訂單文件按照金額排序這樣一個(gè)需求？  

我們就可以先掃描一遍訂單，根據(jù)訂單的金額，將 10GB 的文件劃分為幾個(gè)金額區(qū)間。比如訂單金額為 1 到 100 元的放到一個(gè)小文件，101 到 200 之間的放到另一個(gè)文件，以此類推。這樣每個(gè)小文件都可以單獨(dú)加載到內(nèi)存排序，最后將這些有序的小文件合并，就是最終有序的 10GB 訂單數(shù)據(jù)了。  

回溯算法  

應(yīng)用場(chǎng)景：深度優(yōu)先搜索，正則表達(dá)式匹配、編譯原理中的語(yǔ)法分析。很多經(jīng)典的數(shù)學(xué)問(wèn)題都可以用回溯算法解決，比如數(shù)獨(dú)、八皇后、0-1 背包、圖的著色、旅行商問(wèn)題、全排列等等  

回溯的處理思想，有點(diǎn)類似枚舉搜索。我們枚舉所有的解，找到滿足期望的解。為了有規(guī)律地枚舉所有可能的解，避免遺漏和重復(fù)，我們把問(wèn)題求解的過(guò)程分為多個(gè)階段。每個(gè)階段，我們都會(huì)面對(duì)一個(gè)岔路口，我們先隨意選一條路走，當(dāng)發(fā)現(xiàn)這條路走不通的時(shí)候（不符合期望的解），就回退到上一個(gè)岔路口，另選一種走法繼續(xù)走。  

八皇后問(wèn)題  

我們有一個(gè) 8x8 的棋盤，希望往里放 8 個(gè)棋子（皇后），每個(gè)棋子所在的行、列、對(duì)角線都不能有另一個(gè)棋子。  

1.0-1 背包  

很多場(chǎng)景都可以抽象成這個(gè)問(wèn)題模型。這個(gè)問(wèn)題的經(jīng)典解法是動(dòng)態(tài)規(guī)劃，不過(guò)還有一種簡(jiǎn)單但沒(méi)有那么高效的解法，那就是今天講的回溯算法。  

我們有一個(gè)背包，背包總的承載重量是 Wkg?，F(xiàn)在我們有 n 個(gè)物品，每個(gè)物品的重量不等，并且不可分割。我們現(xiàn)在期望選擇幾件物品，裝載到背包中。在不超過(guò)背包所能裝載重量的前提下，如何讓背包中物品的總重量最大？  

對(duì)于每個(gè)物品來(lái)說(shuō)，都有兩種選擇，裝進(jìn)背包或者不裝進(jìn)背包。對(duì)于 n 個(gè)物品來(lái)說(shuō)，總的裝法就有 2^n 種，去掉總重量超過(guò) Wkg 的，從剩下的裝法中選擇總重量最接近 Wkg 的。不過(guò)，我們?nèi)绾尾拍懿恢貜?fù)地窮舉出這 2^n 種裝法呢？  

回溯方法：我們可以把物品依次排列，整個(gè)問(wèn)題就分解為了 n 個(gè)階段，每個(gè)階段對(duì)應(yīng)一個(gè)物品怎么選擇。先對(duì)第一個(gè)物品進(jìn)行處理，選擇裝進(jìn)去或者不裝進(jìn)去，然后再遞歸地處理剩下的物品。  

動(dòng)態(tài)規(guī)劃  

動(dòng)態(tài)規(guī)劃比較適合用來(lái)求解最優(yōu)問(wèn)題，比如求最大值、最小值等等。它可以非常顯著地降低時(shí)間復(fù)雜度，提高代碼的執(zhí)行效率。  

0-1 背包問(wèn)題  

對(duì)于一組不同重量、不可分割的物品，我們需要選擇一些裝入背包，在滿足背包最大重量限制的前提下，背包中物品總重量的最大值是多少呢？  

思路：  

（1）把整個(gè)求解過(guò)程分為 n 個(gè)階段，每個(gè)階段會(huì)決策一個(gè)物品是否放到背包中。每個(gè)物品決策（放入或者不放入背包）完之后，背包中的物品的重量會(huì)有多種情況，也就是說(shuō)，會(huì)達(dá)到多種不同的狀態(tài)，對(duì)應(yīng)到遞歸樹中，就是有很多不同的節(jié)點(diǎn)。  

（2）我們把每一層重復(fù)的狀態(tài)（節(jié)點(diǎn)）合并，只記錄不同的狀態(tài)，然后基于上一層的狀態(tài)集合，來(lái)推導(dǎo)下一層的狀態(tài)集合。我們可以通過(guò)合并每一層重復(fù)的狀態(tài)，這樣就保證每一層不同狀態(tài)的個(gè)數(shù)都不會(huì)超過(guò) w 個(gè)（w 表示背包的承載重量），也就是例子中的 9。  

劃分n個(gè)階段，每一個(gè)階段基于上一個(gè)階段推導(dǎo)，動(dòng)態(tài)地往前推進(jìn)，就避免了重復(fù)計(jì)算。  

用回溯算法解決這個(gè)問(wèn)題的時(shí)間復(fù)雜度 O(2^n)，是指數(shù)級(jí)的。那動(dòng)態(tài)規(guī)劃解決方案的時(shí)間復(fù)雜度是多少呢？  

耗時(shí)最多的部分就是代碼中的兩層 for 循環(huán)，所以時(shí)間復(fù)雜度是 O(n*w)。n 表示物品個(gè)數(shù)，w 表示背包可以承載的總重量。我們需要額外申請(qǐng)一個(gè) n 乘以 w+1 的二維數(shù)組，對(duì)空間的消耗比較多。所以，有時(shí)候，我們會(huì)說(shuō)，動(dòng)態(tài)規(guī)劃是一種空間換時(shí)間的解決思路。  

0-1 背包問(wèn)題升級(jí)版  

對(duì)于一組不同重量、不同價(jià)值、不可分割的物品，我們選擇將某些物品裝入背包，在滿足背包最大重量限制的前提下，背包中可裝入物品的總價(jià)值最大是多少呢？  

什么樣的問(wèn)題適合用動(dòng)態(tài)規(guī)劃來(lái)解決呢？  

一個(gè)模型三個(gè)特征  

一個(gè)模型：多階段決策最優(yōu)解模型  

三個(gè)特征：  

• 最優(yōu)子結(jié)構(gòu)，問(wèn)題的最優(yōu)解包含子問(wèn)題的最優(yōu)解

• 無(wú)后效性，第一層含義是，在推導(dǎo)后面階段的狀態(tài)的時(shí)候，我們只關(guān)心前面階段的狀態(tài)值，不關(guān)心這個(gè)狀態(tài)是怎么一步一步推導(dǎo)出來(lái)的。第二層含義是，某階段狀態(tài)一旦確定，就不受之后階段的決策影響。（后面的不影響前面的。）

• 重復(fù)子問(wèn)題，不同的決策序列，到達(dá)某個(gè)相同的階段時(shí)，可能會(huì)產(chǎn)生重復(fù)的狀態(tài)。

兩種動(dòng)態(tài)規(guī)劃解題思路總結(jié)  

1. 狀態(tài)轉(zhuǎn)移表法  

一般能用動(dòng)態(tài)規(guī)劃解決的問(wèn)題，都可以使用回溯算法的暴力搜索解決。畫出遞歸樹。從遞歸樹中，我們很容易可以看出來(lái)，是否存在重復(fù)子問(wèn)題，以及重復(fù)子問(wèn)題是如何產(chǎn)生的  

找到重復(fù)子問(wèn)題之后，接下來(lái)，我們有兩種處理思路，第一種是直接用回溯加“備忘錄”的方法，來(lái)避免重復(fù)子問(wèn)題。從執(zhí)行效率上來(lái)講，這跟動(dòng)態(tài)規(guī)劃的解決思路沒(méi)有差別。第二種是使用動(dòng)態(tài)規(guī)劃的解決方法，狀態(tài)轉(zhuǎn)移表法。  

我們先畫出一個(gè)狀態(tài)表。狀態(tài)表一般都是二維的，所以你可以把它想象成二維數(shù)組。其中，每個(gè)狀態(tài)包含三個(gè)變量，行、列、數(shù)組值。我們根據(jù)決策的先后過(guò)程，從前往后，根據(jù)遞推關(guān)系，分階段填充狀態(tài)表中的每個(gè)狀態(tài)。最后，我們將這個(gè)遞推填表的過(guò)程，翻譯成代碼，就是動(dòng)態(tài)規(guī)劃代碼了。  

需要很多變量來(lái)表示，那對(duì)應(yīng)的狀態(tài)表可能就是高維的，比如三維、四維。那這個(gè)時(shí)候，我們就不適合用狀態(tài)轉(zhuǎn)移表法來(lái)解決了。一方面是因?yàn)楦呔S狀態(tài)轉(zhuǎn)移表不好畫圖表示，另一方面是因?yàn)槿四X確實(shí)很不擅長(zhǎng)思考高維的東西。  

2. 狀態(tài)轉(zhuǎn)移方程法  

我們需要分析，某個(gè)問(wèn)題如何通過(guò)子問(wèn)題來(lái)遞歸求解，也就是所謂的最優(yōu)子結(jié)構(gòu)。根據(jù)最優(yōu)子結(jié)構(gòu)，寫出遞歸公式，也就是所謂的狀態(tài)轉(zhuǎn)移方程。有了狀態(tài)轉(zhuǎn)移方程，代碼實(shí)現(xiàn)就非常簡(jiǎn)單了。一般情況下，我們有兩種代碼實(shí)現(xiàn)方法，一種是遞歸加“備忘錄”，另一種是迭代遞推。  

min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))  

我要強(qiáng)調(diào)一點(diǎn)，不是每個(gè)問(wèn)題都同時(shí)適合這兩種解題思路。有的問(wèn)題可能用第一種思路更清晰，而有的問(wèn)題可能用第二種思路更清晰，所以，你要結(jié)合具體的題目來(lái)看，到底選擇用哪種解題思路。

狀態(tài)轉(zhuǎn)移表法解題思路大致可以概括為，回溯算法實(shí)現(xiàn) - 定義狀態(tài) - 畫遞歸樹 - 找重復(fù)子問(wèn)題 - 畫狀態(tài)轉(zhuǎn)移表 - 根據(jù)遞推關(guān)系填表 - 將填表過(guò)程翻譯成代碼。狀態(tài)轉(zhuǎn)移方程法的大致思路可以概括為，找最優(yōu)子結(jié)構(gòu) - 寫狀態(tài)轉(zhuǎn)移方程 - 將狀態(tài)轉(zhuǎn)移方程翻譯成代碼。

如何量化兩個(gè)字符串的相似度？

編輯距離指的就是，將一個(gè)字符串轉(zhuǎn)化成另一個(gè)字符串，需要的最少編輯操作次數(shù)（比如增加一個(gè)字符、刪除一個(gè)字符、替換一個(gè)字符）。編輯距離越大，說(shuō)明兩個(gè)字符串的相似程度越??；相反，編輯距離就越小，說(shuō)明兩個(gè)字符串的相似程度越大。對(duì)于兩個(gè)完全相同的字符串來(lái)說(shuō)，編輯距離就是 0。

編輯距離有多種不同的計(jì)算方式，比較著名的有萊文斯坦距離（Levenshtein distance）和最長(zhǎng)公共子串長(zhǎng)度（Longest common substring length）。其中，萊文斯坦距離允許增加、刪除、替換字符這三個(gè)編輯操作，最長(zhǎng)公共子串長(zhǎng)度只允許增加、刪除字符這兩個(gè)編輯操作。

萊文斯坦距離和最長(zhǎng)公共子串長(zhǎng)度，從兩個(gè)截然相反的角度，分析字符串的相似程度。萊文斯坦距離的大小，表示兩個(gè)字符串差異的大??；而最長(zhǎng)公共子串的大小，表示兩個(gè)字符串相似程度的大小。

兩個(gè)字符串 mitcmu 和 mtacnu 的萊文斯坦距離是 3，最長(zhǎng)公共子串長(zhǎng)度是 4。

如何編程計(jì)算萊文斯坦距離？

這個(gè)問(wèn)題是求把一個(gè)字符串變成另一個(gè)字符串，需要的最少編輯次數(shù)。整個(gè)求解過(guò)程，涉及多個(gè)決策階段，我們需要依次考察一個(gè)字符串中的每個(gè)字符，跟另一個(gè)字符串中的字符是否匹配，匹配的話如何處理，不匹配的話又如何處理。所以，這個(gè)問(wèn)題符合多階段決策最優(yōu)解模型。

推薦算法

利用向量的距離，求相似成度。

搜索：如何用A*搜索算法實(shí)現(xiàn)游戲中的尋路功能？

那如何快速找出一條接近于最短路線的次優(yōu)路線呢？

這個(gè)快速的路徑規(guī)劃算法，就是我們今天要學(xué)習(xí)的A* 算法。實(shí)際上，A* 算法是對(duì) Dijkstra 算法的優(yōu)化和改造。

通過(guò)這個(gè)頂點(diǎn)跟終點(diǎn)之間的直線距離，也就是歐幾里得距離來(lái)近似地估計(jì)這個(gè)頂點(diǎn)跟終點(diǎn)的路徑長(zhǎng)度（注意：路徑長(zhǎng)度跟直線距離是兩個(gè)概念）

這個(gè)距離記作 h(i)（i 表示這個(gè)頂點(diǎn)的編號(hào)），專業(yè)的叫法是啟發(fā)函數(shù)（heuristic function）

因?yàn)闅W幾里得距離的計(jì)算公式，會(huì)涉及比較耗時(shí)的開根號(hào)計(jì)算，所以，我們一般通過(guò)另外一個(gè)更加簡(jiǎn)單的距離計(jì)算公式，那就是曼哈頓距離（Manhattan distance）

曼哈頓距離是兩點(diǎn)之間橫縱坐標(biāo)的距離之和。計(jì)算的過(guò)程只涉及加減法、符號(hào)位反轉(zhuǎn)，所以比歐幾里得距離更加高效。

int hManhattan(Vertex v1, Vertex v2) { // Vertex 表示頂點(diǎn)，后面有定義  

    return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);  

}  

f(i)=g(i)+h(i)，頂點(diǎn)與起點(diǎn)之間的路徑長(zhǎng)度 g(i)，頂點(diǎn)到終點(diǎn)的路徑長(zhǎng)度估計(jì)值h(i). f(i) 的專業(yè)叫法是估價(jià)函數(shù)（evaluation function）。

A* 算法就是對(duì) Dijkstra 算法的簡(jiǎn)單改造, f(i) 最小的先出列。

它跟 Dijkstra 算法的代碼實(shí)現(xiàn)，主要有 3 點(diǎn)區(qū)別：

• 優(yōu)先級(jí)隊(duì)列構(gòu)建的方式不同。A* 算法是根據(jù) f 值（也就是剛剛講到的 f(i)=g(i)+h(i)）來(lái)構(gòu)建優(yōu)先級(jí)隊(duì)列，而 Dijkstra 算法是根據(jù) dist 值（也就是剛剛講到的 g(i)）來(lái)構(gòu)建優(yōu)先級(jí)隊(duì)列；

• A* 算法在更新頂點(diǎn) dist 值的時(shí)候，會(huì)同步更新 f 值；

• 循環(huán)結(jié)束的條件也不一樣。Dijkstra 算法是在終點(diǎn)出隊(duì)列的時(shí)候才結(jié)束，A* 算法是一旦遍歷到終點(diǎn)就結(jié)束。

讀到這里，這篇“Java常用的算法有哪些”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過(guò)才能領(lǐng)會(huì)，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。