有限策略集全序解及其生成算法

陳少白，熊麗瓊，張　嫚

(1.武漢科技大學理學院，湖北 武漢，430065；2. 武漢科技大學冶金工業過程系統科學湖北省重點實驗室,湖北 武漢,430065)

?

有限策略集全序解及其生成算法

陳少白1,2，熊麗瓊1，張嫚1

(1.武漢科技大學理學院，湖北 武漢，430065；2. 武漢科技大學冶金工業過程系統科學湖北省重點實驗室,湖北 武漢,430065)

根據策略之間的兩兩比較結果，將策略集中的所有策略排出順序是人們在決策時的一個基本依據。本文提出最小全序解的概念，并分別給出偏序策略集、預序策略集以及任意關系策略集最小全序解的表示及其生成算法。

策略集；最小全序解；偏序關系；全序關系；決策

決策理論在社會科學、管理科學以及人工智能等研究領域已經得到廣泛應用[1-2]。人們在進行決策時，往往先對策略集X中的策略進行兩兩優劣比較，其結果用二元關系R來表示，從而形成策略集關系。根據比較的結果將所有的策略依優劣程度排出一個合理的次序，這是人們在決策時的一個基本依據，而效用理論、偏好理論以及信念的度量等均與排序相關[3]。舉一個簡單的例子：球隊進行比賽，怎樣合理地用比賽結果形成的勝負關系將球隊排出名次。人們習慣用數值來量化這種優劣關系，于是有兩個基本問題：①找到一個函數f，使得當(x,y)∈R時，有f(x)≥f(y)成立；②這種函數在何種意義下唯一，如何將它確定出來。由于在做決策時不在乎策略對應的數值大小，只需對各種策略排出優劣次序，即對于單射f:X→(-∞,+∞)，確定一個二元關系T：T={(x,y)∈X×X|f(x)≥f(y)}，T具有自反性、傳遞性和完全性。于是問題轉變成：①找到X上的全序關系T，使得當(x,y)∈R時，總有(x,y)∈T成立；②在何種意義下這種全序關系是唯一的，求出全體這樣的全序關系。針對上述問題，本文提出最小全序解概念，并分別給出偏序策略集、預序策略集以及任意關系策略集最小全序解的表示及其生成算法。

1　最小全序解

以下X表示n個元素的有限集合，T是X上全序關系的全體，A′=X-A是A的補集，Rc是二元關系R的逆關系，I={(x,x)∶x∈X}是恒等關系。

定義1設R是X上二元關系，如果有T∈T，使得R?T，稱R可以全序表示，T是R的一個全序表示。

X上二元關系R與S的距離用對稱差ρ(R,S)=|R-S|+|S-R|來度量，其中|·|表示集合中元素的個數。

對于任意關系，不一定有全序表示，以距離二元關系R最近的全序關系作為二元關系R的最佳排序。

定義2對于集合X上二元關系R，距離R最近的全序關系全體記為T(R)，即

稱T(R)中元素為二元關系R的最小全序解，簡稱全序解，其中，argmin表示使得ρ(R,T)達到最小的全序關系T的集合。

二元關系的全序解有如下四種等價形式。

定理1對于X上二元關系R，以下四項是等價的：

(1)T(R)=argmin{|R-T|+|T-R|∶T∈T}；

(2)T(R)=argmin{|R-T|∶T∈T}；

(3)T(R)=argmin{|T-R|∶T∈T}；

(4)T(R)=argmax{|R∩T|∶T∈T}。

證明：對于任意T∈T，總有

以及

定理2如果二元關系R可以全序表示，則T(R)={T∈T∶R?T}。

證明：如果關系R可全序表示，則存在T0∈T，使得R?T0。對于T∈T(R)，由于|R∩T|≥|R∩T0|=|R|，得R?T，即

對于T∈T，R?T，由|R∩T|=|R|≥max{|R∩T|∶T∈T}，得T∈T(R)，即

證畢。

以下分別確定偏序關系、預序關系以及任意二元關系R的全序解T(R)，并給出其全序解的生成算法。

2　偏序關系的全序解

滿足自反性、傳遞性的關系為預序關系，滿足反對稱性的預序關系為偏序關系，如果R∪Rc∪I=X×X，稱R是完全的。如果S是X上偏序關系，R?S，稱S是關系R的保序擴展；如果S還是X上全序關系，稱S是R的全序擴展。

定理3設R是X上預序關系，(x0,y0)?Rc，記R+=R∪R(x0,y0)，其中R(x0,y0)={(x,y)∶(x,x0),(y0,y)∈R}，則

(1)R(x0,y0)≠?，

(2)R∩Rc(x0,y0)=Rc(x0,y0)∩R(x0,y0)=?，

(3)R(x0,y0)°R(x0,y0)=?，

(4)R°R(x0,y0)=R(x0,y0)°R=R(x0,y0)。

其中：Rc(x0,y0)表示R(x0,y0)的逆關系；“°”表示二元關系的復合關系。

