棋陣多項(xiàng)式生成算法及其在禁位排列中的應(yīng)用研究

孫靜

摘 要：棋陣多項(xiàng)式生成算法擁有自己獨(dú)立的計(jì)算原理，主要結(jié)合多種方法比較算法中的優(yōu)缺點(diǎn)，最后得出最優(yōu)算法實(shí)現(xiàn)設(shè)計(jì)程序，通過禁位排列顯示算法在顯示應(yīng)用中實(shí)現(xiàn)計(jì)算過程。本文介紹了棋陣多項(xiàng)式生成算法的基本概念與正規(guī)布局形式。隨后對棋陣多項(xiàng)式的基本性質(zhì)、傳統(tǒng)計(jì)算方法以及禁位排列實(shí)際應(yīng)用展開分析。

關(guān)鍵詞：棋陣多項(xiàng)式生成算法;組合數(shù)學(xué);棋盤;組合法;禁位排列

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-9052（2020）03-0188-02

在組合數(shù)學(xué)中存在棋陣多項(xiàng)式這一重要工具，它能夠被應(yīng)用于禁位排列、博弈問題中且具有廣泛用途。同時(shí)可在棋陣多項(xiàng)式中生成常用算法，這其中就包括了分部相乘法、直接觀察法以及關(guān)鍵點(diǎn)遞歸法。但客觀講，這3種算法適用性表現(xiàn)普遍較差，且技巧性強(qiáng)不易自動(dòng)生成關(guān)鍵節(jié)點(diǎn)，存在各種缺點(diǎn)問題。為有效克服這些問題，需要研究提出一種新生成算法，即組合法。組合法具有較強(qiáng)的適用性，且非常利于程序?qū)崿F(xiàn)，例如它在禁位排列中的應(yīng)用就是一個(gè)較好的例子。

1 棋陣多項(xiàng)式生成算法的基本理論

棋陣多項(xiàng)式生成算法中的基本理論內(nèi)容豐富，包含了棋盤、正規(guī)布局等內(nèi)容，同時(shí)也要對棋陣多項(xiàng)式的基本性質(zhì)進(jìn)行分析，下文將一一列舉分析。

1.1 棋盤的基本概念

一般來說，棋陣多項(xiàng)式中的棋盤都是由單位正方形所構(gòu)成的，具體如圖1。

如圖1，在棋盤C中如果嘗試刪除某一個(gè)格子，它所在的行列中剩余的棋盤可標(biāo)記為C1，棋盤C中在刪除掉某一格子后所剩下的棋盤標(biāo)記為C2。假設(shè)棋盤中棋盤1為C，那么可以將其它格子設(shè)置為C的黑點(diǎn)，棋盤2、3分別代表了棋盤C2以及C1。另外棋盤C中還包含了C3和C4兩部分，且二者是相互分離的。棋盤4是可分離的，但其余棋盤是無法分離的[1]。

1.2 正規(guī)布局的基本概念

在正規(guī)布局中可將k個(gè)數(shù)量的棋子都放在棋盤C上構(gòu)建多種布局方式，確保每行每列都存在一個(gè)棋子的布局并作為正規(guī)布局。假設(shè)棋盤C中存在正整數(shù)k，這就說明正規(guī)棋盤布局并不唯一。結(jié)合本文討論內(nèi)容，需要確保棋盤C上的正規(guī)布局個(gè)數(shù)作為一個(gè)重要參數(shù)存在，并將這個(gè)數(shù)記作。這里假設(shè)有棋盤，它在棋盤4中布置了兩個(gè)棋子，且擁有兩種正規(guī)布局如圖2。

從圖2布局1、2來看，它恰好對應(yīng)的是排列13和排列23，可以見得在棋盤C與正整數(shù)k背景下正規(guī)布局與k個(gè)元素排列在一起并一一對應(yīng)。

1.3 棋陣多項(xiàng)式的表達(dá)方法

棋陣多項(xiàng)式的表達(dá)方法如下：

另外對棋陣多項(xiàng)式的基本性質(zhì)進(jìn)行分析，首先它的第一個(gè)性質(zhì)中有，針對某一個(gè)格子中所布局的棋子來講，它只有布置棋子和不布置棋子兩種可能。如果C1中的某一個(gè)棋子布局到棋盤C2上，增加方案書，則可得出以下公式為[2]：

其中棋盤C可分裂為C3和C4兩部分。

2 棋陣多項(xiàng)式生成算法的傳統(tǒng)計(jì)算方法分析

如上文所述，棋陣多項(xiàng)式生成算法中的傳統(tǒng)計(jì)算方法中包括了多種算法，包括了直接觀察法、分部相乘法、關(guān)鍵點(diǎn)遞歸法等。直接觀察法主要適用于棋盤中較為簡單的算法情況，因?yàn)樗钠甯癯叽缡切∮?*3的;而分部相乘法比較適用于棋盤中的可分離多部分情況展開分析，分離獲得第一種方法并進(jìn)行計(jì)算，同時(shí)采用如下公式：

另外還有關(guān)鍵點(diǎn)遞歸法，它主要選擇了棋盤中的關(guān)鍵點(diǎn)，結(jié)合點(diǎn)將棋盤中的部分內(nèi)容整合，形成，合理選擇關(guān)鍵點(diǎn)，并給出公式如下：

結(jié)合上式分析，可以發(fā)現(xiàn)關(guān)鍵點(diǎn)遞歸法中的算式是沒有普遍性的，而且其適用性表現(xiàn)較差，也不具備太強(qiáng)的技巧性，不容易自動(dòng)生成，無法滿足當(dāng)前的算法實(shí)際需要[3]。

3 棋陣多項(xiàng)式生成算法的創(chuàng)新算法應(yīng)用——組合法

