偏差仿真中排列組合單步遞推算法

劉 峰

（中國運載火箭技術(shù)研究院研究發(fā)展中心，北京，100076）

0 引 言

飛行器研制過程如圖1所示，通常采用六自由度仿真試驗考核飛行器控制系統(tǒng)的性能，通過遍歷飛行器偏差模型前幾項的極限工況，評估偏差項對系統(tǒng)性能的影響程度，找出影響的主要因素。當(dāng)偏差項有序關(guān)聯(lián)時，需要通過選排列方式遍歷偏差模型的前幾項，當(dāng)偏差項相互獨立時，只需要通過組合方式遍歷偏差模型的前幾項。

傳統(tǒng)上的排列組合遍歷方法中[1,2]，特別是組合遍歷，采用傅克慎[3]法的具有較高的運算效率，但生成的組合遍歷序列不具備有序性。趙天玉[4]法體現(xiàn)了遞歸思想，給出了組合構(gòu)造與序號的函數(shù)對應(yīng)關(guān)系，但全面的構(gòu)造有損運算效率；王孫安等文獻[5～8]給出了組合遍歷的算法研究與應(yīng)用實例。

圖1 飛行器控制系統(tǒng)六自由度仿真試驗設(shè)備示意Fig.1 Six Degree of Freedom Simulation Test Equipment for Aircraft Control System

本文提出多種遍歷算法，分別為全排列遍歷和組合遍歷的序數(shù)解析算法和單步遞推算法，從形式上采用序數(shù)解析方式或單步遞推方式便于不同遍歷的相互嵌套應(yīng)用，生成的組合遍歷序列具備有序性，基于運算量優(yōu)選得到全排列遍歷和組合遍歷的單步遞推算法，遍歷序列有序，有利于事后開展偏差因素影響對比分析等工作。

1 排列組合算法原理

1.1 排列組合基本公式

由《數(shù)學(xué)手冊》第1.1節(jié)[1]和《實用數(shù)學(xué)手冊》第1.3節(jié)[2]可知，從n個不同的元素中，每次取出n個不同的元素，按一定的順序排成一列，稱為全排列，其排列種數(shù)為

從n個不同的元素中，每次取出k個不同的元素，不管其順序合并成一組，稱為組合，其組合種數(shù)為不同的元素，按一定的順序排成一列，稱為選排列，其排列種數(shù)為

從n個不同的元素中，每次取出k個

可知，選排列可以表示成組合下嵌套全排列。

1.2 全排列遍歷的序數(shù)解析

在交換實現(xiàn)排列中，在從1～n的基本整數(shù)序列的基礎(chǔ)上，根據(jù)商數(shù)序列調(diào)整基本整數(shù)序列中數(shù)據(jù)項的位置，實現(xiàn)當(dāng)前排列序列。當(dāng)商數(shù)序列的當(dāng)前值為零時，表示將基本整數(shù)序列當(dāng)前下標(biāo)的非零值移到排列序列的對應(yīng)位置，基本整數(shù)序列的當(dāng)前值為零時，自動向后搜索，在移動后將基本整數(shù)序列的被移動值清零；當(dāng)商數(shù)序列的當(dāng)前值為正i時，表示將基本整數(shù)序列當(dāng)前后第i個下標(biāo)的非零值移到排列序列的對應(yīng)位置，基本整數(shù)序列的當(dāng)前值為零時，自動向后搜索，以此類推，得到商數(shù)序列d，使得：在移動后將基本整數(shù)序列的被移動值清零。

全部移動完畢后，基本整數(shù)序列被全清零，得到的排列序列即為序數(shù)解析后對應(yīng)全排列遍歷中某一特定的排列。

1.3 組合遍歷的序數(shù)解析

在確定分支中，按照楊輝三角將數(shù)據(jù)分解為路徑，確定左右支路，左小右大，則左支路取1、右支路取0。根據(jù)組合遞推計算公式有

通過左右支路向上遍歷到楊輝三角的頂部后，得到的組合序列即為序數(shù)解析后對應(yīng)組合遍歷中某一特定的排列。

1.4 單步遞推中關(guān)于整數(shù)序列的名詞解釋

