[科普中國]-分支因子

在計(jì)算機(jī)運(yùn)算、樹數(shù)據(jù)結(jié)構(gòu)、博弈論領(lǐng)域中，分支因子（branching factor）是每個(gè)結(jié)點(diǎn)下的子結(jié)點(diǎn)數(shù)，即出度。如果各個(gè)結(jié)點(diǎn)分支因子不同，則可以計(jì)算平均分支因子。例如，在國際象棋中，如把一步合法走法算作一個(gè)“結(jié)點(diǎn)”，那么平均分支因子據(jù)信約為35。這表示，棋手每一步走棋平均有大約35種合法走法。相比之下，圍棋的分支因子為250。

簡介分支因子有多種解釋，在計(jì)算機(jī)運(yùn)算中，分支因子是指從一步運(yùn)算進(jìn)行下一步運(yùn)算有多種選擇。在數(shù)據(jù)結(jié)構(gòu)中，樹由稱為結(jié)點(diǎn)的元素按照層次結(jié)構(gòu)的方式組織而成。層次結(jié)構(gòu)最頂端的結(jié)點(diǎn)稱為根。與根結(jié)點(diǎn)直接相連的結(jié)點(diǎn)稱為根的子結(jié)點(diǎn)，通常子結(jié)點(diǎn)本身也有屬于它們自己的子結(jié)點(diǎn)。除了根結(jié)點(diǎn)外，在這個(gè)層次體系中的每個(gè)結(jié)點(diǎn)都有單一的父結(jié)點(diǎn)，也就是與其直接相連的上級(jí)結(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)擁有多少個(gè)子節(jié)點(diǎn)取決于樹的類型，這個(gè)量值稱為樹的的分支因子，它決定了當(dāng)插入結(jié)點(diǎn)時(shí)樹的分支擴(kuò)展的速度。

一般來說，圖可分為有向圖和無向圖。有向圖的所有邊都有方向，即確定了頂點(diǎn)到頂點(diǎn)的一個(gè)指向；而無向圖的所有邊都是雙向的，即無向邊所連接的兩個(gè)頂點(diǎn)可以互相到達(dá)。在一些問題中，可以把無向圖當(dāng)作所有邊都是正向和負(fù)向的兩條有向邊組成。頂點(diǎn)的度是指和該頂點(diǎn)相連的邊的條數(shù)。特別是對(duì)于有向圖來說，頂點(diǎn)的出邊條數(shù)稱為該頂點(diǎn)的出度1，也可稱為分支因子。

因結(jié)點(diǎn)數(shù)呈指數(shù)增長，所以分支因子越大，需要遍歷所有分支的算法（如暴力搜索法）的計(jì)算量越大。例如，若分支因子為10，則當(dāng)前位置下一層會(huì)有10個(gè)結(jié)點(diǎn)，下兩層會(huì)有102即100個(gè)結(jié)點(diǎn)，下三層會(huì)有103即1,000個(gè)結(jié)點(diǎn)，依此類推。分支因子越大，指數(shù)爆炸越快。剪枝算法可以減小分支因子。

指數(shù)增長指數(shù)增長（包括指數(shù)衰減）指一個(gè)函數(shù)的增長率與其函數(shù)值成比例。在定義域?yàn)殡x散的且等差的情況下，也稱作幾何增長或幾何衰減（函數(shù)值是一個(gè)等比數(shù)列）?；蛑冈谀骋浑A段時(shí)間內(nèi)，應(yīng)用于持續(xù)增 長的基數(shù)上的不變的增長率。例如，以復(fù)利比例增長的儲(chǔ)蓄賬目；越集越 大的雪球；以年平均3%的速度增長的人口等。指數(shù)增長模型也稱作馬爾薩斯增長模型。

剪枝剪枝，就是通過某種判斷，避免一些不必要的遍歷過程，形象的說，就是剪去了搜索樹中的某些“枝條”，故稱剪枝。應(yīng)用剪枝優(yōu)化的核心問題是設(shè)計(jì)剪枝判斷方法，即確定哪些枝條應(yīng)當(dāng)舍棄，哪些枝條應(yīng)當(dāng)保留的方法。剪枝優(yōu)化三原則: 正確、準(zhǔn)確、高效的原則搜索算法，絕大部分需要用到剪枝。然而，不是所有的枝條都可以剪掉，這就需要通過設(shè)計(jì)出合理的判斷方法，以決定某一分支的取舍。 在設(shè)計(jì)判斷方法的時(shí)候，需要遵循一定的原則。

正確性

枝條不是愛剪就能剪的。 如果隨便剪枝，把帶有最優(yōu)解的那一分支也剪掉了的話，剪枝也就失去了意義。 所以，剪枝的前提是一定要保證不丟失正確的結(jié)果。

準(zhǔn)確性

在保證了正確性的基礎(chǔ)上，我們應(yīng)該根據(jù)具體問題具體分析，采用合適的判斷手段，使不包含最優(yōu)解的枝條盡可能多的被剪去，以達(dá)到程序“最優(yōu)化”的目的。 可以說，剪枝的準(zhǔn)確性，是衡量一個(gè)優(yōu)化算法好壞的標(biāo)準(zhǔn)。

高效性

設(shè)計(jì)優(yōu)化程序的根本目的，是要減少搜索的次數(shù)，使程序運(yùn)行的時(shí)間減少。 但為了使搜索次數(shù)盡可能的減少，我們又必須花工夫設(shè)計(jì)出一個(gè)準(zhǔn)確性較高的優(yōu)化算法，而當(dāng)算法的準(zhǔn)確性升高，其判斷的次數(shù)必定增多，從而又導(dǎo)致耗時(shí)的增多，這便引出了矛盾。 因此，如何在優(yōu)化與效率之間尋找一個(gè)平衡點(diǎn)，使得程序的時(shí)間復(fù)雜度盡可能降低，同樣是非常重要的。 倘若一個(gè)剪枝的判斷效果非常好，但是它卻需要耗費(fèi)大量的時(shí)間來判斷、比較，結(jié)果整個(gè)程序運(yùn)行起來也跟沒有優(yōu)化過的沒什么區(qū)別，這樣就太得不償失了。

本詞條內(nèi)容貢獻(xiàn)者為:

李嘉騫 - 博士 - 同濟(jì)大學(xué)