孫靜

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

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

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

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

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

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

1.1 棋盤(pán)的基本概念

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

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

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

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

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

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

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

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

其中棋盤(pán)C可分裂為C3和C4兩部分。

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

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

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

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

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

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

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

如上反復(fù)執(zhí)行這一集合方案計(jì)算過(guò)程，可獲得不同方案，考慮到位有限正整數(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ī)用遞歸算法滿(mǎn)足優(yōu)化計(jì)算流程，整體看來(lái)通俗易懂[4]。

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

4.1 算法描述

第一，在棋陣多項(xiàng)式組合計(jì)算方法中生成算法，需要首先對(duì)算法進(jìn)行初始化整合，確保棋盤(pán)方針中的棋子數(shù)量為count，臨時(shí)數(shù)組中方案總數(shù)可設(shè)置為temp，且初始值可設(shè)置為0，它的取值一般分為3種情況，其中0表示沒(méi)有棋子，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)容。

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

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

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

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

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

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

5 結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

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

[3]壹號(hào)元素（廣州）科技有限公司.一種無(wú)序排列的寬禁帶半導(dǎo)體納米線(xiàn)的同位素電池：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]梁作松.車(chē)多項(xiàng)式在解決禁位排列問(wèn)題中的應(yīng)用[J].高等函授學(xué)報(bào)（自然科學(xué)版），2009（3）：55-56.

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