全排列遍歷或組合遍歷中，首先生成整數(shù)序列，從左到右，該序列的左端第 1項稱為首項或左端項，左端第2項稱為次項，右端第1項稱為末項或右端項；在搜索過程中，當(dāng)前搜索索引對應(yīng)項稱為當(dāng)前項，鄰近當(dāng)前項的左側(cè)第 1項稱為左側(cè)項，鄰近當(dāng)前項的右側(cè)第1項稱為右側(cè)項。

1.5 全排列遍歷的單步遞推

單步遞推時，從數(shù)列右端向左搜索，若當(dāng)前項大于左側(cè)項，則停止搜索，完全顛倒從右端項到當(dāng)前項的所有項的順序，然后在右端項到當(dāng)前項序列中找出比左側(cè)項大的最小項，并將其與左側(cè)項交換，由此生成新的序列，作為當(dāng)前全排列遍歷的單步遞推結(jié)果。

當(dāng)搜索序列到次項仍不滿足當(dāng)前項大于左側(cè)項的條件，即此時首項大于次項，數(shù)列從左到右按照從大到小排列，則單步遞推過程中止，循環(huán)結(jié)束，流程圖如圖2所示。

圖2 全排列單步遞推的算法流程Fig.2 Single Step Recursive Algorithm for Full Permutation

1.6 組合遍歷的單步遞推

單步遞推時，從數(shù)列右端向左搜索，若當(dāng)前項大于左側(cè)項，則停止搜索，完全顛倒從右端項到右側(cè)項的所有項的順序，交換當(dāng)前項與左側(cè)項，由此生成新的序列，作為當(dāng)前組合遍歷的單步遞推結(jié)果。

當(dāng)搜索序列到次項仍不滿足當(dāng)前項大于左側(cè)項的條件，即此時首項與次項均為1，數(shù)列從左到右的k項為1，剩余項賦值為0，則單步遞推過程中止，循環(huán)結(jié)束，流程如圖3所示。

圖3 組合單步遞推的算法流程Fig. 3 Combined Single Step Recursive Algorithm Flow

全排列遍歷和組合遍歷的單步遞推算法生成的序列存在有序性，故沒有重復(fù)確保唯一；單步遞推算法從遞歸角度迭代次數(shù)符合全排列遍歷和組合遍歷的性質(zhì)，故沒有遺漏確保完備。

2 排列組合算例推演與分析

2.1 算法的軟件開發(fā)環(huán)境

排列組合遍歷算法基于Windows操作系統(tǒng)，采用Visual C++ 6.0（VC6）編譯環(huán)境和C語言開發(fā)，以VC6提供的編譯環(huán)境進行指令條數(shù)統(tǒng)計。為給出直觀的可比性，統(tǒng)計Math.h中基本數(shù)學(xué)函數(shù)的指令條數(shù)如表1所示（取x=0.618）。計算其全排列序列。首先依次整除4!3!2!1!，得到商數(shù)序列A如下：

表1 基本數(shù)學(xué)函數(shù)的指令條數(shù)Tab.1 Mumber of Instructions for Basic Mathematical Functions

2.2 全排列遍歷序數(shù)解析的算例

在序數(shù)解析時，取n=5時的序數(shù)s=59，

第1步：A中第1項為2，則將N中非零首項后的第2項移到P中，原位置清零得到：

式中 ?表示空位。

第2步：A中第2項為1，則將N中非零首項后的第1項移到P中，原位置清零得到：

依此類推，最后得到目標(biāo)序列：

仿真分析可知，軟件中生成每個排列的平均指令數(shù)為340.00條。

2.3 組合遍歷序數(shù)解析的算例

仿真分析可知，軟件中生成每個組合的平均指令數(shù)為256.68條。

2.4 全排列遍歷單步遞推算例與統(tǒng)計分析

在單步遞推時，取n=5的某一組全排列狀態(tài)如下：

從數(shù)列右端向左搜索，當(dāng)前項5大于左側(cè)項2，停止搜索，有：

完全顛倒從右端項1到當(dāng)前項5的所有項順序，有：

在右端項到當(dāng)前項序列中找出比左側(cè)項大的最小項4，并將其與左側(cè)項2交換，由此生成新的序列，作為當(dāng)前組合遍歷的單步遞推結(jié)果如下：

