- 近似算法的基本概念
很多實(shí)際應(yīng)用問題都是NP-完全問題上枕，這類問題很可能不存在多項(xiàng)式時(shí)間算法咐熙。一般而言，NP-完全問題可采用以下三種方式處理辨萍。如果問題的輸入規(guī)模較小棋恼，則可以利用搜索策略在指數(shù)時(shí)間內(nèi)求解問題。如果輸入規(guī)模較大锈玉，既可以利用隨機(jī)算法在多項(xiàng)式時(shí)間內(nèi)“高概率”地精確求解問題爪飘，也可以考慮在多項(xiàng)式時(shí)間內(nèi)求得問題的一個(gè)“近似解”。
近似算法是指能夠在多項(xiàng)式時(shí)間內(nèi)給出優(yōu)化問題的近似優(yōu)化解的算法拉背，近似算法不僅可用于近似求解NP-完全問題师崎，也可用于近似求解復(fù)雜度較高的P問題。
- 近似算法的性能分析
近似算法的性能分析包括時(shí)間復(fù)雜度分析椅棺、空間復(fù)雜度分析和近似精度分析犁罩，其中時(shí)間（空間）復(fù)雜度的分析同精確復(fù)雜度相同。近似精度分析是近似算法特有的两疚，它主要用于刻畫近似算法給出的近似解相比于問題優(yōu)化解的優(yōu)劣程度床估。目前，存在三種刻畫近似精度的度量诱渤，即近似比丐巫、相對(duì)誤差界和1+ε近似。
近似比：設(shè)A是一個(gè)優(yōu)化問題的近似算法勺美，A具有近似比（ratio bound） p(n), 如果max{C/C, C/C} ≤ p(n)鞋吉。其中n是輸入大小，C是A產(chǎn)生的解的代價(jià)励烦，C*是優(yōu)化解的代價(jià)。
相對(duì)誤差：對(duì)于任意輸入泼诱，近似算法的相對(duì)誤差定義為|C - C|/C,其中C是近似解的代價(jià)坛掠，C*是優(yōu)化解的代價(jià)。
相對(duì)誤差界：一個(gè)近似算法的相對(duì)誤差界為ε(n),如果|C-C|/C ≤ ε(n)。
近似模式：一個(gè)優(yōu)化問題的近似模式是一個(gè)以問題實(shí)例I和ε>0位輸入的算法屉栓。對(duì)于任意固定的ε舷蒲，近似模式是一個(gè)(1+ε)-近似算法。一個(gè)近似模式A(I,ε)稱為一個(gè)多項(xiàng)式時(shí)間近似模式友多，如果對(duì)于任意ε>0, A(I,ε)的運(yùn)行時(shí)間是|I|的多項(xiàng)式牲平。一個(gè)近似模式稱為完全多項(xiàng)式時(shí)間近似模式，如果它的運(yùn)行時(shí)間是關(guān)于I/ε和輸入實(shí)例大小n的多項(xiàng)式域滥。
