數(shù)學(xué)建模——組合優(yōu)化問(wèn)題及算法

1、-2- 組合最優(yōu)化（組合最優(yōu)化（combinatorial optimization)combinatorial optimization)是通過(guò)是通過(guò)對(duì)數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次對(duì)數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，是運(yùn)籌學(xué)序或篩選等，是運(yùn)籌學(xué)( (operations research)operations research)中的一個(gè)中的一個(gè)重要分支。所研究的問(wèn)題涉及信息技術(shù)、經(jīng)濟(jì)管理、工業(yè)重要分支。所研究的問(wèn)題涉及信息技術(shù)、經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸、通信網(wǎng)絡(luò)等領(lǐng)域。該問(wèn)題可用數(shù)學(xué)模型工程、交通運(yùn)輸、通信網(wǎng)絡(luò)等領(lǐng)域。該問(wèn)題可用數(shù)學(xué)模型描述為

2、：描述為：Dxxgtsxf 0)(. .)(min 其中其中D D表示有限個(gè)點(diǎn)組成的集合。表示有限個(gè)點(diǎn)組成的集合。-3- 1. 0-1 1. 0-1背包問(wèn)題背包問(wèn)題 設(shè)有一個(gè)容積為設(shè)有一個(gè)容積為b b的背包，的背包，n n個(gè)體積分別為個(gè)體積分別為a ai i(i(i=1,2,=1,2,n),n),價(jià)值分別為價(jià)值分別為c ci i (i=1,2, (i=1,2,n),n)的物品，如的物品，如何以最大的價(jià)值裝包？何以最大的價(jià)值裝包？ nixbxatsxciniiiniii, 1,1 , 0. .max11-4- 2. 2. 旅行商問(wèn)題旅行商問(wèn)題( (TSPTSP，travelingtravelin

3、g salesman problem) salesman problem) 一個(gè)商人欲到一個(gè)商人欲到n n個(gè)城市推銷商品，每?jī)蓚€(gè)城市個(gè)城市推銷商品，每?jī)蓚€(gè)城市i i和和j j之之間的距離為間的距離為d dijij，如何選擇一條道路使得商人每個(gè)城市正如何選擇一條道路使得商人每個(gè)城市正好走一遍后回到起點(diǎn)且所走路徑最短。好走一遍后回到起點(diǎn)且所走路徑最短。., 1,1 , 0, 2 , 1, 2|2, 1|, 1, 1, 1, 1. .min,11jinjixnSnSSxnjxnixtsxdijSjiijniijnjijnjiijij-5- 3. 3.有約束的機(jī)器調(diào)度問(wèn)題有約束的機(jī)器調(diào)度問(wèn)題( (ca

4、pacitated machine capacitated machine scheduling)scheduling) n n個(gè)加工量為個(gè)加工量為 d di i|i|i=1,2,=1,2,n,n的產(chǎn)品在一臺(tái)機(jī)器上加工，的產(chǎn)品在一臺(tái)機(jī)器上加工，機(jī)器在第機(jī)器在第t t個(gè)時(shí)段的工作能力為個(gè)時(shí)段的工作能力為c ct t, ,求完成所有產(chǎn)品加工所需時(shí)求完成所有產(chǎn)品加工所需時(shí)段數(shù)最少的調(diào)度方案段數(shù)最少的調(diào)度方案TtnixTtcxdnixtsTitnititiTtit, 2 , 1, 1,1 , 0,2 , 1, 1, 1. .min11 其中其中x xitit,T,T為決策變量為決策變量, ,x xit

5、it=1=1表示產(chǎn)品表示產(chǎn)品i i在第在第t t時(shí)段加工時(shí)段加工-6- 4. 4. 裝箱問(wèn)題裝箱問(wèn)題( (bin packing)bin packing) 如何把如何把n n個(gè)尺寸不超過(guò)個(gè)尺寸不超過(guò)1 1的物品裝入尺寸為的物品裝入尺寸為1 1的箱子，并使所的箱子，并使所用的箱子個(gè)數(shù)最少用的箱子個(gè)數(shù)最少。 5. 5. 二維裝箱問(wèn)題（平面上的套裁問(wèn)題）二維裝箱問(wèn)題（平面上的套裁問(wèn)題） 原料的尺寸大于需求的尺寸，需求的品種尺寸可以不同，原料的尺寸大于需求的尺寸，需求的品種尺寸可以不同，最終的目標(biāo)是在滿足需求的前提下，使邊角余料最小。最終的目標(biāo)是在滿足需求的前提下，使邊角余料最小。 6. 6. 車間作