單步遞推時，計算 5n=的所有全排列狀態(tài)的軟件指令條數(shù)如圖 3所示。生成每個組合平均指令數(shù)為91.43條。

圖4 所有全排列狀態(tài)的軟件指令條數(shù)Fig.4 Number of Software Instructions in All Arranged States

在單步遞推時，計算不同n工況下的所有全排列狀態(tài)的軟件指令條數(shù)如表2所示。

表2 不同工況下全排列狀態(tài)的軟件指令條數(shù)Tab.2 Number of Software Instructions in Full Arrangement under Different Working Conditions

從數(shù)列右端向左搜索，若當(dāng)前項1大于左側(cè)項0，得到第1個連續(xù)非零的序列，則停止搜索，有：

完全顛倒從右端項到右側(cè)項的所有項的順序，交換當(dāng)前項與左側(cè)項，由此生成新的序列，作為當(dāng)前組合遍歷的單步遞推結(jié)果如下：

2.5 組合遍歷單步遞推算例與統(tǒng)計分析

單步遞推時，取n=7，k=5某一組組合狀態(tài)如下：

在完全顛倒順序的算法中采用折半法可以提高運算效率。

圖5 所有組合狀態(tài)的軟件指令條數(shù)Fig.5 Number of Software Instructions in AllCombination States

在單步遞推時，計算不同n與k組合工況下的所有組合狀態(tài)的軟件指令條數(shù)如表3所示。

表3 不同組合工況下組合狀態(tài)的軟件指令條數(shù)Tab.3 Number of Software Instructions under Different Combination Conditions

2.6 在偏差仿真中的應(yīng)用

以某飛行器為例，在偏差仿真中共考慮 7n=項偏差，從中隨機選擇 3k=項進行打靶仿真，則構(gòu)造初始組合數(shù)列如下：

其中，按照順序的某一位為1時表示選擇7項中的某一項，為 0時表示不選，然后可通過單步遞推實現(xiàn)偏差項的取舍，從而實現(xiàn)對偏差項的全局遍歷。

假設(shè) 7項偏差分別為：大氣密度、水平風(fēng)、氣動系數(shù)、全彈質(zhì)量、飛行器質(zhì)量、大氣壓強和風(fēng)向角，隨機選取3項進行組合遍歷的選取狀態(tài)如圖6所示。

圖6 7項偏差下的組合遍歷狀態(tài)Fig.6 Combinatorial Ergodic States under 7 Deviations

續(xù)圖6

通過帶制導(dǎo)的偏差仿真得到組合偏差下熱流和動壓的最大值如圖7所示。

圖7 組合偏差下的熱流和動壓Fig.7 Heat Flow and Dynamic Pressure under Combined Deviations

通過分析可知，氣動系數(shù)和水平風(fēng)為影響熱流的主要因素，氣動系數(shù)和大氣密度為影響動壓的主要因素。取一項偏差進行遍歷的結(jié)果與極限偏差法等價，組合所有偏差極限工況進行遍歷的結(jié)果與枚舉法等價，而取有限個偏差項進行組合遍歷，便于實現(xiàn)運算效率與交叉影響分析之間的均衡。

3 結(jié)束語

本文給出了全排列和組合的序數(shù)解析算法和單步遞推算法，序數(shù)解析算法得到的排列組合序列與序數(shù)嚴(yán)格對應(yīng)，意義直觀便于使用，只是相比的計算量稍大；單步遞推算法的計算量較小，且從算術(shù)意義上，可理解為初始化得到量值最低的狀態(tài)，中止時得到量值最高的狀態(tài)，單步遞推時對序列當(dāng)前項的左側(cè)項進位，通過顛倒順序使當(dāng)前項到右端項的序列獲得量值最低的狀態(tài)，通過單步遞推得到的全排列和組合在量值上嚴(yán)格按升冪排列。

此外，對于選排列遍歷，可以通過組合遍歷中嵌套全排列遍歷來實現(xiàn)。通過序數(shù)解析算法和單步遞推算法，極大方便了與其他形式的遍歷方式任意組合，能夠應(yīng)用到飛行器六自由度仿真試驗的偏差組合設(shè)計等各種離散問題的全局搜索中。