1、計算復雜性計算復雜性 算法性能：算法性能： （1）在最壞情況下算法所表現出來的性能；）在最壞情況下算法所表現出來的性能；-最壞性能最壞性能 （2）在各種情況可能出現時，算法所表現）在各種情況可能出現時，算法所表現出來的期望性能。出來的期望性能。-平均性能平均性能 一個商人欲到一個商人欲到n個城市推銷商品，每兩個城市個城市推銷商品，每兩個城市i和和j之間的距離為之間的距離為dij，如何選擇一條道路，使得商人每個城市走過一遍后回到起點且所如何選擇一條道路，使得商人每個城市走過一遍后回到起點且所走路徑最短。走路徑最短。 解：設解：設xij=1若商人行走的路線中包含從城市若商人行走的路線中包含從城市i

2、到到j的路徑，否則的路徑，否則xij =0。01, 11|2, 1|, 2 , 1, 1, 2 , 1, 1. .min,11orxnSnSSxnjxnixtsxdijSjiijniijnjijjiijij 可行解：用可行解：用n個城市的一個排列表示商人按個城市的一個排列表示商人按這個排列序推銷并返回起點。這個排列序推銷并返回起點。 使用枚舉法求解，需要使用枚舉法求解，需要(n-1)!次枚舉。次枚舉。 以計算機以計算機1秒可以完成秒可以完成24個城市所有路徑枚個城市所有路徑枚舉為單位。舉為單位。 城市數城市數 24 25 26 27 30 計算時間計算時間 1秒秒 24秒秒 10分分 4.3小

3、時小時 10.8年年 1. 問題與實例問題與實例 問題問題(problem):需要回答的一種提問，通需要回答的一種提問，通常包含一些參數和取值未定的自由變量，可常包含一些參數和取值未定的自由變量，可以從兩個方面加以描述：以從兩個方面加以描述： （1）對所有參數的一般描述；）對所有參數的一般描述； （2）對回答（也稱為）對回答（也稱為解解）所需要滿足的特）所需要滿足的特性的描述。性的描述。 實例實例(instance)：當對一個問題中的參數：當對一個問題中的參數賦予特定的數值時，如何尋找相應的回答賦予特定的數值時，如何尋找相應的回答（解），這種提問稱為該問題的一個實例。（解），這種提問稱為該問題

4、的一個實例。 問題是對許多具體事例構成集合的一種抽象問題是對許多具體事例構成集合的一種抽象表述，而實例就是相應問題的一種具體表現表述，而實例就是相應問題的一種具體表現形式。形式。 例：線性規劃問題與實例例：線性規劃問題與實例 一個線性規劃問題的實例是指矩陣和向量一個線性規劃問題的實例是指矩陣和向量組組(A, b, c)的某一特定取值，這些參數按照的某一特定取值，這些參數按照如下的結構關聯在一起，描述了問題（解）如下的結構關聯在一起，描述了問題（解）所需要滿足的特性。所需要滿足的特性。min. .0cxstAxbx 線性規劃問題是對具有上述結構的所有實例線性規劃問題是對具有上述結構的所有實例的一

5、種抽象描述。的一種抽象描述。 算法算法：是一組含義明確的簡單指令。：是一組含義明確的簡單指令。 一個問題是算法可解的一個問題是算法可解的(solvable)：存在一個：存在一個求解該問題的算法，只要讓算法運行足夠長的時求解該問題的算法，只要讓算法運行足夠長的時間，并且保證滿足算法在運行過程中所需要的存間，并且保證滿足算法在運行過程中所需要的存儲空間，它就能求解該問題的任何一個實例。儲空間，它就能求解該問題的任何一個實例。 停機問題停機問題：不可能構造出一個程序來確定任意給：不可能構造出一個程序來確定任意給出的程序是否會陷入無限循環。出的程序是否會陷入無限循環。 算法復雜性算法復雜性(algor

6、ithm complexity):描述算法的存儲要求和運行時間要求，分描述算法的存儲要求和運行時間要求，分為算法的空間復雜性和算法的時間復雜性。為算法的空間復雜性和算法的時間復雜性。 -利用算法需要的初等運算次數來表示利用算法需要的初等運算次數來表示算法的時間復雜性。算法的時間復雜性。 輸入規模輸入規模(input size)：表示一個：表示一個實例實例所所需要的字符串長度。需要的字符串長度。 一般的，使用一般的，使用 位二進制就可以位二進制就可以表示任意整數表示任意整數r。 線性規劃的輸入規模為：線性規劃的輸入規模為：21log r 22212211121log1log1log |1log