6、業(yè)調(diào)度問(wèn)題車間作業(yè)調(diào)度問(wèn)題( (job shop scheduling)job shop scheduling) n n個(gè)工件，個(gè)工件，J J1 1, , ,J Jn n在在m m臺(tái)機(jī)器臺(tái)機(jī)器M M1 1,M,M2 2, ,M,Mm m上加工。每個(gè)工上加工。每個(gè)工件件J Ji i有有n ni i個(gè)工序，個(gè)工序，O Oi1i1, , ,O Oiniini, ,第第O Oijij工序的加工時(shí)間為工序的加工時(shí)間為p pijij，必須必須按工序進(jìn)行加工且每一工序必須一次加工完成。一臺(tái)機(jī)器在任按工序進(jìn)行加工且每一工序必須一次加工完成。一臺(tái)機(jī)器在任何時(shí)刻最多只能加工一個(gè)產(chǎn)品，一個(gè)工件不能同時(shí)在兩臺(tái)機(jī)器何時(shí)

7、刻最多只能加工一個(gè)產(chǎn)品，一個(gè)工件不能同時(shí)在兩臺(tái)機(jī)器上加工，如何安排才能使最后一個(gè)完工的工件完工時(shí)間最小？上加工，如何安排才能使最后一個(gè)完工的工件完工時(shí)間最??？-7- 7. 7. 最大截問(wèn)題最大截問(wèn)題( (MCP,MaxMCP,Max Cut Problem) Cut Problem) 8. 8. 圖的頂點(diǎn)著色問(wèn)題圖的頂點(diǎn)著色問(wèn)題（GCP,GraphGCP,Graph ColouringColouring Problem) Problem) 9. 9. 獨(dú)立集問(wèn)題（獨(dú)立集問(wèn)題（ISP,IndependentISP,Independent Set Problem) Set Problem) 10.

8、 10.調(diào)度問(wèn)題調(diào)度問(wèn)題( (SCP,SchedulingSCP,Scheduling Problem) Problem) 11. 11.劃分問(wèn)題劃分問(wèn)題( (PAP,PartitionPAP,Partition Problem) Problem) 12. 12.布局問(wèn)題（布局問(wèn)題（PLP, Placement Problem)PLP, Placement Problem) 上述問(wèn)題都是上述問(wèn)題都是NP-hardNP-hard問(wèn)題，目前人們認(rèn)為它們不存在問(wèn)題，目前人們認(rèn)為它們不存在求解最優(yōu)解的多項(xiàng)式時(shí)間算法，大規(guī)模情形只有嘗試用一求解最優(yōu)解的多項(xiàng)式時(shí)間算法，大規(guī)模情形只有嘗試用一些近似算法或啟

9、發(fā)式算法求解。些近似算法或啟發(fā)式算法求解。 -8-鄰域概念鄰域概念 對(duì)于組合優(yōu)化問(wèn)題對(duì)于組合優(yōu)化問(wèn)題( (D,F,f),DD,F,f),D上的一個(gè)映射：上的一個(gè)映射： N:S N:S D D N(S) N(S) 2 2D D稱為一個(gè)鄰域映射，其中稱為一個(gè)鄰域映射，其中2 2D D表示表示D D的所有子集構(gòu)的所有子集構(gòu)成的集合，成的集合，N(S)N(S)稱為稱為S S的鄰域。的鄰域。 鄰域的構(gòu)造依賴于問(wèn)題決策變量的表示，鄰鄰域的構(gòu)造依賴于問(wèn)題決策變量的表示，鄰域的結(jié)構(gòu)在現(xiàn)代化優(yōu)化算法中起重要作用。域的結(jié)構(gòu)在現(xiàn)代化優(yōu)化算法中起重要作用。-9-鄰域概念鄰域概念例如，前面例子例如，前面例子2 2給出的

