一個狀態控制問題的數學建模與求解

胡英武

(金華職業技術學院,浙江金華 321017)

一個狀態控制問題的數學建模與求解

胡英武

(金華職業技術學院,浙江金華 321017)

對互聯網上的一個數學游戲的控制問題,進行了一般性推廣,運用數學建模的方法給出了其基于有限域上的線性方程組的數學模型及求解.

有限域;狀態向量;初始控制矩陣;復合變換;復合控制矩陣;最終效果矩陣

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

假定棋盤的初始狀態為所有方格全部為白色,問是否可以通過點擊方格將棋盤的所有方格全部變為黑色.若可以,如何進行游戲,使點擊鼠標的次數盡可能少(稱為最優策略).

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

1 問題的提出

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

2 模型的建立

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

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

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

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

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

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

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

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

稱此運算為l維二進制向量數乘.

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

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

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

到此,我們給出問題的數學模型如下:

已知m×n方格棋盤的初始狀態向量S0,終止狀態向量S1和初始控制矩陣A,問

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

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

3 模型的求解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

顯然,關系“∽”為等價關系,復合變換是一種等價變換.

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

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

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

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

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

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

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

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

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

1)通過一系列復合變換將初始控制陣A變為最終效果陣Q,于是得到最終效果陣Q的r個非零行向量Q1,Q2,…,Qr;

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

3)如果棋盤能從初始狀態S0變成終止狀態S1,則根據2)的解中等于1的xi所對應的Qi即可得到將初始狀態S0變成終止狀態S1的點擊操作方法.

4 模型檢驗

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

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

通過點擊方格能否達到終止狀態(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);

若能達到終止狀態,如何點擊方格.

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

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

因而,從初始狀態S0,能達到終止狀態S1.

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

注 若由A到Q的變換方法不唯一,則可能產生不同的方法,但最少點擊方格次數相同.如點擊第1,3,7,10,11,13方格各一次也可將初始狀態S0,變成終止狀態S1.

對于終止狀態S1=(1,1,1,1,1,1,1,1,1,1,1,1,0,1,1),因為S0+S1=S1,所以令

此式無解,因而,從初始狀態S0不能達到終止狀態S1.

5 模型評價

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

[1] 周昊.“關燈”游戲中的代數學[J].數學的實踐與認識,2007,37(11)：132-140.

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

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

[4] 李炯生,查建國.線性代數[M].合肥：中國科學技術大學出版社,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);金華職業技術學院青年教改項目(10QN18)