7、|1log |2log |(, ,)njjmnmijjijiLmncabmnmnPPA b c為中所有非零數的乘積 對應對應TSP，枚舉算法的基本計算總次數為，枚舉算法的基本計算總次數為(n-1)!n=n! 實例的二進制輸入長度總量不超過實例的二進制輸入長度總量不超過 L=n(n-1)+log2|P| 其中其中P為所有非零數為所有非零數dij的乘積。的乘積。 假設假設 中每個數據都有上中每個數據都有上界界K，則有，則有|1,ijSdi j nij2(1) 1 logLn nK 一個求解實例一個求解實例I的算法的基本計算總次數的算法的基本計算總次數C(I)同實例同實例I的計算機二進制輸入長度的計

8、算機二進制輸入長度d(I)的關系的關系常用符號常用符號C(I)=f(d(I)=O(g(d(I)表示，它的表示，它的含義：求解實例含義：求解實例I的算法的基本計算總次數的算法的基本計算總次數C(I)是實例是實例輸入長度輸入長度d(I)的一個函數，該函的一個函數，該函數被另一個函數數被另一個函數g(x)控制，即存在一個函數控制，即存在一個函數g(x)和一個常數和一個常數a，使得，使得 ( ( )C Iag d I 定義：假設問題和解決該問題的一個算法已經定義：假設問題和解決該問題的一個算法已經給定，若給定該問題的一個實例給定，若給定該問題的一個實例I，存在多項式，存在多項式函數函數g(x)，使得，

9、使得 成立，則稱該算法對成立，則稱該算法對實例實例I是多項式時間算法；是多項式時間算法；若若存在存在g(x)為為多項式函數且對該問題任意一個實多項式函數且對該問題任意一個實例例I ，都有上式成立，則稱，都有上式成立，則稱該算法為解決該問該算法為解決該問題的題的多項式時間算法多項式時間算法。 當當g(x)為為指數函數時，稱相應的算法為指數函數時，稱相應的算法為指數時間指數時間算法算法。 ( ( )C Iag d I10nn22nn! =2O(n lg n)input lengthtime 多項式時間算法的優點：多項式時間算法的優點： （1）隨著問題輸入規模的增加，算法的計）隨著問題輸入規模的增加

10、，算法的計算量（即算法復雜性）呈多項式增長；算量（即算法復雜性）呈多項式增長； （2）一個多項式時間算法利用另一個多項）一個多項式時間算法利用另一個多項式時間算法作為其式時間算法作為其“子程序子程序”，構造一個，構造一個新的復合型算法，則新算法仍是多項式時新的復合型算法，則新算法仍是多項式時間算法。間算法。0122max10. .21010,2,0,1,2,nn iiiijiijj iixxstxxinxin單純形算法需要單純形算法需要2n-1次迭代。次迭代。22( )623log |,d InnnPP二進制輸入大小其中 為所有非零系數的乘積。011max. .2,2,0,1,2,niiiij

11、j iiwwstwwinwin定理：當定理：當2時，用單純形算法求解上述問題時需要時，用單純形算法求解上述問題時需要2n-1次迭代。次迭代。 110(1,1),ninnwinw最優解為：最優值。 橢球法橢球法 第一個可以在多項式時間內解決一般線性規劃問第一個可以在多項式時間內解決一般線性規劃問題的解法。題的解法。min( ). .0cxPstAxbxmax(). .0TTb wDstA wcw根據根據(P) 與與(D) 的對偶關系的對偶關系, 我們可將兩者的最優解以我們可將兩者的最優解以一組最優性條件聯結起來一組最優性條件聯結起來:,0,0(*)0TAxbxA wcwcxwbLPAxb定理：存

12、在求解問題的多項式時間算法的充要條件是存在求解線性不等式組的多項式時間算法。 min*. .0,0,0AxbLPcxstAxbxxxAAAbb xxccx 證明：與線性不等式組相關的問題為其中任取 如 *LPAxbAxbAxb若有多項式時間的算法，能夠判斷問題不可行，則不等式組無解；或者得到其最優解或判定問題無界，則得到不等式組的一個解，顯然就以多項式時間解決了問題。LPAxb定理：存在求解問題的多項式時間算法的充要條件是存在求解線性不等式組的多項式時間算法。 max*. .0,0, ,0wbstwAcwLPx wAxb wAc cxwbx w的對偶問題為所以求解問題可歸結為求解關于變量的線性

13、不等式組：*,*,0 xwxLPwAxb xLPLP設有多項式時間方法求解線性不等式組。若該聯立不等式組有解，則是問題的最優解，是其對偶問題的最優解；若該聯立不等式組無解，考慮不等式組若它有解，則問題無界；否則問題不可行。 只要能有效的解決最優性條件的線性不等式只要能有效的解決最優性條件的線性不等式, 就能夠同時的解決一個線性規劃問題就能夠同時的解決一個線性規劃問題(P) 以及它的以及它的對偶問題對偶問題(D)。橢球法正是一種專門解決線性不等。橢球法正是一種專門解決線性不等式的方法。式的方法。介紹如何以橢球法來解一組線性不等式介紹如何以橢球法來解一組線性不等式MuvMuv的解集合是一個凸集：的

14、解集合是一個凸集： |Su Muv 假設假設S, 以原點以原點u1為圓心為圓心, 足夠大的半徑做一足夠大的半徑做一圓圓E1, 使得使得SE1 。11Muvu若，則為所求的解。 否則否則, 因為因為SE1是一個凸集是一個凸集, 所以經過圓心所以經過圓心,可可以切掉不含以切掉不含SE1 的半個圓的半個圓, 而只剩下包含而只剩下包含SE1的半個圓的半個圓(以以1/2E1表示表示)。對。對1/2E1而言而言,可以做出可以做出一個最小的橢圓一個最小的橢圓E2, 使得使得1/2E1 E2，橢圓的圓心，橢圓的圓心記記u2。SE1E2, 若若Mu2 v成立成立, 則則u2SE1必為其必為其解。否則經過解。否則

15、經過u2又可切去半個又可切去半個E2, 而使而使SE1包包含在另一半橢圓含在另一半橢圓1/2E2之中。之中。 在在p維空間中維空間中, 每次做出的橢球體積都會逐漸縮每次做出的橢球體積都會逐漸縮小。以小。以V(Ek)及及V(Ek+1)來來表示前后兩個橢球的體積表示前后兩個橢球的體積, 那么可以證明那么可以證明V(Ek+1) e1/2 (p+1)V(Ek)。所以。所以 V(Ek+1) 0。可行內點解集合可行內點解集合：F0 = xRn|Ax =b, x 0。假設假設F0非空。非空。內點法可粗略的分為三個步驟內點法可粗略的分為三個步驟:步驟一步驟一: 找一個可行內點找一個可行內點x1F0。置。置k=

16、1。步驟二步驟二: 決定現有解決定現有解xk是否為是否為(P) 的最優解。若是的最優解。若是, 則輸出則輸出x = xk。否則就尋找一個好的移動方向。否則就尋找一個好的移動方向 , 以及適當的步長以及適當的步長 0。kxdk10.:1kkkkkxxxxdFkk步驟三：由移動到新的內點置，返回步驟二。Primal Affine Scaling內點法內點法 假想假想(P) 的可行解集合位于第一象限的一個球的可行解集合位于第一象限的一個球, 而而現行解現行解xk落在球心上落在球心上, 此球的半徑是此球的半徑是r 0。2121min(). .Tnkjjjc xPstxxr1*kkcxxxrc最優解為：

17、最優解為： 將將(P1) 變得稍微復雜一些變得稍微復雜一些, 將球改為第一象將球改為第一象限來考慮下列問題限來考慮下列問題:2min(). .0Tc xPstx1112201100010kkkkkkkknknxn nxxxxDDxx假設，定義矩陣111:( ):( )nnkkknnkkkTRRxyT xD xTRRyxTyD y則定義映射：定義映射：11()( )kkkkkkkkyT xD xeTeD ex 在上述轉化之下在上述轉化之下, (P2) 的近似問題在的近似問題在y空間中就可空間中就可寫成寫成:221min(). .11Tknjjc D yPsty應用應用(P1) 的解答技巧的解答技

18、巧, 在在y空間中的近似最優解為：空間中的近似最優解為：1*kkkkkkD cD cyyyeD cD c 在在x空間中空間中(P2)的近似最優解為：的近似最優解為：2211*kkkkkkkkkD cD cxxD yD exD cD cmin( ). .0Tc xPs tAxbx在在y空間中空間中(P) 變成下列的近似問題變成下列的近似問題:21min(). .11Tkknjjc D yPstAD yby 與與(P2) 相比較相比較, (P) 多了一些等式約束條件多了一些等式約束條件ADky = b。為了保持這些等式的繼續成立。為了保持這些等式的繼續成立, 原來原來在在(P2) 中的移動方向中的

19、移動方向Dkc便需要投影在便需要投影在(ADk)這這個矩陣個矩陣的零空間的零空間(null space) 之中，即經過投影之中，即經過投影后的方向應是后的方向應是Pk(Dkc)，其中其中Pk是一個投影矩陣，是一個投影矩陣，定義為：定義為：12TTkkkkPID AAD AAD所以所以(P) 的近似最優解是的近似最優解是1*kkkkkPD cyyePD c(P) 的近似最優解是的近似最優解是11*kkkkkkkkkD P D cxxD yxP D c11,1,2,0( )kkjj jnxxP定理：若存在使得，則是的最優解。Primal Affine Scaling內點法的重要步驟內點法的重要步驟

20、:101.: 1.xFk找一個可行內點，置112.kxkkkkkkkkkkxdD P D cP D cxxd 計算移動方向，步長，新內點113.01,2,*:12.kjkxjnxxkk檢驗是否有，若成立，則輸出；否則置，返回 兩個基本事實：兩個基本事實： （1）如果一個內點居于多面體的中心，那）如果一個內點居于多面體的中心，那么目標函數的負梯度方向是比較好的可行么目標函數的負梯度方向是比較好的可行方向；方向； （2）在不改變問題基本特性的條件下，存）在不改變問題基本特性的條件下，存在一個適當的變換，能夠將可行域中給定在一個適當的變換，能夠將可行域中給定的內點置于變換后的可行域的中心。的內點置于

21、變換后的可行域的中心。 基本思想：基本思想： （1）選定一個內點解作為迭代過程的初始點，利）選定一個內點解作為迭代過程的初始點，利用可行域的投影尺度變換，將當前的內點解置于用可行域的投影尺度變換，將當前的內點解置于變換后的可行域的中心；變換后的可行域的中心； （2）在變換后的可行域中沿著目標函數最速下降）在變換后的可行域中沿著目標函數最速下降方向的正交投影移動，獲得新的可行內點，并通方向的正交投影移動，獲得新的可行內點，并通過投影尺度逆變換將新的可行內點映射到原來的過投影尺度逆變換將新的可行內點映射到原來的可行域，作為新的迭代點。可行域，作為新的迭代點。 （3）重復這一過程，直至求出滿足一定精

22、度的近）重復這一過程，直至求出滿足一定精度的近優解。優解。X空間空間Y空間空間投影尺度變換Karmarkar標準形標準形12min. .0(*)10,.Tnnc xstAxxxxxAm nc xR其中 是滿秩矩陣，基本假設：基本假設：1(0)(0)(1)|1,01(1,1) .(2)0(3)2 .njjTTTqTSxxxaeenxc xqxc xc a問題(*)是可行的，單純形的中心是可行點，其中對每個可行點 ，有。終止參數 給定，目的是求一個可行點 ，使得單純形單純形(0)|1,01(0,0,1,0,0) ,1, .1.TTjSx e xxnejnSaen定義集合為維單純形，其頂點是的中心是

23、22221111(1) 0.11110(1).1(1)/-1SnRnnnnSrnnnnn nR rn單純形 的外接球半徑單純形 的內接球半徑外接球與內接球半徑之比.向量的投影向量的投影,( ).: |0,.m nBBBBnBBBr BmmVVVVx BxRVV它的 個行向量生成的子空間為。的正交子空間，則則12121211112,( ),.nTBBTTTTTTTyRyyyyVyVyByByBByBBr BmBBByyBBBByyIBBBB y ,其中則兩邊左乘得正交投影正交投影矩陣矩陣單純形單純形S的投影尺度變換的投影尺度變換111( ),(,),0,1, .( ),1, .Tniiiijjj

24、D xT xe D xDdiag aaainT xyx ayinxa定義其中記則11niiy變換變換T的性質的性質11.( )(*).(0,0,1,0,0)iiiTjjjTjTSa yDyxTyxe Dya ySe是單純形 上的一一對應，其逆變換為的每個頂點的像還是這個頂點。2.00.AxADy約束在變換(*)下等價于113.(,)TnaaaSen點的像是單純形 的中心。4.00jjTxSy把由給出的 的每個面映射成對應的面。(0)5. |0 |0.ax AxSay ADy若，則 的中心勢函數勢函數1( )( )( )ln()njjl xl xf xkkx對每個線性函數，定義與勢函它相聯系的為

25、：其數中 為常數性質：性質：射影變換射影變換T把勢函數變換成具有相同形式的函數把勢函數變換成具有相同形式的函數目標函數值所期望的下降量可通過勢函數值的充目標函數值所期望的下降量可通過勢函數值的充分小來達到分小來達到優化函數優化函數f(x)可用優化線性函數來近似可用優化線性函數來近似1111111( )/()( )lnln/()lnlnln( )lnln.TiiiiiTTjjjTTTnnTjjjjjTTnnnjjjjjjjTnnjjjjl xc xDya ya yxxe Dya ye Dyc xc Dye Dyf xxa ye Dyc Dyc yaa yyc yf yaycDc 令即變換后的勢函

26、數為：其中12min. .0(*)10,.Tnnc xstAxxxxxAm nc xR其中 是滿秩矩陣，求解方法求解方法1min(*). . |0,|1,0Tnjjc xstxSx AxSxxx 其中1(0)1(0)( ) |0,1(,)0TTnDyx Tyy ADye DySSSSaaaSaenaS 運用變換 =把 變為變為 ，即把可行域變為，同時把單純形上的可行點變成單純形 的中心，則。111( )lnlnn( )lTTTTTnnnjjjjjjc Dyc xe Dyc xc yf xafxyyminmin( ). . .Tc xf ys txSs tyS(0)(0)(0)(0)(0)11(

27、,)(0,1)(1)(,)(,)(,)011nTjjSarB arSrn nB arB arxB arADxxe x 用包含在 內、以為球心，為半徑的球取代 ，其中，。記則對，有且，即。101mTADBee 令1mBxe 1|mxBxe 令(0)min( )min( ). . .(,)f xf xs txSs txB ar(0)(0)minmin( ). .(,). .(,)Tc xf xs txB ars txB arcDc 其中。01TADxe x 1TTpcIBBBB Dc記(0(0)(0)(,)TppTppc xcdcc xBrbaccar 在上下降最快的方向是在上的最小點是Karma

28、rkar投影尺度算法投影尺度算法(0)11.0,1 (1) ;(0,1).kxe rnnLn置參數， 是充分大的正整數( )(0)( )2.23TkLTkc xc xx若，則停止計算，得到近優解；否則轉 。( )( )( )1( )( )11(1)( )13.,1,kkkkTkTTkykkkkkkkykkTkkkyAXXdiag xBedIBB BBXcdXyyerxne Xyd 令.( )(1)( )(1)( )(1)4.005kkkkkkf xf xf xf xKarmarkarf xf x計算勢函數值和，若，則停止計算，得出標準問題的極小值大于 的結論，這種情形對應原來的線性規劃問題不可

29、行或無下界；若，則轉 。5.:12kk置，返回 。有關定理有關定理(0)1.( (log )2TqTO n qnxc xc a定理 算法在步內求得一個可行點 ，使得。(1)( )222.(1)(2)0.2(1)1/(1)kkkf xf xnnn n定理對每個 ，有下列兩種情形之一：；目標函數的極小值大于 。其中 (0)(0)3.,bB arfbfa定理存在點，使得。 (0)(0)4.,Tbc xB arfbfa定理設 是在上的極小點，則。(0)5.,Tbc xB ar定理算法求得的點 是在上的極小點.1利用對偶定理轉化線性規劃問題利用對偶定理轉化線性規劃問題0. .min)(xbAxtsxcP

30、T0. .max)(ucuAtsubDTT(P)存在最優解的充要條件是存在最優解的充要條件是000uxubxccuAbAxTTT0, 0, 0, 00vyuxubxccvuAbyAxTTT0000,000TTTxAIbuAAIbcxycbv 記記于是問題歸結為求解：于是問題歸結為求解：0,xbxA一個線性規劃問題：為，上述問題又可重新化引入人工變量0, 0)(. .minxbbeAxAts10,cxzbeAAB記記0, 0)(. .minxbbeAxAts0. .minzbBztszcT兩個特性：兩個特性：。是問題的一個可行內解ez . 12.min0min0TTc zc z若，則原線性規劃問

31、題無可行解或者無下界；若，則同時也就獲得了原線性規劃問題和對偶問題的一個最優解。進行如下投影變換：進行如下投影變換： 1 11,11,kkTTTTkkzzze ze zyzz記向量0. .minzbBztszcTmin, 0. .,010TTcystBb ye yy兩個特性：兩個特性：1.1eyk是問題的一個可行內點解。2.0若最優值，則同時也就獲得了原線性規劃問題和對偶問題的一個最優解。3.0 |,0 x Axb xKarmarkarKarmarkar若最優值，則原線性規劃問題無可行解或無下界；此時，可以從出發，構造相應的標準形，通過求解這個標準形，即可判斷原來的線性規劃問題是無界還是無可行

32、解。用用Karmarkar投影尺度算法求解如下線性規劃：投影尺度算法求解如下線性規劃：12123123123min. .526,0 xxstxxxxxxx x x引入松弛變量，化為標準型引入松弛變量，化為標準型1 11 105,1,1, 0, 0, 01 12016TAbc 化為化為Karmarkar標準型標準型 5558 15514000,000, 00 ,1, 0TTTTTTTTAbAebBbAAIceccbbc ec(0)16/161/325(4.42878,5,8.8574TkkTyeLKarmarkarB Bxee算法初始點，步長因子，精度參數，算法開始時，標準形的目標函數值為0.0

33、625，勢函數值為0，經過97次迭代后，對稱正定矩陣接近奇異，勢函數值不再下降，此時，目標函數值為2.1130e-09,勢函數值=-176.97.此時，線性規劃問題標準形式的近優解、對偶問題近優解及對偶間隙分別為：8,8.85748,1)( 1,9.82866),1.13474.TTTewec xb we *(0,5, 0, 0,1)Tx min( ). .0Tc xLstAxbxmax(). .0TTb yDstA ywcw1111, ( )nnmmm ncxbyAr Am |,0,|,0TLDySx Axb xSA ywc ww |,0,|,0LDTySx Axb xSA ywc ww12

34、12, ,0,00( ,),(,),Tninix y wAxbxA ywcwXWeXdiag x xxxxiWdiag w wwwwi為最優解的充要條件是：其中為 的第 個分量；為 的第 個分量Karush-Kuhn-Tucker條件條件,0,0TAxbxA ywcwXWee松弛松弛KKT條條件件1( )LLSKKT定理設可行域有界且內部非空，則對每個正數 ，松弛條件存在唯一內點解.12222121( , )ln.111( , ),( , )min( , ). .nTLjjxLnSB xc xxB xdiagSxxxB xB xstAxb證明：在上定義障礙函數在上正定，為嚴格凸函數，凸規劃有唯

35、一最優解。1111( , )ln()1( , )0( , )()0,0,0,0,0(*)00nTTjjTxTjiLxc xxAxbLxcX eALxAxbxyX ew wAxbxA ywcwXWeexwKKTKK 存在唯一駐點，即下列方程組有唯一解：記則上式等價于由于或的點均非松弛的可行解，所以（*）的唯一解就是松弛T的唯一解。定義原始定義原始-對偶可行集對偶可行集( , , )|, ( , )0( , , )|, ( , )0TTSx y wAxb A ywcx wSx y wAxb A ywcx w( ), ( ),( ) |0 xyw原始原始-對偶中心路徑對偶中心路徑2( )( ).TTc xb yn定理在中心路徑上，當 減少時，原問題的目標值單調減少且趨于最優值，對偶問題的目標值單調增加且趨于最優值，對于中心路徑參數 ，對偶間隙1212111111222212112211112211112210,()(),1(),()ln()1(),()ln()11()ln()()ln()11()ln()()ln()1nTpjjnTpjjnnTTjjjjnnTTjjjjxxBxc xxBxc x