10、給出的TSPTSP問(wèn)題模型。由解空間問(wèn)題模型。由解空間D=xD=x 0,10,1n n (n-1)(n-1) ，可以定義它的一種鄰域?yàn)椋嚎梢远x它的一種鄰域?yàn)椋簀iijijDykxyxyyxN,|)( k k為一個(gè)正整數(shù)。為一個(gè)正整數(shù)。TSPTSP問(wèn)題解的另一種表示法為問(wèn)題解的另一種表示法為D=S=(iD=S=(i1 1,i,i2 2, ,i,in n) )是是1,2,1,2, ,n n的一個(gè)排列的一個(gè)排列 -10-鄰域概念鄰域概念 TSP TSP問(wèn)題解的另一種表示法為問(wèn)題解的另一種表示法為D=S=(iD=S=(i1 1,i,i2 2, ,i,in n) )是是1,2,1,2, ,n n的一個(gè)

11、排列的一個(gè)排列 可以定義它的鄰域映射為可以定義它的鄰域映射為2-2-optopt，即即S S中的兩個(gè)中的兩個(gè)元素對(duì)換。元素對(duì)換。 如如4 4個(gè)城市的個(gè)城市的TSPTSP問(wèn)題，當(dāng)問(wèn)題，當(dāng)S=(1,2,3,4)S=(1,2,3,4)時(shí)，時(shí)，N(S)=(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,N(S)=(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4),(1,4,3,2),(1,2,4,3).2,4),(1,4,3,2),(1,2,4,3). 類似可定義類似可定義k-opt(kk-opt(k 2)2)-11-局部最優(yōu)與全局最優(yōu)局部最優(yōu)與全局最優(yōu)

12、 若若s s* *滿足滿足 f(s f(s* *) ) ( ( )f(s),)f(s),其中其中s s N(sN(s* *) ) F,F,則稱則稱s s* *為為f f在在F F上的局部上的局部( (local)local)最?。ㄗ畲螅┙狻Ｗ钚。ㄗ畲螅┙?。 若若s s* *滿足滿足 f(s f(s* *) ) ( ( )f(s),)f(s),其中其中s s F,F,則稱則稱s s* *為為f f在在F F上的全局上的全局( (global)global)最?。ㄗ畲螅┳钚。ㄗ畲螅┙狻＝?。-12- 啟發(fā)式算法定義啟發(fā)式算法定義 一個(gè)基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受一個(gè)基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在

13、可接受的花費(fèi)（計(jì)算時(shí)間、占用空間等）下給出待解決的花費(fèi)（計(jì)算時(shí)間、占用空間等）下給出待解決問(wèn)題每一個(gè)實(shí)例的一個(gè)可行解，該解與最優(yōu)解的問(wèn)題每一個(gè)實(shí)例的一個(gè)可行解，該解與最優(yōu)解的偏離程度不一定能預(yù)計(jì)。偏離程度不一定能預(yù)計(jì)。 啟發(fā)式算法是一種技術(shù)，使在可接受的計(jì)算啟發(fā)式算法是一種技術(shù)，使在可接受的計(jì)算開(kāi)銷內(nèi)尋找最好的解，但不一定能保證所得解的開(kāi)銷內(nèi)尋找最好的解，但不一定能保證所得解的可行性和最優(yōu)性，甚至多數(shù)情況下，無(wú)法給出所可行性和最優(yōu)性，甚至多數(shù)情況下，無(wú)法給出所得解同最優(yōu)解的近似程度。得解同最優(yōu)解的近似程度。 -13-近似算法定義近似算法定義 記問(wèn)題記問(wèn)題A A的任何一個(gè)實(shí)例的任何一個(gè)實(shí)例I I

14、的最優(yōu)解和啟發(fā)式的最優(yōu)解和啟發(fā)式算法算法H H解的目標(biāo)值分別為解的目標(biāo)值分別為z zoptopt(I(I) )和和z zH H(I(I),),若對(duì)某若對(duì)某個(gè)正數(shù)個(gè)正數(shù)0 0，有，有 | |z zH H(I)-z(I)-zoptopt(I(I)|)| | |z zoptopt(I)|(I)|， I I A A則稱則稱H H是是A A的的 近似算法。近似算法。-14- 1 1）將物品以）將物品以c ci i/a/ai i（單位體積的價(jià)值）由大到小的順單位體積的價(jià)值）由大到小的順序排列，不妨把排列記為序排列，不妨把排列記為1,2,1,2, ,n,kn,k:=1;:=1;2 2）若若 ，則，則x xk

15、 k=1;=1;否則否則x xk k=0,k:=k+1;=0,k:=k+1;3) 3) 當(dāng)當(dāng)k=n+1k=n+1時(shí)，停止；否則，轉(zhuǎn)時(shí)，停止；否則，轉(zhuǎn)2).2).( (x x1 1,x,x2 2, , ,x xn n) )為貪婪算法所得解，單位體積的價(jià)值越為貪婪算法所得解，單位體積的價(jià)值越大越先放入是貪婪算法的原則。大越先放入是貪婪算法的原則。11kikiibdxd-15- 給定組合優(yōu)化問(wèn)題，假設(shè)其鄰域結(jié)構(gòu)已確給定組合優(yōu)化問(wèn)題，假設(shè)其鄰域結(jié)構(gòu)已確定，算法為定，算法為1 1）任選一個(gè)初始解）任選一個(gè)初始解s s0 0 F;F;2) 2) 在在N(sN(s0 0) )中按某一規(guī)則選一中按某一規(guī)則選一

