第一篇：LTE物理層信道檢測算法總結文檔
信道均衡算法總結
信道均衡技術研究的焦點主要集中在計算復雜度與誤碼性能的折中，即用最小的計算代價獲得最優(yōu)的檢測效果。
為了恢復信號放送方的信息，接收端必須知道如下信息： 1)信道的增益矩陣H。2)加性高斯白噪聲n。
信號接收信息Y可以表示：
Y?Hx?n
一、傳統(tǒng)檢測方法： 1.1、線性檢測算法：
線性檢測思想：在MIMO系統(tǒng)的接收信號中，存在不同的發(fā)射天線間的信號的相互干擾。相對于某一根發(fā)射天線的信號子流，其他天線上信號則看成干擾。相對于某一根發(fā)射天線的信號子流，其他發(fā)射天線上信號則看成干擾，將接收信號乘以一個線性濾波矩陣，使得干擾信號從被檢測信號中消除，這就是“干擾置零”的主要思想。
線性檢測要求系統(tǒng)中的接收天線數(shù)N不小于發(fā)射天線數(shù)M，否則對于線性檢測而言，即使在沒有噪聲的情況下也無法獲得好的技術檢測效果。
1.1.1 ZF算法
線性迫零ZF算法是利用信道傳輸矩陣H的偽逆矩陣H+作為線性運算組合器來實現(xiàn)信號分離的一種檢測算法。迫零的譯碼算法就是找到一個加權矩陣W，使其滿足以下關系：
WiHj?1,i?j
WiHj?0,i!?j
其中Wi,Hj分別表示加權矩陣W的第i行與信道矩陣H的第j列(滿足這個條件的加權矩陣就是H的偽逆矩陣H+)；
ZF算法步驟如下：
1)先根據(jù)上述原則得到并計算加權矩陣H??(HHH)?1HH； 2)將加權矩陣左乘接收信號，式子變?yōu)镠?r?s?H?n；
3)直接利用公式S?Q(Hr)進行量化，從而對信號進行譯碼。
ZF算法把來自每個發(fā)送天線的信號當作希望得到的信號，而剩下的部分當作干擾，所以能夠完全禁止各個之間的互擾。
1.1.2 MMSE算法
為了改善ZF算法的性能，可以在設計濾波器矩陣的時候?qū)⒃肼暤挠绊懣紤]進去，這就是MMSE檢測。MMSE檢測是通過濾波矩陣G的設計使得實際傳輸?shù)男盘柡蜑V波輸出信號之間均方誤差MSE保持最小。
MMSE算法在一定程度上改善了迫零算法的性能，它是用一個新的矩陣HMMSE來代替迫零算法中的H.利用以下原則得到加權矩陣: ?^?HMMSE?argmin(E{||HMMSEr?s||2})，其中E代表期望值。
MMSE算法步驟如下：
?2?1H1)先根據(jù)上述原則得到并計算加權矩陣HMMSE?(HH?I)H，其中：?2為噪聲方
?差；?為發(fā)送信號功率。如果對每根發(fā)射天線信號能量進行歸一化，則在公式中?可以省略，此時?=1.2)將加權矩陣左乘以接收信號，式子變?yōu)镠MMSEr?HMMSEHs?HMMSEn。
H3)直接利用公式S?Q(HMMSEr)進行量化，從而對信號進行譯碼． ^
1.2、干擾消除檢測算法
線性檢測沒有利用多天線的分集增益，為了得到分集增益可以利用判決反饋的思想，將已判決的信號反饋回去，提高檢測的可靠性。判決反饋可以用于同一符號的檢測。干擾消除是將判決反饋用于不同符號間的檢測，將從待檢測信號中消除已檢測出信號的影響，從而降低了檢測信號中的干擾量，提高判決的可靠性，同時積累了分集增益。
干擾消除包括干擾消除SIC、并行干擾消除PIC以及可以進一步提高性能的排序串行干擾消除OSIC。這幾種檢測方法的基礎都是基于不同準則的線性檢測。并行干擾消除是采用并行的方式來消除符號間的干擾，即在所有的信號被解調(diào)之后，同時將干擾接收信號去除。
1.2.1 串行干擾消除(SIC)串行干擾消除在檢測到干擾信號波形時，一次一次地將干擾從接收信號中去除，核心思想是通過對接收信號進行遞歸估計，即先選擇一種線性檢測算法(ZF算法或者MMSE算法)對某一種發(fā)射天線符號進行檢測，然后抵消該信號對其他天線上信號的干擾，再依次對各個發(fā)射天線上的發(fā)送信號進行線性檢測、干擾抵消，直到估計出全部的發(fā)送符號。
SIC處理過程步驟：
1)干擾置零。從剩余未檢測的符號中任選一個進行檢測，方便起見，可以每次選擇第一個符號作為待檢測符號。
X1?GY1（1）
X1?Q(X1)（2）
式(1)中G1為基于某種線性檢測準則(ZF、MMSE)的濾波矩陣的第一行，X1為第一層發(fā)送符號的濾波輸出，Q(.)為判決操作，判斷出的符號作為第一層所發(fā)送符號的估計值。
2)干擾消除。假設判決正確，從接收信號中消除掉該信號的影響，產(chǎn)生一個新的系統(tǒng)模型。
~~Y?Y?H1X1?HX?N(3)其中式(3)中H1為信道矩陣H(Nr*Nt)的第一列，表示第一根發(fā)送天線到所有接收天線的信道響應。H?[H2,H3,...HNT]表示刪除了第一列后的NR?(NT?1)維的等效信道矩陣，~~~~X?[X2,X3,...XNT]T表示刪除了第一個發(fā)送天線上發(fā)送符號后(NT?1)?1維等效發(fā)送符號，Y表示消除第一層符號的影響的接收信號。
然后返回步驟(1),接著進行下一個符號的檢測，每一次檢測出的符號對應不同的發(fā)射天線，直至檢測出所有的發(fā)送符號。
1.2.2 OSIC OSIC檢測算法是一類改進的SIC檢測算法，它在傳統(tǒng)未排序SIC算法干擾置零和干擾消除操作的基礎上，增加了符號檢測的排序操作，可以有效地降低SIC檢測過程中誤差傳播的可能性，從而大大提高系統(tǒng)的檢測性能。
OSIC檢測算法的基本思想在于執(zhí)行多級的、優(yōu)化排序的迭代干擾消除。OSIC的操作步驟是：排序、干擾置零和干擾消除。1)首先根據(jù)一定的排序準則，從當前所有剩余未檢測的發(fā)送數(shù)據(jù)流中選擇出一個待檢測數(shù)據(jù)流；
2)然后通過采用某種零化準則的濾波完成該數(shù)據(jù)流檢測；
3)最后從接收信號中消除被檢測數(shù)據(jù)流的干擾，準備進入下一級。
4)排序、干擾置零和干擾消除操作不斷重復、直至經(jīng)過多級處理以后，所有發(fā)送數(shù)據(jù)符號均被檢測為止。~~1.3 最優(yōu)檢測算法
最大似然(ML)算法是MIMO系統(tǒng)中最優(yōu)的信號均衡算法，其基本原理是：將接收信號對所有的可能的發(fā)送符號域進行全局搜索，找到與接收信號距離最小的發(fā)射符號作為原始的發(fā)送符號，即使給定r的情況下x的最大似然估計值達到最大，其實現(xiàn)方法是由所有調(diào)制星座圖的點計算得出的。
最大似然檢測算法其計算公式為：
X?argmax?(y|x)
其中：
??(y|x)?(det(?R))?1exp(?(y?Hx)HR?1(y?Hx))?(???)2?NRexp(?y?Hx/??)22
這里，R?E(??H)???2I。由上式最大似然檢測算法可簡化為:
X?argminy?Hx
由上式可知，最大似然準則等效于最小歐式距離準則。由此可知最大似然檢測算法的復雜度與候選的x的數(shù)目成正比，換句話說其復雜度隨著發(fā)射天線數(shù)目、每天線平均傳輸速率的增長呈指數(shù)增長，因此當發(fā)射天線數(shù)目較多、傳輸速率較高時最大似然檢測算法的復雜度極高，難以實現(xiàn)。
二、新算法
2.1 球形譯碼算法(SD算法)球形譯碼算法是一種性能接近于最大似然檢測而復雜度低的檢測方法，將系統(tǒng)實數(shù)話后用球形檢測進行譯碼，復雜度明顯降低。SD算法和ML算法不同是：ML算法是在整個向量空間上搜索最有可能的發(fā)送向量，使得該向量經(jīng)過信道后于接收信號向量歐式距離最小，SD算法是在以接收信號點Y為圓心，r為半徑的空間內(nèi)搜索最有可能的發(fā)送向量。
算法思路：球形譯碼的作用就是判斷Hs空間中的點是否在以x為球心、半徑為d的超球體里面，下面討論具體如何接收信號x是否在半徑為d的超球體內(nèi)，條件如下所示：
?2d2?||x?Hs||2（4）
其中x為接收信號矢量，s為發(fā)送信號矢量，H為沖擊響應矩陣，d為搜索半徑，d其實為允許的誤差范圍，如果d太大就增加了搜索范圍，從而增加復雜度。
對沖擊響應矩陣H進行QR分解，H矩陣大小為n行m列，其中n?m，m為發(fā)送天線，n為接收天線。
H?QR（5）
其中R是m?m的上三角矩陣，并且Q=[Q1Q2]是一個n?n正交矩陣，矩陣Q1和Q2分別為矩陣Q的前m列和n?m列，因此公式(4)可變換為：
?Q1*?2?R??R?2**2d?x?[Q1Q2]??s??*?x???s?Q1x?Rs?Q2x(6)
?0??0??Q2?式(6)中*表示共軛轉(zhuǎn)置，將右側移項得到： d?Q2x*令y?Q1x，d?d?Q2x，公式改寫為： '22*22*222?Q1*x?Rs(7)
2d??(yi??ri,jsj)(8)
'2i?1j?im2其中ri,j是矩陣R的元素，R是上三角矩陣。公式(8)可展開如下：
d'2?(ym?rm,msm)2?(ym?1?rm?1,msm?rm?1,m?1sm?1)2?...(9)式(9)中右邊第一項只與sm有關，第二項只有sm，sm?1有關。后面各項以此類推。因此Hs在超球體里面的一個必要條件是： d'2?(ym?rm,msm)2，將該條件寫成區(qū)間的形式為：
??d'?ym??d'?ym????sm???(10)?rm,m???rm,m??式(10)中符號????????分別表示向上和向下取整數(shù)，由(10)可以解得sm的值，但是我們知道式(10)還不是Hs在超球體內(nèi)的充分條件，當選中滿足條件的sm時，計算下一個值sm?1，'2'22這時需要更新半徑。令dmm?1,msm，根據(jù)公?1?d?(ym?rm,msm)，并且ym?1|m?ym?1?r式(9)可知：
''??dm??dm??1?ym?1|m?1?ym?1|m?s???m?1??(11)
?rm?1,m?1???rm?1,m?1??由此再確定一個sm?1，繼續(xù)計算下一個值sm?2，直到s1。
以上分析了球形譯碼算法尋找內(nèi)點的過程，下面給出SD算法的偽代碼步驟：
*1)輸入?yún)?shù)Q=[Q1Q2],R，x，y?Q1x，d。'22*2)設置k?m，dm?d?Q2x，ym|m?1?ym。
''3)計算sk的界限，設置上界UB(sk)???(dk?yk|k?1)/rk,k??，sk???(?d?ym)/rk,k???1。
24)sk?sk?1.判斷如果sk?UB(sk)，那么跳至步驟6，否則跳至步驟5。5)k?k?1，如果k?m?1，終止計算，否則，跳至步驟4。6)如果k?1，跳至7；否則k?k?1，yk|k?1?yk?2dk'2?dk'2?1?(yk?1|k?2?rk?1,k?1sk?1)跳轉(zhuǎn)至步驟3。
j?k?1?rmk,jsj，'2'22Hsysd?d?(y?rs)7)找到結果，將數(shù)組，以及與接收信號的差距m111,11保存并跳轉(zhuǎn)至步驟4.算法sd.m文件見matlab程序
算法性能比較: ZF
第二篇：LTE常見故障總結
LTE-FZHA（RL25）常見故障總結
目錄
LTE-FZHA（RL25）常見故障總結............................................................................................1
1.System module failure(0010)........................................................................................3 2.BTS reference clock missing(1898)................................................................................3 3.Configuration error: Unit initialization failure(0012).....................................................3 4.Configuration error: Not enough HW for LCR(1868).....................................................4 5.Configuration error: Power level not supported(4008).................................................4 6.Cell configuration data distribution failed(6253)..........................................................4 7.Failure in optical RP3 interface(4064)...........................................................................5 8.Failure in optical RP3 interface(0010)...........................................................................5 9.Baseband bus failure(3020,1906).................................................................................5 10.RF module failure(6259，1911、1711、1712)..........................................................5 11.Cell power failure(4090)..............................................................................................6 12.GPS Receiver alarm: Control Interface not available（4011）..................................6 13.X2 interface setup failure（6304）.............................................................................6 14.Transport layer connection failure in X2 interface.......................................................6 15.Failure in replaceable baseband unit...........................................................................7 16.Temperature alarm(0002)............................................................................................7
17.VSWR（1838）............................................................................................................7 18.Failure in optical RP3 interface(2004).........................................................................8 19.GPS時鐘盒閃斷，時鐘信號不正常，無法識別RRU...............................................8 20.Failure in optical RP3 interface（2000）.....................................................................8 21.光纖交叉連接..............................................................................................................8 22.基站始終無法建立S1連接，只到configed狀態(tài)....................................................9 23.GPS時鐘盒閃斷，時鐘信號不正常，無法識別RRU...............................................9 24.某一個小區(qū)的RRU無法識別.....................................................................................9 25.BBU版本無法識別....................................................................................................10 26.校準初步排查............................................................................................................10 27.本地IP地址和路由正常，ping不通MME和網(wǎng)關................................................11 28.TRS文件始終無法生效.............................................................................................11 29.三種疑難告警............................................................................................................12 30.遠程ping不通基站...................................................................................................12 31.風扇告警....................................................................................................................12 32.BTSlog有l(wèi)ink消息，但是pinger始終不亮............................................................12 33.駐波問題....................................................................................................................13 34.pinger正常，但是SM里小區(qū)顯示橙黃色告警.....................................................13 35.幾個特列....................................................................................................................13 36.FOSI 和FOSN的光功率范圍....................................................................................13 37.不同頻段RRU類型...................................................................................................13 1 38.MAC綁定及載波沖突...............................................................................................14 39.傳輸不通....................................................................................................................14 40.升級完成后出現(xiàn)駐波告警........................................................................................14 1.System module failure(0010)引起原因：
由于天氣溫度過高或者機房溫度過高，導致BBU的熱量散發(fā)不出去，引起的告警，一般表現(xiàn)是第三小區(qū)掛死，嚴重的可能會整站掛死，甚至會燒壞BBU。抑或是光模塊出現(xiàn)問題導致出現(xiàn)此告警。處理方法：
1、由于是高溫引起，基站要降溫并重啟BBU.若是BBU長期處于高溫狀態(tài)，會導致BBU內(nèi)部的芯片燒壞，到最后只能替換BBU
2、若是因為光模塊導致，則可以更換光模塊，則可以解決此問題。
2.BTS reference clock missing(1898)引起原因：一般導致此故障有兩個原因：
1、高溫導致比較常見，由于高溫時間過長，光模塊過熱，導致BBU和RRU失去連接，而后會出現(xiàn)此告警。
2、時鐘盒出現(xiàn)故障。
3、時鐘線與GPS頭的連接線接頭（避雷器接口）沒有做好，接收不到時鐘信號。
4、時鐘線和時鐘盒的連接不好。處理方法：
1、高溫引起，基站要降溫，等待一段時間后并重啟BBU.2、時鐘盒故障，更換時鐘盒；
3、GPS線頭沒有接好，重新做一下從GPS引下來的饋線到避雷器的頭子，使其能夠正常接觸。
4、若是時鐘線損壞，則更換時鐘線；若是時鐘線和時鐘盒接頭沒有接好，則接好接頭。
3.Configuration error: Unit initialization failure(0012)引起原因：
1、高溫導致小區(qū)掛死，軟重啟后會出現(xiàn)此告警
2、高溫導致基站自動重啟出現(xiàn)此告警 處理發(fā)法：
1、高溫引起，基站要降溫并重啟BBU。
2、重新COMISSION基站，即重新把基站的集成文件（SCFC）和傳輸文件（Config）重新傳入BBU內(nèi)，重啟后一般可以恢復正常。4.Configuration error: Not enough HW for LCR(1868)引起原因：以3小區(qū)基站配置來說明，由于集成文件已經(jīng)配置好了，若是某一小區(qū)丟失或兩個、三個小區(qū)的RRU都識別不到，則會出現(xiàn)此告警。
1、高溫導致光模塊過熱，跟光纖的連接中斷
2、光纖沒有插好
3、光纖斷了
4、RRU壞了
5、SCFC文件配置有問題 處理方法：
1、高溫引起，基站要降溫并重啟BBU。
2、將光纖拔下來，重新插好
3、更換損壞的光纖
4、更換RRU
5、重新配置SCFC文件，如果是二小區(qū)的基站，不能將SCFC文件做成三小區(qū)的配置，否則也會出此告警。
5.Configuration error: Power level not supported(4008)引起原因：
1、BBU上的FSMF到FBBA之間的電源連接線沒有插好，導致供電不足
2、BBU自身的問題 處理方法：
1、重新拔插這些電源線，使之接觸正常
2、說是BBU自身的問題，則是有些可以不用拔插，直接重啟基站就可以解決此問題。
6.Cell configuration data distribution failed(6253)引起原因：
基站運行一段時間由于自身問題導致，在此也說不清楚為什么會出現(xiàn)此問題，最大的可能性就是BBU加載好的文件一般存儲在它的FLASH芯片里面，運行一段時間后文件出錯，未能成功讀取到SCFC文件，導致基站出現(xiàn)此告警
處理方法：
由于重啟基站后此問題即可消失，所以一般處理的方式為重啟基站，在重啟的過程中，基站會重新讀取索引目錄Filedirectory，重新加載基站的配置文件，此過程會擦除原先在Flasn里面的數(shù)據(jù)，這樣基站就能正常工作了。7.Failure in optical RP3 interface(4064)引起原因：
1、光模塊損壞導致輔口讀不到光纖消息
2、溫度過高，導致輔口光模塊故障，讀取不到光纖消息
3、輔口的光纖斷了 處理方法：
1、更換輔口的光模塊，問題得到解決
2、下電直接重啟，或是下電后將光模塊拔出，冷卻一陣再插入卡槽內(nèi)，加好光纖，加電起來后此告警消失
3、光纖損壞導致此問題，需要更換光纖，此問題最為麻煩，需要工程隊配合，一般更換光纖后都能好（前提是把1、2都做過一遍了，告警得不到解決的情況下，更換光纖）。
8.Failure in optical RP3 interface(0010)引起原因：
1、高溫導致小區(qū)兩光纖傳輸中斷，BBU讀不到RRU消息
2、高溫導致小區(qū)兩光模塊出現(xiàn)問題
處理方法：
此問題處理的方法一般為下點重啟，問題都可以得到解決，但是如果機房或者綜合柜的溫度還是很高的話，過不了多久，大概10分鐘左右，此告警還會出現(xiàn)，所以需要做的是打開綜合柜的門，進行散熱處理，或是增加空調(diào)設備，降低室內(nèi)溫度，如果基站在室外，則沒有什么好的辦法，只能將BBU拿出來，放在綜合柜外面。
9.Baseband bus failure(3020,1906)引起原因：
1、BUS線沒有插好
2、BBU內(nèi)部主板的問題 處理方法：
1、重新拔插BUS線，使之連接正常
2、BBU內(nèi)部主板的問題有的可以通過下電重啟解決此問題，但是有的只能更換BBU，此問題才能得到解決。
10.RF module failure(6259，1911、1711、1712)引起原因：
1、光模塊損壞導致
2、RRU出現(xiàn)故障導致
處理方法：
1、若是告警號為1711（主）或1712（輔），則分別更換主輔側的光模塊即可解決問題。
2、告警號為1911或者是6259的時候，則需要更換RRU，一般都可以解決此類故障。
11.Cell power failure(4090)引起原因：
1、高溫導致供給FBBA的電流減少，導致功率不足
2、Vendor文件不匹配 處理方法：
1、高溫引起，基站要降溫并重啟BBU
2、更換跟天線匹配的正確的Vendor文件
12.GPS Receiver alarm: Control Interface not available（4011）
引起原因：
GPS時鐘盒工作不正常
處理方法：
1、重啟時鐘盒
2、拔插連接BBU和時鐘盒的時鐘線
13.X2 interface setup failure（6304）
引起原因：
X2鏈路連接建立失敗，需要建立X2鏈路連接
處理方法：
1、如果鄰基站存在，則鄰基站好了以后，此告警自然消失
2、如果鄰基站不存在，則需要在鄰區(qū)關系表里面講此鏈路的連接配置刪除，既可以消除此告警。
14.Transport layer connection failure in X2 interface 引起原因：
鄰小區(qū)沒有Onair,即基站未能正常起來工作 處理方法：
1、刪除鄰區(qū)關系
2、是鄰小區(qū)正常工作
15.Failure in replaceable baseband unit 引起原因：
1、FSMF和FBBA之間連接不好導致
2、FBBA硬件問題 處理方法：
1、重啟BBU
2、檢查FSMF和FBBA之間的連線
3、更換FBBA板件
16.Temperature alarm(0002)引起原因：
1、機房或者綜合柜溫度過高
2、BBU風扇轉(zhuǎn)速過快或者過慢
處理方法：
1、檢查機房空調(diào)是否正常工作，溫度是否正常。
2、檢查綜合柜是否散熱良好
3、檢查BBU的風扇轉(zhuǎn)速是否正常，一般可以看到此類告警，若是不正常，則需要更換風扇。
17.VSWR（1838）
引起原因：
1、RRU內(nèi)部的耦合器脫落，倒是發(fā)射端口出現(xiàn)駐波
2、天線跟BBU內(nèi)的Vendor文件不匹配，出現(xiàn)駐波
3、饋線頭子沒有做好，進水了，出現(xiàn)駐波
4、饋線有問題，出現(xiàn)駐波
5、光模塊也會導致駐波（很少見，我沒見過，但是聽說過）處理方法：
1、對于RRU損壞導致的駐波，則更換RRU，只能如此解決
2、若是天線和Vendor文件不匹配導致的告警，則更換相對應的Vendor文件
3、進水了則需要晾干或者更換饋線
4、饋線有問題則直接更換
5、光模塊有問題，可以通過更換光模塊來解決。
18.Failure in optical RP3 interface(2004)引起原因：
1、軟件問題
2、硬件問題
處理方法：
1、更換軟件版本，此告警有的基站可以消失
2、更換硬件，此告警可以消失
對于此告警，實在是難以有一個定論，曾經(jīng)研發(fā)的人為此告警一天打了5個補丁還是解決不了，到現(xiàn)在也不知道怎么辦，只有不停的更換軟件包，更換硬件，更換光模塊來消除此告警。
19.GPS時鐘盒閃斷，時鐘信號不正常，無法識別RRU 正常情況下，小的時鐘盒信號燈為常綠，如果出現(xiàn)綠色指示燈不斷閃爍則GPS信號不正常。
如果燈閃的情況為一長二短，則為GPS饋線短路，如果燈閃的情況為一長一短，則為GPS饋線開路。
20.Failure in optical RP3 interface（2000）
引起原因：此告警基本是因為溫度過高，但是光模塊還能工作，但又受到影響，出現(xiàn)的告警，或者是光模塊故障導致
解決辦法：
1、更換光模塊
2、下電重啟，若是基站處于正常溫度下，則可以保持正常，不再出此告警。
21.光纖交叉連接
對于室外型宏基站（FZHA，s111），開通后正常的FZHA的框號為1.1.1、1.3.1、1.4.1(normal FZHA rack no.png)。已發(fā)現(xiàn)有部分基站開通后的FZHA的框號為1.1.1、1.2.1、1.3.1(abnormal FZHA rack no.png)。
對于這種情況，基站無告警，但對于第一、二小區(qū)的業(yè)務測試會造成影響。原因可能是第一小區(qū)的輔光纖與第二小區(qū)的主光纖交叉錯接。1、3、4代表主光口
22.基站始終無法建立S1連接，只到configed狀態(tài)
這種情況一般是基站發(fā)了S1連接請求，但是核心網(wǎng)側沒有回，在SM里面會有6308的告警（S1 interface setup failure），這個時候我們會誤認為是核心網(wǎng)側沒有配這個站的數(shù)據(jù)或沒配對，其實核心網(wǎng)側不需要配置任何數(shù)據(jù)。所有的information都由ENB上報。下面是MME的輸出：
MCC MNCENB ID ENB IP S1 CONN AMOUNT === === ===== ======================================= 460 08 13 172.16.2.16 3 460 08 106 172.16.2.137 0 460 08 108 172.16.2.139 16 S1口通了之后，ENB正常接入網(wǎng)絡，MME側就能看見有關的信息。所以，基站側開通時，不外乎2個問題：
1.傳輸不通：需要核對傳輸側數(shù)據(jù)是否配對。比如：ENB IP地址，網(wǎng)關，S1-C控制地址，VLAN ID等。
2.傳輸通了，S1口不通：需要核對ENB側 MCC,MNC,ENBID是否正確。特別是ENBID，不能與其它站沖突。截止到現(xiàn)在，99%的ENB S1口不通，是由于ENBID沖突造成的。SCTP的端口號36412如果都是諾西的設備，就不會出問題。
總之，在ENB接入EPC的過程中，MME只是起著等待接入，接入確認的作用。
23.GPS時鐘盒閃斷，時鐘信號不正常，無法識別RRU 正常情況下，時鐘盒信號燈為常綠，如果出現(xiàn)綠色指示燈不斷閃爍則GPS信號不正常。如果燈閃的情況為一長二短，則為GPS饋線短路；如果燈閃的情況為一長一短，則為GPS饋線開路。這兩種情況一般只需重做GPS頭子就行。
還有一種情況是燈閃的時間間隔相同，則為時鐘盒模式選擇錯誤，只需把時鐘盒上的模式開關撥到GNSS就行。
24.某一個小區(qū)的RRU無法識別
現(xiàn)象是：該小區(qū)的RRU能ping通，但是在BTSlog里面無法讀出RRU的版本，SiteManger里面也無法識別RRU。
既然小區(qū)光纖同步?jīng)]問題，而BTSlog和SM卻又同時識別不到RRU的版本，按照RL15時的經(jīng)驗只可能是RRU的productCode丟失，所以從RRU里面，通過log –a提取RRU的log（F01_startup.zip和F01_runtime.zip），從該RRU的啟動log里面，可以看到如圖1-1顯示的信息：
圖1-1 該小區(qū)RRU啟動log 而正常RRU啟動log里面，應為如圖1-2所示的信息：
圖1-2 正常RRU啟動log 對比可以看出，原因應該是productCode和Serial number丟失造成。在RRU里面，使用eeprom命令，手動寫入productCode和Serial number，重啟基站后，小區(qū)恢復正常。
25.BBU版本無法識別
BBU版本無法識別主要表現(xiàn)在SM讀到的版本為“?”，這個問題也是在1800之后出現(xiàn)的，主要是因為往BBU里傳文件時出錯引起系統(tǒng)切換，重啟后就識別不到版本了。
對此嘗試過很多手段，包括重升PS、重傳fs1、重灌基站包和重刷flash都不行。既然這個問題是系統(tǒng)切換時造成的那能不能再讓它切換一次？于是問研發(fā)要了一條關于切換的命令，具體步驟如下：
1)通過將FileDirectory里面的“?”寫回版本號，再放回flash里面 2)保證備區(qū)的FileDirectory里版本號不是“?” 3)在FCTB里執(zhí)行命令：uboot_env get，查看正在運行的區(qū)域，如果是fs1，則執(zhí)行命令: uboot_env set active_partition=2，將系統(tǒng)切換至fs2 4)重啟BBU，重啟后一般情況下能恢復正常版本，不行的話可以再次嘗試以上方法。
26.校準初步排查
如果發(fā)現(xiàn)某個小區(qū)的校準有問題，比如說2小區(qū)的校準有問題，那么我們更換小區(qū)110 和小區(qū)2的光纖位置（也就是OptIF1和OptIF3更換，OptIF2和OptIF6更換），看看校準不好的小區(qū)是否有變化：
（1）如果校準不好的小區(qū)變到了第1小區(qū)，那么可能是RRU或者射頻連線的問題（2）如果校準不好的小區(qū)還是第2小區(qū)，那么可能就是eNB的問題 對于(1)類問題，我們要繼續(xù)看看是哪個path有問題，如下面的log：
AntIdx(7)值偏大，則須檢查對應第8通道的跳線是否接好。如果所有path都不好的話，則可以嘗試sitemanager block、unblock這個小區(qū)，看是否恢復正常，如果沒有校準打印，則直接重啟。以下是各個參數(shù)的定義：
Timeoff 波動不要太大，能穩(wěn)定就可以
Ampratio 是原始天線信號計算出的天線x對參考天線的幅度比 Finalampratio 是最后ULPHY給出的調(diào)整幅度比，不會>1 Maxtxantampratio 是7組幅度比中最大值，代表了RRU 8個通道之間幅度的差異
27.本地IP地址和路由正常，ping不通MME和網(wǎng)關
先檢查光電轉(zhuǎn)換器上面是否有5個綠燈。如果電口燈未亮，檢查eNB到光電轉(zhuǎn)換器的網(wǎng)線；
如果光口燈未亮，檢查光電轉(zhuǎn)換器到PTN的光纖是否連接正確； 如果1000M燈未亮，檢查網(wǎng)線的質(zhì)量；
如果指示燈都正常的話，則致電PTN工程師核對PTN的端口和傳輸數(shù)據(jù)，尤其是VLAN和容量。
28.TRS文件始終無法生效
當傳完fs1文件或升完級后，TRS文件在SM里始終無法sending出去，將其上傳至runfs1trs_datadb根目錄下重啟基站也不生效；
此時可以嘗試重刷PS來解決，生效后BBU上的傳輸指示燈會變綠！29.三種疑難告警
（1）Cell power failure 原因：RF received low power from BTS 解決方法：1.Check Pmax and txPowerScaling value 2.Check vendor file 3.Replace FSMF or FBBA（2）RF module failure 原因：LNA burned 解決方法：Replace RRU HW或BBU HW或FBBA（3）Baseband bus failure 原因：基帶總線配置被硬件，軟件，DSP或LTX拒絕 解決方法：更換BBU到兩塊FBBA的數(shù)據(jù)線或直接更換BBU 30.遠程ping不通基站
遠程ping不通有以下幾種可能：（1）網(wǎng)管IP沒配或配錯
（2）該站之前正常，但是后來上站發(fā)現(xiàn)vlan數(shù)據(jù)又被做到PTN2-5口，導致遠程ping不通；
（3）光電轉(zhuǎn)換器到BBU的網(wǎng)線有問題，諾西采購的這批網(wǎng)線還不如地攤上賣的靠譜，運行一段時間后，竟然會導致傳輸中斷
（4）PTN上的光模塊突然之間出問題了
（5）基站正常運行一段時間后TRS文件丟失（6）PTN被托管了
（7）機房斷電、BBU或光電轉(zhuǎn)換器被下電
以上可能大多數(shù)都需去現(xiàn)場結合實際情況來判斷，并采取相應的解決方法！
31.風扇告警
風扇告警可能是風扇過速、低速或不轉(zhuǎn)，一半是風扇本身的問題，可以通過更換風扇來解決，一半是由于BBU出了問題，而不轉(zhuǎn)也可能是因為風扇電源未插好。
另外有些風扇告警時有時無，需結合實際情況來判斷。
32.BTSlog有l(wèi)ink消息，但是pinger始終不亮
這個問題在18630版本下很常見，據(jù)說是因為該版本對光口質(zhì)量要求高，因為我試過將版本降到16200時問題就消失了，升上來后又復現(xiàn)了，解決方法如下：
（1）整站下電（2）更換光模塊
（3）單獨上電問題小區(qū)
（4）將問題小區(qū)一根光纖拔掉 33.駐波問題
駐波問題很常見，主要有以下幾種：
（1）跳線未插或未插好
（2）RRU耦合器脫落，導致駐波固定在RRU某一通道（3）天線問題
（4）Vendor文件沒有和天線型號對應
SM里面顯示的某通道駐波比告警是指RRU上對應的某通道，不是天線的，而校準+1則和RRU對應！
34.pinger正常，但是SM里小區(qū)顯示橙黃色告警
岳峰鎮(zhèn)臺中這個站之前很正常，運行一段時間后二小區(qū)無法識別，遠程重啟基站后該小區(qū)報4064告警。
上站下電重啟基站后該小區(qū)光纖同步正常，但是SM里小區(qū)顯示橙黃色告警，更換BBU側光模塊后問題依舊，最后更換RRU側光模塊問題解決。
35.幾個特列
（1）金榜食府->溫度告警->整站掛掉 :溫度過高會導致光口異常，小區(qū)退服；
（2）傳輸數(shù)據(jù)做好后，PTN網(wǎng)管確認vlan、ip也添加了，但是就是ping不通網(wǎng)關：后來才知道對應的網(wǎng)關沒添加；
（3）有個小區(qū)始終不報link消息：后來發(fā)現(xiàn)是RRU側光纖未插；
（4）瑯岐便攜->將BBU下電6-8分鐘后，pinger能正常識別，但是SM識別不到該小區(qū)->重啟幾次后SM能識別，但是報RP3-2000:更換光模塊后問題解決。
36.FOSI 和FOSN的光功率范圍
（1）RTXM228-601 輸出光功率:-8.2dBm~+0.5dBm（FOSN）輸入光功率：-14.4dBm~+0.5dBm（2）RTXM228-618 輸出光功率:-5.2dBm~+0.5dBm（FOSI）輸入光功率：-14.4dBm~+0.5dBm 37.不同頻段RRU類型
室分只有一種頻段：
E頻段，2.3G(6通道FZNC 和2通道FZND)宏站有兩種頻段：
F頻段，1.9G(8通道FZFA和8通道FZFD)13 D頻段，2.6G(8通道FZHA)38.MAC綁定及載波沖突
更換BBU后傳輸需在網(wǎng)管做一個MAC地址的綁定
鐵路旅社：TD第三小區(qū)11個載波，所以LTE的第三小區(qū)只能到configing狀態(tài)，到不了configed的狀態(tài)，也ONair不了！
39.傳輸不通
1，網(wǎng)管IP沒配或配錯，按規(guī)劃重新做數(shù)據(jù)； 2，該站之前正常，但是后來上站發(fā)現(xiàn)vlan數(shù)據(jù)又被做到PTN2-5口，導致遠程ping不通，將PTN尾纖插到正確位置；
3，光電轉(zhuǎn)換器到BBU的網(wǎng)線有問題，直接更換； 4，PTN上的光模塊出問題，直接更換；
5，基站正常運行一段時間后TRS文件丟失，重做數(shù)據(jù)； 6，PTN被托管，聯(lián)系PTN側處理；
7，機房斷電、BBU或光電轉(zhuǎn)換器被下電、空開跳閘，上電或聯(lián)系移動處理；
40.升級完成后出現(xiàn)駐波告警
此故障出現(xiàn)在最新升級的版本247_16，升級完成后，由于Vendor文件未能同步更新名稱，導致出現(xiàn)駐波，這時候就需要通過Fileziler登陸到BBU里面，將Vendor文件的后面幾位改成升級以后版本的名稱，比如說升級前，Vendor名稱為vendor_GZ818630，這時候就需要該為vendor_GZ824716。
第三篇：LTE填空題總結
3.UE通過E-UTRAN廣播消息獲取AS和NAS系統(tǒng)消息。
4、隨機接入實現(xiàn)的基本功能：申請上行資源、與eNodeB間的上行時間同步。
5、RLC實體傳輸數(shù)據(jù)有三種模式：透明模式（TM）、無確認模式（UM）、確認模式（AM）。
6、LTE測量分為3類：同頻測量(Intra frequency measurement，不需要改變收發(fā)頻率）、異頻測量(Inter frequency measurement，需要改變收發(fā)頻率）、異技術測量(Inter-RAT measurement，需要改變收發(fā)頻率）
1、室內(nèi)覆蓋指標要求_90_%的區(qū)域達到_-105__dBm以上。
2、室內(nèi)單點測試中好點下行測試要求TM3達到_50__Mbps，TM1達到__35__Mbps。
3、室內(nèi)信號泄漏到室外指標要求為__建筑物外10m要求滿足室外室內(nèi)信號
比>10dB,或者室內(nèi)信號<-110dBm __。
4、室內(nèi)小區(qū)基本參數(shù)核查包括__PCI、頻點、BW、子幀配置、天線間距、CELL ID、eNB ID、TAC等____。
5、子幀配置1的上下行時隙配置為__DSUUD___。
1.CMCC測試規(guī)范規(guī)定，計算賦型增益時需要用到的數(shù)據(jù)有CRS RSRP和DRS RSRP
2.中移動TD-LTE試驗局要求默認采用上下行配置 1，特殊子幀配置 7
3.目前TD-LTE所用的頻段為 Band 38 和Band 40。
1.無線網(wǎng)絡規(guī)劃結束后應輸出文檔
2.OFDMA從頻域?qū)d波資源劃分成多個正交的載波，小區(qū)內(nèi)間無干擾，同頻組網(wǎng)時，不同小區(qū)使用相同時頻資源，存在小區(qū)間干擾。
3.影響小區(qū)吞吐量主要因素有，發(fā)射功率，其它
4.鏈路預算包括上下鏈路的發(fā)射機的各項和損耗，接收機的各項增益和損耗，以及各項增益和最大路徑損耗
5.PDSCH信道的TM3模式在信道質(zhì)量好的時候為，信道質(zhì)量差的時
候回落到單流波束賦型。
6.LTE組網(wǎng)中，如果采用室外D頻段組網(wǎng)，一般使用的時隙配比為，特
殊時隙配比為10:2:2；如果采用室外F頻段組網(wǎng)，一般使用的時隙配比為3:1:1，特殊時隙配比為3:9:2。
第四篇：算法總結
算法分析與設計總結報告
71110415 錢玉明
在計算機軟件專業(yè)中，算法分析與設計是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數(shù)據(jù)結構這個公式。算法的學習對于培養(yǎng)一個人的邏輯思維能力是有極大幫助的，它可以培養(yǎng)我們養(yǎng)成思考分析問題，解決問題的能力。作為IT行業(yè)學生，學習算法無疑會增強自己的競爭力，修煉自己的“內(nèi)功”。
下面我將談談我對這門課程的心得與體會。
一、數(shù)學是算法的基礎
經(jīng)過這門課的學習，我深刻的領悟到數(shù)學是一切算法分析與設計的基礎。這門課的很多時間多花在了數(shù)學公式定理的引入和證明上。雖然很枯燥，但是有必不可少。我們可以清晰的看到好多算法思路是從這些公式定理中得出來的，尤其是算法性能的分析更是與數(shù)學息息相關。其中有幾個定理令我印象深刻。
①主定理
本門課中它主要應用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一個大問題分解為a個子問題，其中子問題的規(guī)模為b。而f(n)可看作這些子問題的組合時的消耗。這些可以利用主定理的相關結論進行分析處理。當f(n)量級高于nlogba時，我們可以設法降低子問題組合時的消耗來提高性能。反之我們可以降低nlogba的消耗，即可以擴大問題的規(guī)?；蛘邷p小子問題的個數(shù)。因此主定理可以幫助我們清晰的分析出算法的性能以及如何進行有效的改進。
②隨機算法中的許多定理的運用
在這門課中，我學到了以前從未遇見過的隨機算法，它給予我很大的啟示。隨機算法不隨機，它可通過多次的嘗試來降低它的錯誤率以至于可以忽略不計。這些都不是空穴來風，它是建立在嚴格的定理的證明上。如素數(shù)判定定理是個很明顯的例子。它運用了包括費馬小定理在內(nèi)的各種定理。將這些定理進行有效的組合利用，才得出行之有效的素數(shù)判定的定理。尤其是對尋找證據(jù)數(shù)算法的改進的依據(jù)，也是建立在3個定理上。還有檢查字符串是否匹配也是運用了許多定理：指紋的運用，理論出錯率的計算，算法性能的評價也都是建立在數(shù)學定理的運用上。
這些算法都給予了我很大啟發(fā)，要想學好算法，學好數(shù)學是必不可少的。沒有深厚的數(shù)學功力作為地基，即使再漂亮的算法框架，代碼實現(xiàn)也只能是根底淺的墻上蘆葦。
二、算法的核心是思想
我們學習這門課不是僅僅掌握那幾個經(jīng)典算法例子，更重要的是為了學習蘊含在其中的思想方法。為什么呢？舉個例子。有同學曾問我這樣一個問題：1000只瓶子裝滿水，但有一瓶有毒，且毒發(fā)期為1個星期?，F(xiàn)在用10只老鼠在一個星期內(nèi)判斷那只瓶子有毒，每只老鼠可以喝多個瓶子的水，每個瓶子可以只喝一點。問如何解決？其實一開始我也一頭霧水，但是他提醒我跟計算機領域相關，我就立馬有了思路，運用二進制。因為計算機的最基本思想就是二進制。所以說，我們不僅要學習算法，更得學習思想方法。
①算法最基本的設計方法包括分治法，動態(tài)規(guī)劃法，貪心法，周游法，回溯法，分支定界法。我們可利用分治法做快速排序，降低找n個元素中最大元和最小元的量級，降低n位二進制x和y相乘的量級，做Strassen矩陣乘法等等。它的思想就是規(guī)模很大的問題分解為規(guī)模較小的獨立的子問題，關鍵是子問題要與原問題同類，可以采取平衡法來提高性能。
動態(tài)規(guī)劃法是把大問題分解為子問題，但是子問題是重復的，后面的問題可以利用前面解決過的問題的結果。如構造最優(yōu)二叉查找樹，解決矩陣連乘時最小計算次數(shù)問題，尋找最長公共子序列等等。
貪心法就是局部最優(yōu)法，先使局部最優(yōu)，再依次構造出更大的局部直至整體。如Kruscal最小生成樹算法，求哈夫曼編碼問題。
周游法就是簡單理解就是采取一定的策略遍歷圖中所有的點，典型的應用就是圖中的深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)。
回溯法就是就是在滿足一定的條件后就往前走，當走到某步時，發(fā)現(xiàn)不滿足條件就退回一步重新選擇新的路線。典型的應用就是8皇后問題，平面點集的凸包問題和0-1背包問題。
分支定界法：它是解決整數(shù)規(guī)劃問題一種最常用的方法。典型應用就是解決整數(shù)規(guī)劃問題。
②評價算法性能的方法如平攤分析中的聚集法，會計法和勢能法。聚集法就是把指令分為幾類，計算每一類的消耗，再全部疊加起來。會計法就是計算某個指令時提前將另一個指令的消耗也算進去，以后計算另一個指令時就不必再算了。勢能法計算每一步的勢的變化以及執(zhí)行這步指令的消耗，再將每一步消耗全部累計。
這幾種方法都是平攤分析法，平攤分析的實質(zhì)就是總體考慮指令的消耗時間，盡管某些指令的消耗時間很大也可以忽略不計。上述三種方法難易程度差不多，每種方法都有屬于它的難點。如聚集法中如何將指令有效分類，會計法中用什么指令提前計算什么指令的消耗，勢能法中如何選取勢能。因此掌握這些方法原理還不夠，還要學會去應用，在具體的問題中去判斷分析。
三、算法與應用緊密相關
我認為學習算法不能局限于書本上的理論運算，局限于如何提高性能以降低復雜度，我們要將它與實際生活聯(lián)系起來。其實算法問題的產(chǎn)生就來自于生活，設計出高效的算法就是為了更好的應用。如尋找最長公共子序列算法可以應用在生物信息學中通過檢測相似DNA片段的相似成分來檢測生物特性的相似性，也可以用來判斷兩個字符串的相近性，這可應用在數(shù)據(jù)挖掘中?？焖俑盗⑷~變換（FFT）可應用在計算多項式相乘上來降低復雜度，脫線min算法就是利用了Union-Find這種結構。還有圖中相關算法，它對于解決網(wǎng)絡流量分配問題起了很大的幫助，等等。
這些應用給了我很大的啟發(fā)：因為單純講一個Union-Find算法，即使了解了它的實現(xiàn)原理，遇到具體的實際問題也不知去如何應用。這就要求我們要將自己學到的算法要和實際問題結合起來，不能停留在思想方法階段，要學以致用，做到具體問題具體分析。
四、對計算模型和NP問題的理解
由于對這部分內(nèi)容不是很理解，所以就粗淺的談一下我的看法。
首先談到計算模型，就不得不提到圖靈計算，他將基本的計算抽象化，造出一個圖靈機，得出了計算的本質(zhì)。并提出圖靈機可以計算的問題都是可以計算的，否則就是不可計算的。由此引申出一個著名論題：任何合理的計算模型都是相互等價的。它說明了可計算性本身不依賴于任何具體的模型而客觀存在。
NP問題比較復雜，我認為它是制約算法發(fā)展的瓶頸，但這也是算法分析的魅力所在。NP問題一般可分為3類，NP-C問題，NP-hard問題以及頑型問題。NP-C它有個特殊的性質(zhì)，如果存在一個NP-C問題找到一個多項式時間的解法，則所有的NP-C問題都能找到多項式時間解法。如哈密頓回路問題。NP-hard主要是解決最優(yōu)化問題。它不一定是NP問題。這些問題在規(guī)模較小時可以找出精確解，但是規(guī)模大時，就因時間太復雜而找不到最優(yōu)解。此時一般會采用近似算法的解法。頑型問題就是已經(jīng)證明不可能有多項式時間的算法，如漢諾塔問題。
最后談談對這門課程的建議
①對于這門算法課，我認為應該加強對算法思想方法的學習。所以我建議老師可不可以先拋出問題而不給出答案，講完一章，再發(fā)課件。讓我們先思考一會兒，或者給出個獎勵機制，誰能解決這個問題，平時成績加分。這在一定程度上會將強我們思考分析問題的能力。因為我感覺到，一個問題出來，未經(jīng)過思考就已經(jīng)知曉它的答案，就沒什么意思，得不到提高，而且也不能加深對問題的思考和理解。下次遇到類似的問題也就沒有什么印象。而且上課讓我們思考，點名回答問題可以一定程度上有效的防止不認真聽課的現(xiàn)象。
②作業(yè)安排的不是很恰當。本門課主要安排了三次作業(yè)，個人感覺只有第一次作業(yè)比較有意思。后面兩次作業(yè)只是實現(xiàn)一下偽代碼，沒有太多的技術含量。而且對于培養(yǎng)我們的解決問題的能力也沒有太多的幫助，因為這間接成為了程序設計題，不是算法設計題。
③本門課的時間安排的不太恰當，因為本學期的課程太多，壓力太大。沒有太多的時間去學習這門課程。因為我相信大家都對它感興趣，比較重視，想花功夫，但苦于沒時間。所以可不可以將課程提前一個學期，那時候離散數(shù)學也已經(jīng)學過，且課程的壓力也不是很大。錯開時間的話，我覺得應該能夠更好提高大家算法分析設計的能力。
第五篇：算法總結
算法分塊總結
為備戰(zhàn)2005年11月4日成都一戰(zhàn)，特將已經(jīng)做過的題目按算法分塊做一個全面詳細的總結，主要突出算法思路，盡量選取有代表性的題目，盡量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法設計中，時刻都要牢記要減少冗余，要以簡潔高效為追求目標。另外當遇到陌生的問題時，要想方設法進行模型簡化，轉(zhuǎn)化，轉(zhuǎn)化成我們熟悉的東西。
圖論模型的應用
分層圖思想的應用：
用此思想可以建立起更簡潔、嚴謹?shù)臄?shù)學模型，進而很容易得到有效算法。重要的是，新建立的圖有一些很好的性質(zhì)： 由于層是由復制得到的，所以所有層都非常相似，以至于我們只要在邏輯上分出層的概念即可，根本不用在程序中進行新層的存儲，甚至幾乎不需要花時間去處理。由于層之間的相似性，很多計算結果都是相同的。所以我們只需對這些計算進行一次，把結果存起來，而不需要反復計算。如此看來，雖然看起來圖變大了，但實際上問題的規(guī)模并沒有變大。層之間是拓撲有序的。這也就意味著在層之間可以很容易實現(xiàn)遞推等處理，為發(fā)現(xiàn)有效算法打下了良好的基礎。
這些特點說明這個分層圖思想還是很有潛力的，尤其是各層有很多公共計算結果這一點，有可能大大消除冗余計算，進而降低算法時間復雜度。二分圖最大及完備匹配的應用： ZOJ place the robots: 二分圖最優(yōu)匹配的應用：
最大網(wǎng)絡流算法的應用：典型應用就求圖的最小割。最小費用最大流的應用：
容量有上下界的最大流的應用：
歐拉路以及歐拉回路的應用：主要利用求歐拉路的套圈算法。最小生成樹：
求最小生成樹，比較常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使復雜度降為O(Vlog2V+E)，后者一般應用于稀疏圖，其時間復雜度為O(Elog2V)。最小K度限制生成樹：
抽象成數(shù)學模型就是：
設G=(V,E,ω)是連通的無向圖，v0 ∈V是特別指定的一個頂點,k為給定的一個正整數(shù)。首先考慮邊界情況。先求出問題有解時k 的最小值：把v0點從圖中刪去后，圖中可能會出 現(xiàn)m 個連通分量，而這m 個連通分量必須通過v0來連接，所以，在圖G 的所有生成樹中 dT(v0)≥m。也就是說，當k 首先，將 v0和與之關聯(lián)的邊分別從圖中刪去，此時的圖可能不再連通，對各個連通分量，分別求最小生成樹。接著，對于每個連通分量V’，求一點v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，則該連通分量通過邊(v1,v0)與v0相連。于是，我們就得到了一個m度限制生成樹，不難證明，這就是最小m度限制生成樹。這一步的時間復雜度為O(Vlog2V+E)我們所求的樹是無根樹，為了解題的簡便，把該樹轉(zhuǎn)化成以v0為根的有根樹。 假設已經(jīng)得到了最小p度限制生成樹，如何求最小p+1 度限制生成樹呢？在原先的樹中加入一條與v0相關聯(lián)的邊后，必定形成一個環(huán)。若想得到一棵p+1 度限制生成樹，需刪去一條在環(huán)上的且與v0無關聯(lián)的邊。刪去的邊的權值越大，則所得到的生成樹的權值和就越小。動態(tài)規(guī)劃就有了用武之地。設Best(v)為路徑v0—v上與v0無關聯(lián)且權值最大的邊。定義father(v)為v的父結點，動態(tài)轉(zhuǎn)移方程：Best(v)=max(Best(father(v)),(father(v),v))，邊界條件為Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。 狀態(tài)共|V|個，狀態(tài)轉(zhuǎn)移的時間復雜度O(1)，所以總的時間復雜度為O(V)。故由最小p度限制生成樹得到最小p+1度限制生成樹的時間復雜度為O(V)。1 先求出最小m度限制生成樹； 2由最小m度限制生成樹得到最小m+1度限制生成樹;3 當dT(v0)=k時停止。 加邊和去邊過程，利用動態(tài)規(guī)劃優(yōu)化特別值得注意。 次小生成樹： 加邊和去邊很值得注意。 每加入一條不在樹上的邊，總能形成一個環(huán)，只有刪去環(huán)上的一條邊，才能保證交換后仍然是生成樹，而刪去邊的權值越大，新得到的生成樹的權值和越小。具體做法： 首先做一步預處理，求出樹上每兩個結點之間的路徑上的權值最大的邊，然后，枚舉圖中不在樹上的邊，有了剛才的預處理，我們就可以用O(1)的時間得到形成的環(huán)上的權值最大的邊。如何預處理呢？因為這是一棵樹，所以并不需要什么高深的算法，只要簡單的BFS 即可。 最短路徑的應用： Dijkstra 算法應用： Folyed 算法應用： Bellman-Ford 算法的應用： 差分約束系統(tǒng)的應用： 搜索算法 搜索對象和搜索順序的選取最為重要。一些麻煩題，要注意利用數(shù)據(jù)有序化，要找一個較優(yōu)的搜索出發(fā)點，凡是能用高效算法的地方盡量爭取用高效算法?；镜倪f歸回溯深搜，記憶化搜索，注意剪枝： 廣搜（BFS）的應用： 枚舉思想的應用： ZOJ 1252 island of logic A*算法的應用： IDA*算法的應用，以及跳躍式搜索探索： 限深搜索，限次： 迭代加深搜索： 部分搜索+高效算法（比如二分匹配，動態(tài)規(guī)劃）： ZOJ milk bottle data: 剪枝優(yōu)化探索： 可行性剪枝，最優(yōu)性剪枝，調(diào)整搜索順序是常用的優(yōu)化手段。 動態(tài)規(guī)劃 動態(tài)規(guī)劃最重要的就是狀態(tài)的選取，以及狀態(tài)轉(zhuǎn)移方程，另外還要考慮高效的預處理（以便更好更快的實現(xiàn)狀態(tài)轉(zhuǎn)移）。最常用的思想就是用枚舉最后一次操作。 狀態(tài)壓縮DP，又叫帶集合的動態(tài)規(guī)劃：題目特點是有一維的維數(shù)特別小。類似TSP問題的DP： 狀態(tài)劃分比較困難的題目： 樹形DP： 四邊形不等式的應用探索：四邊形不等式通常應用是把O(n^3)復雜度O(n^2) 高檔數(shù)據(jù)結構的應用 并查集的應用： 巧用并查集中的路徑壓縮思想： 堆的利用： 線段樹的應用： 總結用線段樹解題的方法 根據(jù)題目要求將一個區(qū)間建成線段樹，一般的題目都需要對坐標離散。建樹時，不要拘泥于線段樹這個名字而只將線段建樹，只要是表示區(qū)間，而且區(qū)間是由單位元素(可以是一個點、線段、或數(shù)組中一個值)組成的，都可以建線段樹；不要拘泥于一維，根據(jù)題目要求可以建立面積樹、體積樹等等 樹的每個節(jié)點根據(jù)題目所需，設置變量記錄要求的值 用樹形結構來維護這些變量：如果是求總數(shù)，則是左右兒子總數(shù)之和加上本節(jié)點的總數(shù)，如果要求最值，則是左右兒子的最大值再聯(lián)系本區(qū)間。利用每次插入、刪除時，都只對O(logL)個節(jié)點修改這個特點，在O(logL)的時間內(nèi)維護修改后相關節(jié)點的變量。 在非規(guī)則刪除操作和大規(guī)模修改數(shù)據(jù)操作中，要靈活的運用子樹的收縮與葉子節(jié)點的釋放，避免重復操作。 Trie的應用：； Trie圖的應用探索： 后綴數(shù)組的應用研究： 在字符串處理當中，后綴樹和后綴數(shù)組都是非常有力的工具，其中后綴樹了解得比較多，關于后綴數(shù)組則很少見于國內(nèi)的資料。其實后綴數(shù)組是后綴樹的一個非常精巧的替代品，它比后綴樹容易編程實現(xiàn)，能夠?qū)崿F(xiàn)后綴樹的很多功能而時間復雜度也不太遜色，并且，它比后綴樹所占用的空間小很多。 樹狀數(shù)組的應用探索：； 計算幾何 掌握基本算法的實現(xiàn)。凸包的應用：； 半平面交算法的應用：； 幾何+模擬類題目：幾何設計好算法，模擬控制好精度。掃描法：； 轉(zhuǎn)化法：ZOJ 1606 將求所圍的格子數(shù)，巧妙的轉(zhuǎn)化為求多邊形的面積。離散法思想的應用：； 經(jīng)典算法：找平面上的最近點對。 貪心 矩形切割 二分思想應用 活用經(jīng)典算法 利用歸并排序算法思想求數(shù)列的逆序?qū)?shù)： 利用快速排序算法思想，查詢N個數(shù)中的第K小數(shù)： 博弈問題 博弈類題目通常用三類解法：第一類推結論； 第二類遞推，找N位置，P位置； 第三類SG函數(shù)的應用。第四類極大極小法，甚至配合上αβ剪枝。最難掌握的就是第四類極大極小法。 第一類：推結論。典型題目： 第二類：遞推。典型題目： 比如有向無環(huán)圖類型的博弈。在一個有向圖中，我們把選手I有必勝策略的初始位置稱為N位置(Next player winning)，其余的位置被稱為P位置(Previous player winning)。很顯然，P位置和N位置應該具有如下性質(zhì)： 1． 所有的結束位置都是P位置。 2． 對于每一個N位置，至少存在一種移動可以將棋子移動到一個P位置。3． 對于每一個P位置，它的每一種移動都會將棋子移到一個N位置。 這樣，獲勝的策略就是每次都把棋子移動到一個P位置，因為在一個P位置，你的對手只能將棋子移動到一個N位置，然后你總有一種方法再把棋子移動到一個P位置。一直這樣移動，最后你一定會將棋子移動到一個結束位置（結束位置是P位置），這時你的對手將無法在移動棋子，你便贏得了勝利。 與此同時，得到了這些性質(zhì)，我們便很容易通過倒退的方法求出哪些位置是P位置，哪些位置是N位置，具體的算法為： 1． 將所有的結束位置標為P位置。 2． 將所有能一步到達P位置的點標為N位置。 3． 找出所有只能到達N位置的點，將它們標為P位置。 4． 如果在第三步中沒有找到新的被標為P位置的點，則算法結束，否則轉(zhuǎn)到步驟2。這樣我們便確定了所有位置，對于題目給出的任一初始位置，我們都能夠很快確定出是選手I獲勝還是選手II獲勝了。第三類：SG函數(shù)的應用。 關于SG函數(shù)的基本知識：對于一個有向圖(X, F)來說，SG函數(shù)g是一個在X上的函數(shù)，并且它返回一個非負整數(shù)值，具體定義為 g(x)?min{n?0,n?g(y)對于所有y?F(x)} 1． 對于所有的結束位置x，g(x)= 0。 2． 對于每一個g(x)≠ 0的位置x，在它可以一步到達的位置中至少存在一個位置y使得g(y)= 0。 3．對于每一個g(x)＝ 0的位置x，所有可以由它一步到達的位置y都有g(y)≠ 0。 定理 如果g(xi)是第i個有向圖的SG函數(shù)值，i = 1,…,n，那么在由這n個有向圖組成的狀態(tài)的SG函數(shù)值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn) 第四類：極大極小法。 典型題目：ZOJ 1155：Triangle War ZOJ 1993：A Number Game 矩陣妙用 矩陣最基本的妙用就是利用快速乘法O（logn）來求解遞推關系（最基本的就是求Fibonacci數(shù)列的某項）和各種圖形變換，以及利用高斯消元法變成階梯矩陣。典型題目： 數(shù)學模型舉例 向量思想的應用： UVA 10089：注意降維和向量的規(guī)范化 ； 利用復數(shù)思想進行向量旋轉(zhuǎn)。 UVA 10253： 遞推 數(shù)代集合 數(shù)代集合的思想： ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一題：Intuitionistic Logic 用枚舉+數(shù)代集合思想優(yōu)化，注意到題中有一句話：“You may assume that the number H = |H| of elements of H?doesn't exceed 100”，這句話告訴我們H的元素個數(shù)不會超過100，因此可以考慮用一個數(shù)代替一個集合，首先把所有的運算結果都用預處理算出來，到計算的時候只要用O(1)的復雜度就可以完成一次運算。 組合數(shù)學 Polya定理則是解決同構染色計數(shù)問題的有力工具。 補集轉(zhuǎn)化思想 ZOJ 單色三角形： 字符串相關 擴展的KMP算法應用：；最長回文串； 最長公共子串； 最長公共前綴； 填充問題 高精度運算 三維空間問題專題 無論什么問題，一旦擴展到三難空間，就變得很有難度了。三維空間的問題，很考代碼實現(xiàn)能力。 其它問題的心得 解決一些判斷同構問題的方法：同構的關鍵在于一一對應，而如果枚舉一一對應的關系，時間復雜度相當?shù)母?，利用最小表示，就能把一個事物的本質(zhì)表示出來。求最小表示時，我們一定要仔細分析，將一切能區(qū)分兩個元素的條件都在最小表示中體現(xiàn)，而且又不能主觀的加上其他條件。得到最小表示后，我們往往還要尋求適當?shù)?、高效的匹配算法（例如KMP字符匹配之類的），來比較最小表示是否相同，這里常常要將我們熟悉的高效算法進行推廣
點擊咨詢 