4悯辙，回溯法
回溯法是一種優(yōu)化的窮舉法。所謂窮舉法就是窮舉問題的所有可能性躲撰，直到發(fā)現(xiàn)解決問題的最佳解為止〖岵龋回溯法會有效地降低窮舉法帶來的高損耗瓤狐。
舉個栗子：
考慮對迷宮進(jìn)行遍歷
每當(dāng)遇到十字路口時便向一個固定的方向前進(jìn)批幌。假設(shè)這個方向是左础锐。對遇到的十字路口持續(xù)向左走荧缘，當(dāng)遇到死胡同便回溯到前一個路口并直走（此路口的左邊已被證實(shí)是走不通的）當(dāng)直走并遇到路口后繼續(xù)向左走，當(dāng)直走并遇到死胡同時回溯到前一個路口（此時這個路口只剩下右邊可以走了）信姓。當(dāng)向右走后仍遇到路口依然向左走绸罗，當(dāng)向右走并遇到死胡同后仍然回溯到前一個路口。此時這個路口已經(jīng)被證實(shí)是走不通的珊蟀，于是再向前回溯一個路口。
如此循環(huán)下去直到找到迷宮的出口
以上是回溯法的基本思想
????利用回溯法解決的問題有以下幾個特點(diǎn)：
1. 問題可以劃分為幾個不相關(guān)的子問題
2.幾個字問題有類似的求解方式
3. 如果子問題還可以劃分腻窒，便繼續(xù)對子問題進(jìn)行劃分
回溯法與分治法解決問題有相似之處磅崭，但回溯法的本質(zhì)是深度優(yōu)先搜索，在應(yīng)用回溯法時需要建立一個棧保存搜索路徑砸喻。而分治法實(shí)現(xiàn)的是遞歸。
回溯法的一個缺點(diǎn)是效率較低恩够。
5.概率算法
與確定性算法相比，概率算法不能得到精確的結(jié)果儡毕。但這并不意味著概率算法得不到正確的結(jié)果，而且在某些場合概率算法得到的正確結(jié)果的效率要比精確算法高很多腰湾。
又舉一個栗子：
如果一個國家要選舉一位總統(tǒng)，假設(shè)這個國家的所有公民都要參與選舉過程倒槐。那么如何在盡可能短的時間內(nèi)選出這位總統(tǒng)呢?
這里有兩種方式：
一種選舉方式為全民投票選舉附井，向所有公民發(fā)放選票，最后在集中起來進(jìn)行統(tǒng)計(jì)永毅，這種選舉方式可以保證得到精確的選舉結(jié)果。但這種方式最大的缺點(diǎn)就是周期過長着逐，過程繁瑣。
另一種方式是民意測驗(yàn)法耸别，向公民發(fā)放民意調(diào)查表县钥，調(diào)查總統(tǒng)候選人在人民當(dāng)中的支持率。這種方法的好處是時間周期短魁蒜，結(jié)果符合絕大多數(shù)選民的意愿，缺點(diǎn)是不夠精確锥咸。但在此例子中细移，決定選出的總統(tǒng)與大多數(shù)選民的意愿有決定性，所以可以認(rèn)為此方法得到的為合理的弧轧。在這個前提下，民意測驗(yàn)法可以說是一種又快又“準(zhǔn)”的方法了精绎。
概率算法涉及很多概率論與數(shù)理統(tǒng)計(jì)方面的知識
經(jīng)典的概率算法有蒙特卡洛（Monte Carlo）算法和拉斯維加斯（Las Vegas）算法。