證明：(1)R是X上自反的關系，有(x0,y0)∈R(x0,y0)，所以R(x0,y0)≠?。

(2)如果(x,y)∈R∩Rc(x0,y0)，即(x,y)∈R，(y,x0),(y0,x)∈R，由R的傳遞性得(y0,x0)∈R，與條件(x0,y0)?Rc不合，所以R∩Rc(x0,y0)=?；

如果(x,y)∈Rc(x0,y0)∩R(x0,y0)，即(y,x0),(y0,x)∈R，(x,x0),(y0,y)∈R，由R的傳遞性得(y0,x0)∈R，與條件(x0,y0)?Rc不合，所以Rc(x0,y0)∩R(x0,y0)=?。

(3)如果(x,y)∈R(x0,y0)°R(x0,y0)，即存在z∈X，使得(x,x0),(y0,z)∈R、(z,x0),(y0,y)∈R，根據R的傳遞性得(y0,x0)∈R，與條件(x0,y0)?Rc不合，所以R(x0,y0)°R(x0,y0)=?。

(4)根據R的傳遞性，顯然有R°R(x0,y0)=R(x0,y0)°R=R(x0,y0)。證畢。

定理4設R是X上預(偏)序關系，如果(x0,y0)?Rc，則R+是X上預(偏)序關系。

證明：設R是X上預(偏)序關系，因R?R+，所以R+是自反的。根據定理3，

=R∩Rc

所以R+與R具有相同的反對稱性。由于

所以R+具有傳遞性，即：R+是X上預(偏)序關系。證畢。

如果(x0,y0)?Rc，當(x0,y0)∈R時，R+=R，R+沒有增加任何有序對，當(x0,y0)?R時，相對R而言，R+至少增加一個有序對(x0,y0)。如果R是X上偏序關系，則R+是R的保序擴展。

定理5集合X上偏序關系R經過有限次保序擴展后必為全序關系；每一個包含偏序關系R的全序關系，總可以由該類保序擴展得到。

證明：R是X上偏序關系，如果R∪Rc=X×X，即R是完全的，則R是X上全序關系；如果R∪Rc≠X×X，則將R保序擴展成R+，直至R∪Rc=X×X，所以偏序關系R經過有限次保序擴展最終成為全序關系。對于任意R?T的全序關系T，如果(R∪Rc)′≠?，選(x0,y0)∈T∩(R∪Rc)′，則R+?T，T包含由偏序關系R經過有限次擴展而成的全序關系，所以T是R的一個保序擴展。證畢。

推論1R是X上偏序關系，則

T(R)={T∈T∶R?T}，

其中T(R)為二元關系R的全序解集合。

推論2對于X上任意二元關系R，總有:T(R+)?T(R)。

以下給出偏序關系R的全序解T(R)的生成算法：

步驟1如果R∪Rc=X×X，結束；否則轉步驟2。

步驟2取(x,y)∈X×X-R∪Rc，得到R的兩個擴展R1=R∪R(x,y)與R2=R∪R(y,x)，分別轉步驟1。

