一個狀態(tài)控制問題的數(shù)學(xué)建模與求解

胡英武

(金華職業(yè)技術(shù)學(xué)院,浙江金華 321017)

一個狀態(tài)控制問題的數(shù)學(xué)建模與求解

胡英武

(金華職業(yè)技術(shù)學(xué)院,浙江金華 321017)

對互聯(lián)網(wǎng)上的一個數(shù)學(xué)游戲的控制問題,進行了一般性推廣,運用數(shù)學(xué)建模的方法給出了其基于有限域上的線性方程組的數(shù)學(xué)模型及求解.

有限域;狀態(tài)向量;初始控制矩陣;復(fù)合變換;復(fù)合控制矩陣;最終效果矩陣

考慮互聯(lián)網(wǎng)上的一個關(guān)燈游戲[1]：給定一個5×5方格的棋盤,每個方格有白色和黑色兩種狀態(tài),當(dāng)用鼠標(biāo)點擊其中任何一個方格時,則使這個方格自身及與之相鄰的上下左右四個方格都改變狀態(tài)(即原來是白色的則變成黑色,原來是黑色的則變成白色).對于處于棋盤邊緣的16個方格,它們的這四個鄰居可能不全存在,那么只考慮存在的方格.

假定棋盤的初始狀態(tài)為所有方格全部為白色,問是否可以通過點擊方格將棋盤的所有方格全部變?yōu)楹谏?若可以,如何進行游戲,使點擊鼠標(biāo)的次數(shù)盡可能少(稱為最優(yōu)策略).

文[1]用抽象代數(shù)的變換理論建立了該游戲的數(shù)學(xué)模型.

1 問題的提出

本文利用有限域上的線性空間理論討論m×n方格的棋盤問題,研究了棋盤從任一初始狀態(tài)S0能否通過點擊方格變?yōu)榻K止?fàn)顟B(tài)S1的操作可行性判定方法,以及操作可行時的具體操作(最優(yōu)策略),較全面地解決了該問題.

2 模型的建立

定義1 若aij∈{0,1},則稱矩陣Am×n=(aij)為m×n的二進制矩陣[2].特別地,1×n階的二進制矩陣稱為n維二進制向量.

若用0代表白色,1代表黑色,令l=mn,并將m×n棋盤的所有方格按從左到右,從上到下依次編號為1,2,…,l,則棋盤的任一狀態(tài)對應(yīng)與一個l維二進制向量S=(s1,s2,…,si,…sl),si∈{0,1}, i=1,2,…,l,稱此向量S為棋盤的狀態(tài)向量.

定義2 稱l維二進制向量Li=(ai1,ai2,…,ail)(i=1,2,…l),為點擊方格i對棋盤的控制作用(簡稱初始控制向量),其中aij=1,表示點擊方格i能控制方格j;aij=0,表示點擊方格i不能控制方格j(j=1,2,…,l).

稱由初始控制向量Li為行向量構(gòu)成的二進制矩陣A為初始控制矩陣.

定義3 設(shè)F2={0,1},F2上定義四則運算,其運算法則如下:

顯然,F2={0,1}對于上述運算構(gòu)成一個域(稱此域為二元有限域).

定義4 設(shè)V1=(b1,b2,…,bl),V2=(c1,c2,…,cl)是兩個l維二進制向量,定義

稱此運算為l維二進制向量加法.k∈F2,定義

稱此運算為l維二進制向量數(shù)乘.

顯然,對于這樣定義的l維二進制向量的加法與數(shù)乘,有

定理1[3]設(shè)V是所有l(wèi)維二進制向量組成的集合,F2={0,1},則對于l維二進制向量加法與數(shù)乘,V是數(shù)域F2上的向量空間.稱向量空間V為l維二進制向量空間.

定義5 設(shè)β,αi∈V(i=1,2,…,r),若存在xi∈F2(i=1,2,…,r),使β=x1·α1+x2·α2+…+xr·αr,則稱β是α1,α2,…,αr二進制線性組合(簡稱線性組合).

到此,我們給出問題的數(shù)學(xué)模型如下:

已知m×n方格棋盤的初始狀態(tài)向量S0,終止?fàn)顟B(tài)向量S1和初始控制矩陣A,問

1)通過操作點擊方格能否將初始狀態(tài)向量S0變成終止?fàn)顟B(tài)向量S1,即給出可行性判別方法;

2)操作可行時如何具體操作,即給出算法.

3 模型的求解