16、s s；若若f(sf(s)f(s)lL Lk k，則到則到4 4）；否則，從鄰域）；否則，從鄰域N(xN(xi i) )中隨機(jī)選中隨機(jī)選一一x xj j, ,計(jì)算計(jì)算 f fijij= =f(xf(xj j)-f(x)-f(xi i); l); ll+1;l+1;若若 f fijij 0 0，則則x xi ix xj j; ; 否則否則, ,若若exp(-exp(- f fijij/t/tk k)random)random（0,1)0,1)）時(shí)，時(shí)，x xi ix xj j；重復(fù)重復(fù)3 3）；）；4 4）t tk+1k+1;k ;k k+1k+1；計(jì)算計(jì)算L Lk k，若滿足若滿足，終止計(jì)算，

17、否則，回到終止計(jì)算，否則，回到2).2).-21- 已證明，模擬退火算法以已證明，模擬退火算法以1 1的概率收斂到整體的概率收斂到整體最優(yōu)解集，但漸近收斂到最優(yōu)解集須經(jīng)歷無(wú)限多最優(yōu)解集，但漸近收斂到最優(yōu)解集須經(jīng)歷無(wú)限多次變換。次變換。 對(duì)最優(yōu)解任意近似的逼近，對(duì)多數(shù)組合優(yōu)化對(duì)最優(yōu)解任意近似的逼近，對(duì)多數(shù)組合優(yōu)化問(wèn)題都導(dǎo)致比解空間規(guī)模大的變換數(shù)，從而導(dǎo)致問(wèn)題都導(dǎo)致比解空間規(guī)模大的變換數(shù)，從而導(dǎo)致算法的指數(shù)時(shí)間執(zhí)行。算法的指數(shù)時(shí)間執(zhí)行。 解決辦法：犧牲保證得到最優(yōu)解為代價(jià)，在解決辦法：犧牲保證得到最優(yōu)解為代價(jià)，在多項(xiàng)式時(shí)間里，逼近模擬退火算法的漸近收斂狀多項(xiàng)式時(shí)間里，逼近模擬退火算法的漸近收斂狀態(tài)