結(jié)合棋陣多項(xiàng)式的基本定義提出以下算式為：

在計(jì)算過程中需要將個(gè)棋子分布于棋盤C上并明確正規(guī)布局個(gè)數(shù)，進(jìn)行棋盤正規(guī)布局定義，保證個(gè)棋子分布于棋盤C的行與列位置上，并滿足條件集合全體構(gòu)成一套完整的方案集，它上面的元素?cái)?shù)量應(yīng)該為。基于此可以分析并生成某一種方案，找到陰影中的橫豎軸坐標(biāo)并曲調(diào)其中所在行列的陰影，然后再尋找下一個(gè)陰影，曲調(diào)行列中的陰影，并以此類推，直到找到第k個(gè)陰影為止。整個(gè)過程中可生成一個(gè)完整的集合方案應(yīng)該如下：

如上反復(fù)執(zhí)行這一集合方案計(jì)算過程，可獲得不同方案，考慮到位有限正整數(shù)，結(jié)合上述有限步進(jìn)行計(jì)算，可證明組合法計(jì)算方法的有效性。結(jié)合棋陣多項(xiàng)式的表達(dá)方法即可求解得出相應(yīng)的新棋陣多項(xiàng)式。新的棋陣多項(xiàng)式組合計(jì)算方法相比于上述傳統(tǒng)計(jì)算方法在適用性方面表現(xiàn)更強(qiáng)，且可同時(shí)依靠計(jì)算機(jī)用遞歸算法滿足優(yōu)化計(jì)算流程，整體看來通俗易懂[4]。

4 棋陣多項(xiàng)式組合計(jì)算方法的算法描述應(yīng)用

4.1 算法描述

第一，在棋陣多項(xiàng)式組合計(jì)算方法中生成算法，需要首先對算法進(jìn)行初始化整合，確保棋盤方針中的棋子數(shù)量為count，臨時(shí)數(shù)組中方案總數(shù)可設(shè)置為temp，且初始值可設(shè)置為0，它的取值一般分為3種情況，其中0表示沒有棋子，1表示有棋子且可計(jì)數(shù)使用，2表示有棋子且不能被計(jì)數(shù)使用。

第二，判斷棋陣多項(xiàng)式組合計(jì)算方法中的count值，如果count值為1，則需要按照行序優(yōu)先原則進(jìn)行方陣掃描檢查，記錄值為1的元素個(gè)數(shù)?？蓪?shù)據(jù)保存在temp中。

第三，按照從頭到尾的順序進(jìn)行方陣Array掃描，找到第一個(gè)值為1的單元元素。

第四，將Array所在行的列元素分別存入到TempRow中，列元素位置為0，且要有效曲調(diào)Array中的所在行列陰影內(nèi)容。

第五，通過count值減1，再利用處理方陣A進(jìn)行遞歸算法應(yīng)用，獲得結(jié)果與temp可相互積累。

第六，恢復(fù)現(xiàn)場，確保TempRow代替原有的Array，確保所在行與列完整。

第七，從Array中繼續(xù)按照行列優(yōu)先順序進(jìn)行掃描排列，找到下一個(gè)值為1的元素，在掃描Array后返回方案總數(shù)temp中[5]。

4.2 禁位排列應(yīng)用

在禁位排列應(yīng)用中可將主動(dòng)禁止的某些元素放到不同位置，通過排列定義了解到n個(gè)元素的具體排列位置，客觀反映不同元素的不同位置，構(gòu)建一個(gè)圍繞n階的方針映射體系，即禁位排列代表了一個(gè)n階方陣的對應(yīng)排列。比如某一個(gè)單位劃分出了5個(gè)工作區(qū)域，其中每個(gè)工作區(qū)域的工作人員不得隨意進(jìn)入其它任何一個(gè)工作區(qū)域，如圖3。

如圖3中，黑色陰影部分即為禁區(qū)，它表示不同區(qū)域的工作人員不得擅自闖入禁區(qū)，結(jié)合這一目標(biāo)可以計(jì)算禁位排列的具體方案數(shù)與排列方案。滿足棋盤大小動(dòng)態(tài)變化，保證在10x10的整形數(shù)組中表示前n行與前n列內(nèi)容[6]。

5 結(jié)語

在組合數(shù)學(xué)中研究棋陣多項(xiàng)式組合算法，探討其禁位排列技術(shù)內(nèi)容是具有一定技術(shù)研究前景的，它能夠基于計(jì)算機(jī)軟件理論基礎(chǔ)深入研究棋陣多項(xiàng)式這一實(shí)用性工具，解決某些禁位排列問題，整體來看通俗易懂且易于推廣。

參考文獻(xiàn)：

[1]牛立新，等.棋陣多項(xiàng)式生成算法及其在禁位排列中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2006，42（10）：91-93+150.

[2]侯政.用圖論解決幾個(gè)特殊的禁位排列問題[J].江西電力職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2015（2）：38-39+48.

[3]壹號元素（廣州）科技有限公司.一種無序排列的寬禁帶半導(dǎo)體納米線的同位素電池：CN201710849974.0[P].2018-03-09.

[4]史嵐，呂建輝.基于禁位排列原理的路由決策算法[J].計(jì)算機(jī)應(yīng)用研究，2014，31（1）：257-260.

[5]姜學(xué)杰.錯(cuò)位排列和禁位排列及其排列數(shù)公式[J].數(shù)學(xué)學(xué)習(xí)與研究，2011（9）：89.

[6]梁作松.車多項(xiàng)式在解決禁位排列問題中的應(yīng)用[J].高等函授學(xué)報(bào)（自然科學(xué)版），2009（3）：55-56.

（責(zé)任編輯：李凌峰）