定義6 將二進制矩陣的第i行加到(按l維二進制向量加法)第j行去,稱這種變換為二進制矩陣的復(fù)合變換[4].將初始控制矩陣A的第i行加到第j行的復(fù)合變換記為Lj+Li,初始控制矩陣A經(jīng)過一系列復(fù)合變換得到的矩陣稱為復(fù)合控制矩陣.

若復(fù)合控制矩陣的某個行向量是復(fù)合變換(Lj+Lk+Li)+Li的結(jié)果,由運算“+,⊕”有(Lj+Lk+Li) +Li=Lj+Lk,即點擊方格i兩次或偶數(shù)次,此操作的作用將取消,為使點擊方格次數(shù)盡可能少,這種重復(fù)操作應(yīng)避免.于是排除上述情況后的復(fù)合控制矩陣的行向量表示若干個方格(各點擊一次)對棋盤的復(fù)合控制效果.

定理2 設(shè)α1,α2,…,αr是r個線性無關(guān)的l維二進制向量,則由α1,α2,…,αr生成的子空間V(α1,α2,…,αr)總共含有2r個不同的向量.

證因為α1,α2,…,αr的所有線性組合都可以表示為

每個線性組合與其坐標(biāo)(x1,x2,…,xr)一一對應(yīng),所以,由α1,α2,…,αr生成的子空間V(α1,α2,…,αr)總共含有2r個不同的向量.

推論如果初始控制矩陣A的秩為r,則

1)通過操作點擊方格總共可以使棋盤達到2r種不同的狀態(tài),反之亦然;

證因為R(A)=r,所以存在矩陣A的r個行向量構(gòu)成它的行向量組的極大無關(guān)組.設(shè)Lk1,Lk2,…,Lkr是矩陣A的行向量組的一個極大無關(guān)組,顯然Lk1,Lk2,…,Lkr的線性組合

與點擊方格的操作效果一一對應(yīng),即生成子空間V(Lk1,Lk2,…,Lkr)中的向量與點擊方格的操作效果一一對應(yīng).所以1)得證.又因m×n的棋盤共有2l種狀態(tài),2)得證.

注 推論說明,棋盤所能達到的狀態(tài)由初始控制矩陣A的秩唯一決定.

定理3 設(shè)m×n棋盤的初始狀態(tài)向量S0,終止?fàn)顟B(tài)向量S1,初始控制矩陣A的秩為r,Lk1,Lk2,…,Lkr是矩陣A的行向量組的一個極大無關(guān)組,則游戲可從初始狀態(tài)S0變到終止?fàn)顟B(tài)S1的充分必要條件為：存在xi∈F2(i=1,2,…,r),使

證1)對于棋盤的某一狀態(tài)Si,在點擊第k個方格后,轉(zhuǎn)移到另一種狀態(tài)Sj這一過程可以用狀態(tài)向量和初始控制向量之和表示為Sj=Si+Lk,反之亦然.

2)從初始狀態(tài)S0變到終止?fàn)顟B(tài)S1,等價于從初始狀態(tài)S0出發(fā)點擊某幾個方格各一次可變到終止?fàn)顟B(tài)S1.又因為點擊方格的初始控制向量L1,L2,…,Ll都是Lk1,Lk2,…,Lkr的線性組合,綜合1),2)即得到定理3的證明.

顯然,由于復(fù)合控制矩陣的行向量都是某幾個初始控制向量相加得到,所以經(jīng)過復(fù)合變換后新舊矩陣所能達到的總效果不變.

定義7 若二進制矩陣B是二進制矩陣C經(jīng)一系列復(fù)合變換后得到的,則稱矩陣B與C的控制效果等價(簡稱矩陣B,C等價),記為B∽C.

顯然,關(guān)系“∽”為等價關(guān)系,復(fù)合變換是一種等價變換.

定理4[3]若B,C都是二進制矩陣,則

1)如果B∽C,則R(B)=R(C)(即復(fù)合變換不改變矩陣的秩);

2)如果B∽C,則B,C的行向量組的極大無關(guān)組等價(即可以相互表出).(證明略)

定義8 如果矩陣M的非零行的第1個不為0(為1)的元素所在列的其余元素均為0,零行全部位于矩陣M的下部,則稱該矩陣為最簡階梯型矩陣.

定理5[3]若二進制矩陣N的秩為r,則必可經(jīng)過一系列復(fù)合變換將矩陣N變成僅有r個非零行向量的最簡階梯型矩陣.稱由初始控制陣A經(jīng)過一系列復(fù)合變換得到的最簡階梯型矩陣Q為A的最終效果矩陣.(證明略)