18、，返回一個(gè)近似最優(yōu)解。態(tài)，返回一個(gè)近似最優(yōu)解。-22-模擬退火算法應(yīng)用的一般要求模擬退火算法應(yīng)用的一般要求1)1) 數(shù)學(xué)模型數(shù)學(xué)模型 解空間、目標(biāo)函數(shù)和初始解解空間、目標(biāo)函數(shù)和初始解2 2）新解的產(chǎn)生和接受機(jī)制）新解的產(chǎn)生和接受機(jī)制新解產(chǎn)生新解產(chǎn)生: :當(dāng)前解經(jīng)簡(jiǎn)單變換產(chǎn)生新解（決定當(dāng)前解經(jīng)簡(jiǎn)單變換產(chǎn)生新解（決定了當(dāng)前解的鄰域結(jié)構(gòu)），如對(duì)當(dāng)前解的全部了當(dāng)前解的鄰域結(jié)構(gòu)），如對(duì)當(dāng)前解的全部或部分元素進(jìn)行置換、互換或反演等。或部分元素進(jìn)行置換、互換或反演等。MetropolisMetropolis接受準(zhǔn)則接受準(zhǔn)則: : 3 3）冷卻進(jìn)度表的設(shè)定）冷卻進(jìn)度表的設(shè)定0)/exp(01ftffP-23-

19、 冷卻進(jìn)度表是一組控制算法進(jìn)程的參數(shù)，冷卻進(jìn)度表是一組控制算法進(jìn)程的參數(shù)，它包括：它包括：1.1.初始溫度初始溫度t t0 0 = =tmaxtmax2.2.溫度衰減函數(shù)溫度衰減函數(shù)T(tT(t) )3.Markov3.Markov鏈的長(zhǎng)度鏈的長(zhǎng)度L Lk k4.4.終止溫度終止溫度t tf f（停止準(zhǔn)則）（停止準(zhǔn)則） 。-24- 雖然已經(jīng)證明模擬退火算法在一定條件雖然已經(jīng)證明模擬退火算法在一定條件下的漸近收斂性。但這并不意味著任意下的漸近收斂性。但這并不意味著任意冷卻冷卻進(jìn)度表都能確保算法收斂進(jìn)度表都能確保算法收斂，不合理的冷卻進(jìn)不合理的冷卻進(jìn)度表會(huì)使算法在某些解間度表會(huì)使算法在某些解間“振

20、蕩振蕩”而不能收而不能收斂于某一近似解。斂于某一近似解。 模擬退火算法的最終解質(zhì)量和模擬退火算法的最終解質(zhì)量和CPUCPU時(shí)間呈時(shí)間呈反向關(guān)系，很難兩全其美，妥善解決辦法只反向關(guān)系，很難兩全其美，妥善解決辦法只有：折中，即在合理的有：折中，即在合理的CPUCPU時(shí)間里盡量提高最時(shí)間里盡量提高最終解的質(zhì)量。這涉及到冷卻進(jìn)度表所有參數(shù)終解的質(zhì)量。這涉及到冷卻進(jìn)度表所有參數(shù)的合理選取。的合理選取。 -25-1.1.初始溫度初始溫度t t0 0 的選取的選取 t t0 0 要取得足夠大，要取得足夠大，JohnsonJohnson等建議通過(guò)等建議通過(guò)計(jì)算若干次隨機(jī)變換目標(biāo)函數(shù)平均增量的方計(jì)算若干次隨機(jī)變

21、換目標(biāo)函數(shù)平均增量的方法來(lái)確定法來(lái)確定t t0 0的值。的值。)ln(100ft其中，其中， 為上述平均增量，為上述平均增量， 為初始接受率，為初始接受率，一般取一般取0.80.8 1 1之間的數(shù)。之間的數(shù)。f0-26-2.2.溫度衰減函數(shù)溫度衰減函數(shù)T(tT(t) )的選取的選取 一個(gè)常用的溫度衰減函數(shù)是溫度衰減函數(shù)是, 2 , 1 , 0,1kttkk其中，取為0.5 0.990.99之間的數(shù)。之間的數(shù)。 SkiscimSkiscim等人固定控制參數(shù)值的衰減步等人固定控制參數(shù)值的衰減步數(shù)數(shù)K,K, 把區(qū)間把區(qū)間0,0,t t0 0 劃分為劃分為K K個(gè)小區(qū)間，把溫個(gè)小區(qū)間，把溫度衰減函數(shù)取

22、為度衰減函數(shù)取為KktKkKtk, 2 , 1,0-27-3.Markov3.Markov鏈的長(zhǎng)度鏈的長(zhǎng)度L Lk k的選取的選取1 1）固定長(zhǎng)度固定長(zhǎng)度 L Lk k通常取為問(wèn)題規(guī)模通常取為問(wèn)題規(guī)模 n n的一個(gè)多項(xiàng)式函數(shù)。的一個(gè)多項(xiàng)式函數(shù)。如，如，KirkpatricKirkpatric等等 L Lk k=n=n或或100100n,n, AarsAars等等 L Lk k= =鄰域規(guī)模鄰域規(guī)模 2 2）由接受和拒絕的比率來(lái)控制）由接受和拒絕的比率來(lái)控制L Lk k 當(dāng)溫度很高時(shí)，當(dāng)溫度很高時(shí)，L Lk k應(yīng)盡量小，隨著溫度的應(yīng)盡量小，隨著溫度的漸漸下降，漸漸下降，L Lk k逐步增大。逐步

23、增大。 -28-3.Markov3.Markov鏈的長(zhǎng)度鏈的長(zhǎng)度L Lk k的選取的選取2 2）由接受和拒絕的比率來(lái)控制）由接受和拒絕的比率來(lái)控制L Lk k ：給定一個(gè)充分大的：給定一個(gè)充分大的長(zhǎng)度上限長(zhǎng)度上限U U和一個(gè)接受次數(shù)指標(biāo)和一個(gè)接受次數(shù)指標(biāo)R,R,當(dāng)接受次數(shù)等當(dāng)接受次數(shù)等于于R R時(shí)，此溫度不再迭代而使溫度下降。時(shí)，此溫度不再迭代而使溫度下降。 ：給定一個(gè)接受比率：給定一個(gè)接受比率指標(biāo)指標(biāo)R,R,長(zhǎng)度上限長(zhǎng)度上限U U和下限和下限L,L,當(dāng)?shù)螖?shù)超過(guò)當(dāng)?shù)螖?shù)超過(guò)L L時(shí)時(shí)，若接受次數(shù)與迭代次數(shù)的比率不小于，若接受次數(shù)與迭代次數(shù)的比率不小于R R時(shí)，此時(shí)，此溫度不再迭代而使溫度

