棋陣多項式生成算法及其在禁位排列中的應用研究

孫靜

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

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

中圖分類號：TP301.6 文獻標識碼：A 文章編號：2095-9052（2020）03-0188-02

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

1 棋陣多項式生成算法的基本理論

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

1.1 棋盤的基本概念

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

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

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

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

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

1.3 棋陣多項式的表達方法

棋陣多項式的表達方法如下：

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

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

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

如上文所述，棋陣多項式生成算法中的傳統(tǒng)計算方法中包括了多種算法，包括了直接觀察法、分部相乘法、關(guān)鍵點遞歸法等。直接觀察法主要適用于棋盤中較為簡單的算法情況，因為它的棋格尺寸是小于3*3的;而分部相乘法比較適用于棋盤中的可分離多部分情況展開分析，分離獲得第一種方法并進行計算，同時采用如下公式：

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

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

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

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

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

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

4 棋陣多項式組合計算方法的算法描述應用

4.1 算法描述

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

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

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

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

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

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

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

4.2 禁位排列應用

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

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

5 結(jié)語

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

參考文獻：

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

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

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

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

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

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

（責任編輯：李凌峰）