定理6 設(shè)初始控制陣A的秩為r,Q是初始控制陣A的最終效果矩陣,S0,S1分別為游戲的初始狀態(tài)向量和終止?fàn)顟B(tài)向量,Q1,Q2,…,Qr是最終效果矩陣Q的非零行向量,則游戲可從初始狀態(tài)S0變到終止?fàn)顟B(tài)S1的充分必要條件為存在xi∈F2(i=1,2,…,r),使

證由定理4和定理5知,Q1,Q2,…,Qr與矩陣A的行向量組的一個極大無關(guān)組等價.再由定理3就得到定理6的證明.

又根據(jù)“+,⊕”的性質(zhì),可將定理6中的S1=S0+x1·Q1+x2·Q2+…+xr·Qr改為

下面我們給出原問題的可行性判別與求解方法.

1)通過一系列復(fù)合變換將初始控制陣A變?yōu)樽罱K效果陣Q,于是得到最終效果陣Q的r個非零行向量Q1,Q2,…,Qr;

2)令S0+S1=x1·Q1+x2·Q2+…+xr·Qr.若此組合式有解,則棋盤能從初始狀態(tài)S0變成終止?fàn)顟B(tài)S1;否則,棋盤不能從初始狀態(tài)S0變成終止?fàn)顟B(tài)S1;

3)如果棋盤能從初始狀態(tài)S0變成終止?fàn)顟B(tài)S1,則根據(jù)2)的解中等于1的xi所對應(yīng)的Qi即可得到將初始狀態(tài)S0變成終止?fàn)顟B(tài)S1的點擊操作方法.

4 模型檢驗

實例,考慮3×5的棋盤,其初始控制陣為

棋盤的初始狀態(tài)為(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),問:

通過點擊方格能否達到終止?fàn)顟B(tài)(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)與(1,1,1,1,1,1,1,1,1,1,1, 1,0,1,1);

若能達到終止?fàn)顟B(tài),如何點擊方格.

解 對初始控制陣A施行一系列復(fù)合變換后得最終效果陣Q,

由于R(A)=R(Q)=12＜15,所以,點擊方格只能達到棋盤所有可能狀態(tài)215種中的212種,即所有可能狀態(tài)中的

因而,從初始狀態(tài)S0,能達到終止?fàn)顟B(tài)S1.

由矩陣Q的前12行,可知只需點擊第2,9,10,11,14,15方格各一次就可將初始狀態(tài)S0,變成終止?fàn)顟B(tài)S1.

注 若由A到Q的變換方法不唯一,則可能產(chǎn)生不同的方法,但最少點擊方格次數(shù)相同.如點擊第1,3,7,10,11,13方格各一次也可將初始狀態(tài)S0,變成終止?fàn)顟B(tài)S1.

對于終止?fàn)顟B(tài)S1=(1,1,1,1,1,1,1,1,1,1,1,1,0,1,1),因為S0+S1=S1,所以令

此式無解,因而,從初始狀態(tài)S0不能達到終止?fàn)顟B(tài)S1.

5 模型評價

我們首先定義了二元域上的二進制向量空間,然后將此游戲轉(zhuǎn)化成一個二元域上的線性方程組的解的存在性問題,這個線性方程組是定義在二元域F2上,不是我們所熟知的定義在R上的線性方程組.所幸的是,F2上的線性方程組解的存在性理論[3]以及求解方法[5]完全和R上的線性方程組一樣,甚至求解過程還要簡單,因為F2遠(yuǎn)比R簡單.

[1] 周昊.“關(guān)燈”游戲中的代數(shù)學(xué)[J].數(shù)學(xué)的實踐與認(rèn)識,2007,37(11)：132-140.

[2] 程德文,張建濤.一個游戲難題的數(shù)學(xué)建模與求解[J].數(shù)學(xué)的實踐與認(rèn)識,2005,35(8)：1-4.

[3] 馮克勤.有限域[M].長沙：湖南教育出版社,1998.

[4] 李炯生,查建國.線性代數(shù)[M].合肥：中國科學(xué)技術(shù)大學(xué)出版社,1989.

[5] Hungerford T W.Algebra[M].New York：Springer-Verlag,1974.

The Mathematical Modeling and Solving for a State Control Problem

HU Ying-w u

(Jinhuacollege of Profession and Technology of China,Jinhua,Zhejiang 321017,China)

We conduct the general popularization to the state control of a mathematical game on internet and use the method of mathematical modeling to show the mathematical model of linear equation system based on finite field and its solving.

finite field;state variable;initial control matrix;composite convert;composite control matrix;final effect matrix

O141.4

A

1672-1454(2011)03-0168-05

2008-08-18;[修改日期]2008-12-01

浙江省教育廳科研項目(Y201017888);金華職業(yè)技術(shù)學(xué)院青年教改項目(10QN18)