例1對于集合X={1,2,3,4}，其偏序關系R={(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(4,4),(3,3)}，求它的全部全序解。

即對應的3個排序分別為：1,3,2,4；1,2,3,4；1,2,4,3。

3　預序關系的全序解

設R是X上預序關系，I={(x,x)∶x∈X}是恒等關系，將預序關系R分解成：R=(R-Rc)∪(R∩Rc)，則有以下結論。

定理6如果R是X上預序關系，則(R-Rc)∪I是X上偏序關系。

證明：(R-Rc)∪I顯然滿足自反性與反對稱性。對于(x,y),(y,z)∈R-Rc，由R的傳遞性有(x,z)∈R，如果(z,x)∈R，則由(y,z)∈R-Rc，得(y,x)∈R，與(x,y)∈R-Rc矛盾，所以(x,z)∈R-Rc。證畢。

顯然，R∩Rc是X上等價關系。

定理7設R是X上預序關系，則T(R)={T∈T∶R-Rc?T}。

證明：由于

|R∩T|=|(R-Rc)∩T|+|(R∩Rc)∩T|

所以|R∩T|達最大，當且僅當|(R-Rc)∩T|達最大，即T(R)=T(R-Rc)，又(R-Rc)∪I是一個偏序關系，所以T(R)={T∈T∶R-Rc?T}。證畢。

由于T(R)=T(R-Rc)，可依照偏序關系的全序解生成算法計算T(R-Rc)。

4　一般二元關系的全序解

對于序列x1,x2,…,xr，r>1，如果x1≠xr，稱{(x1,x2),(x2,x3),…,(xr,x1)}為圈；如果x1,x2,…,xr兩兩不同，則稱為簡單圈，{(x,x)}稱為自圈。顯然，圈至少包含一個簡單圈。

定理8關系R的傳遞閉包t(R)有圈當且僅當R有圈。

于是有正整數m1,m1,…,mr，分別使得(xi,xi+1)∈Rmi，i=1,2,…,r，所以R有圈。證畢。

推論3設R是X上二元關系，自反、傳遞閉包rt(R)是偏序關系的充分必要條件是R無圈。

定理9若R是X上無圈二元關系，則T(R)=T(rt(R))={T∈T∶rt(R)?T}。

證明：如果R是X上無圈二元關系，對于全序關系T，R?T當且僅當rt(R)?T。又自反、傳遞閉包rt(R)是偏序關系，所以T(R)={T∈T∶rt(R)?T}。證畢。

定理10二元關系R有唯一全序擴展的充分必要條件是：R為無圈、完全的關系。當條件成立時，R的唯一全序擴展為rt(R)。

對于任意T∈T，S=R-T總是R的一個破圈，事實上，S?R，而R-S=R∩T是無圈的。

定理11設R是X上二元關系，如果S為R的一個最小破圈，則R-S的全序擴展T∈T(R)；如果T∈T(R)，則R-T為R的一個最小破圈，即T(R)={T∈T∶R-S?T,S∈S},其中，S為R的一個最小破圈全體。

證明：設R是X上二元關系，S0為R的一個最小破圈，T0為R-S0的全序擴展。對于任意T∈T，令S=R-T，則S?R且R-S=R∩T無圈，S為R的一個破圈，于是|S0|≤|S|。由于|R|=|R-S|+|S|=|R-S0|+|S0|，得|R-S|≤|R-S0|。又因為R-S0?T0，有R-S0?R∩T0，得|R∩T|≤|R∩T0|，所以T0∈T(R)。

設T0∈T(R)，令S0=R-T0，則S0?R，且R-S0=R∩T0，即S0為R的一個破圈。對于R的任意一個破圈S，由于R-S無圈，有全序擴展T∈T，使得R-S?T，得R-T?S，注意到R=(R-T)∪(R∩T)=(R-T0)∪(R∩T0)以及|R∩T|≤|R∩T0|，得|S0|=|R-T0|≤|R-T|≤|S|，所以S0=R-T0為R的一個最小破圈。證畢。

以下給出任意關系全序解T(R)的生成算法：

步驟1計算出所有簡單圈O1,O2,…,Om；

步驟2從每個簡單圈中選一條邊，組成邊集合Lk，k=1,2,…,|O1×O2×…×Om|，求出|Lk|達最小的邊集合Lk，得到最小破圈邊集合；

步驟3求R-Lk的自反、傳遞閉包rt(R-Lk)，它是一個偏序集；

步驟4將rt(R-Lk)全序擴展，得到全序關系。

例2設X={1,2,3,4}，關系R={(1,3),(3,1),(3,2),(1,4),(2,4),(4,2)}，求其全序解。

解：計算出所有的簡單圈：

確定最小破圈邊集合：

可得：

然后通過步驟3和步驟4的運算，最終得到全序解T(R)：3,1,4,2；3,1,2,4；1,3,4,2；1,3,2,4。

5　結語

人們在決策前會進行策略之間的比較，這種比較出來的策略集關系是一個二元關系。在對策略進行排序時，合理的選擇是：將關系集中最接近的全序關系作為策略集的排序，這種全序關系不唯一，形成了一個最小全序解集合。本文給出最小全序解的表示及其生成算法，可用于指導決策。

[1]KatsikopoulosKV,GigerenzerG．One-reasondecision-making：modelingviolationsofexpectedutilitytheory[J].JournalofRiskandUncertainty，2008，37(1)：35-56．

[2]AndreoniJ,SprengerC.Certainanduncertainutility：theAllaisParadoxandfivedecisiontheoryphenomena[Z].Levine’sWorkingPaperArchive，2010：1-20．

[3]WongSKM,YaoYY,BollmannP,etal.Axiomatizationofqualitativebeliefstructures[J].IEEETransactionsonSystems,ManandCybernetics, 1991, 21(4):726-734.

[責任編輯尚晶]

Totalordersolutionofafinitestrategysetanditsgeneratingalgorithm

Chen Shaobai1,2，Xiong Liqiong1，Zhang Man1

(1.CollegeofScience,WuhanUniversityofScienceandTechnology,Wuhan430065,China;2.HubeiProvinceKeyLaboratoryofSystemsScienceinMetallurgicalProcess,WuhanUniversityofScienceandTechnology,Wuhan430065,China)

Allstrategiesinthestrategysetaresortedaccordingtothecomparisonresultsbetweenstrategies,whichisafundamentalbasisforpeopletomakedecision.Thispaperproposestheconceptofminimaltotalordersolution,andprovidestherepresentationsandgeneratingalgorithmsoftheminimaltotalordersolutionsofstrategysetswithpartialorder,pre-orderandarbitraryrelation,respectively.

strategyset;minimaltotalordersolution;partialorderrelation;totalorderrelation;decisionmaking

2016-01-25

湖北省自然科學基金資助項目(2013CFA131).

陳少白(1957-)，男，武漢科技大學教授，博士.E-mail:chenshaobai71@163.com

O225

A

1674-3644(2016)04-0317-04