24、下降，否則，一直迭代溫度不再迭代而使溫度下降，否則，一直迭代到上限步數(shù)到上限步數(shù)U U。-29-4.4.終止溫度終止溫度t tf f（停止準(zhǔn)則）的選?。ㄍＶ箿?zhǔn)則）的選取1 1）零度法零度法2 2）循環(huán)總數(shù)控制法）循環(huán)總數(shù)控制法3 3）基于不改進(jìn)規(guī)則的控制法）基于不改進(jìn)規(guī)則的控制法4 4）接受概率控制法）接受概率控制法 3 3）和）和4 4）的實(shí)現(xiàn)：在一個(gè)溫度和給定的迭代次）的實(shí)現(xiàn)：在一個(gè)溫度和給定的迭代次數(shù)內(nèi)，沒(méi)有改進(jìn)當(dāng)前的局部最優(yōu)解或接受概率都小數(shù)內(nèi)，沒(méi)有改進(jìn)當(dāng)前的局部最優(yōu)解或接受概率都小于一個(gè)給定的比較小的數(shù)于一個(gè)給定的比較小的數(shù) f f, ,則停止運(yùn)算則停止運(yùn)算. .5 5）鄰域法）鄰域

25、法當(dāng)當(dāng) 時(shí)，停止計(jì)算。時(shí)，停止計(jì)算。f f0 0,f,f1 1分別為一個(gè)分別為一個(gè)鄰域內(nèi)的局部最優(yōu)和次最優(yōu)，鄰域內(nèi)的局部最優(yōu)和次最優(yōu)，N N為鄰域的大小。為鄰域的大小。Ntff1)exp(01-30- 高效、健壯、通用、靈活高效、健壯、通用、靈活1 1）高效性）高效性 與局部搜索算法相比，模擬退火算法可望在與局部搜索算法相比，模擬退火算法可望在較短時(shí)間里求得更優(yōu)近似解；允許任意選取初始較短時(shí)間里求得更優(yōu)近似解；允許任意選取初始解，且能得出較優(yōu)近似解，因此應(yīng)用該算法解組解，且能得出較優(yōu)近似解，因此應(yīng)用該算法解組合優(yōu)化問(wèn)題的前期工作量大大減少。合優(yōu)化問(wèn)題的前期工作量大大減少。2 2）健壯性健壯性 該算法的實(shí)驗(yàn)