陳少白，熊麗瓊，張　嫚

(1.武漢科技大學(xué)理學(xué)院，湖北 武漢，430065；2. 武漢科技大學(xué)冶金工業(yè)過程系統(tǒng)科學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室,湖北 武漢,430065)

?

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

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

(1.武漢科技大學(xué)理學(xué)院，湖北 武漢，430065；2. 武漢科技大學(xué)冶金工業(yè)過程系統(tǒng)科學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室,湖北 武漢,430065)

根據(jù)策略之間的兩兩比較結(jié)果，將策略集中的所有策略排出順序是人們?cè)跊Q策時(shí)的一個(gè)基本依據(jù)。本文提出最小全序解的概念，并分別給出偏序策略集、預(yù)序策略集以及任意關(guān)系策略集最小全序解的表示及其生成算法。

策略集；最小全序解；偏序關(guān)系；全序關(guān)系；決策

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

1　最小全序解

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

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

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

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

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

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

二元關(guān)系的全序解有如下四種等價(jià)形式。

定理1對(duì)于X上二元關(guān)系R，以下四項(xiàng)是等價(jià)的：

(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}。

證明：對(duì)于任意T∈T，總有

以及

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

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

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

證畢。

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

2　偏序關(guān)系的全序解

滿足自反性、傳遞性的關(guān)系為預(yù)序關(guān)系，滿足反對(duì)稱性的預(yù)序關(guān)系為偏序關(guān)系，如果R∪Rc∪I=X×X，稱R是完全的。如果S是X上偏序關(guān)系，R?S，稱S是關(guān)系R的保序擴(kuò)展；如果S還是X上全序關(guān)系，稱S是R的全序擴(kuò)展。

定理3設(shè)R是X上預(yù)序關(guān)系，(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)的逆關(guān)系；“°”表示二元關(guān)系的復(fù)合關(guān)系。

證明：(1)R是X上自反的關(guān)系，有(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，根據(jù)R的傳遞性得(y0,x0)∈R，與條件(x0,y0)?Rc不合，所以R(x0,y0)°R(x0,y0)=?。

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

定理4設(shè)R是X上預(yù)(偏)序關(guān)系，如果(x0,y0)?Rc，則R+是X上預(yù)(偏)序關(guān)系。

證明：設(shè)R是X上預(yù)(偏)序關(guān)系，因R?R+，所以R+是自反的。根據(jù)定理3，

=R∩Rc

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

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

如果(x0,y0)?Rc，當(dāng)(x0,y0)∈R時(shí)，R+=R，R+沒有增加任何有序?qū)?，?dāng)(x0,y0)?R時(shí)，相對(duì)R而言，R+至少增加一個(gè)有序?qū)?x0,y0)。如果R是X上偏序關(guān)系，則R+是R的保序擴(kuò)展。

定理5集合X上偏序關(guān)系R經(jīng)過有限次保序擴(kuò)展后必為全序關(guān)系；每一個(gè)包含偏序關(guān)系R的全序關(guān)系，總可以由該類保序擴(kuò)展得到。

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

推論1R是X上偏序關(guān)系，則

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

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

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

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

步驟1如果R∪Rc=X×X，結(jié)束；否則轉(zhuǎn)步驟2。

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

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

即對(duì)應(yīng)的3個(gè)排序分別為：1,3,2,4；1,2,3,4；1,2,4,3。

3　預(yù)序關(guān)系的全序解

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

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

證明：(R-Rc)∪I顯然滿足自反性與反對(duì)稱性。對(duì)于(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上等價(jià)關(guān)系。

定理7設(shè)R是X上預(yù)序關(guān)系，則T(R)={T∈T∶R-Rc?T}。

證明：由于

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

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

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

4　一般二元關(guān)系的全序解

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

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

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

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

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

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

定理10二元關(guān)系R有唯一全序擴(kuò)展的充分必要條件是：R為無(wú)圈、完全的關(guān)系。當(dāng)條件成立時(shí)，R的唯一全序擴(kuò)展為rt(R)。

對(duì)于任意T∈T，S=R-T總是R的一個(gè)破圈，事實(shí)上，S?R，而R-S=R∩T是無(wú)圈的。

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

證明：設(shè)R是X上二元關(guān)系，S0為R的一個(gè)最小破圈，T0為R-S0的全序擴(kuò)展。對(duì)于任意T∈T，令S=R-T，則S?R且R-S=R∩T無(wú)圈，S為R的一個(gè)破圈，于是|S0|≤|S|。由于|R|=|R-S|+|S|=|R-S0|+|S0|，得|R-S|≤|R-S0|。又因?yàn)镽-S0?T0，有R-S0?R∩T0，得|R∩T|≤|R∩T0|，所以T0∈T(R)。

設(shè)T0∈T(R)，令S0=R-T0，則S0?R，且R-S0=R∩T0，即S0為R的一個(gè)破圈。對(duì)于R的任意一個(gè)破圈S，由于R-S無(wú)圈，有全序擴(kuò)展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的一個(gè)最小破圈。證畢。

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

步驟1計(jì)算出所有簡(jiǎn)單圈O1,O2,…,Om；

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

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

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

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

解：計(jì)算出所有的簡(jiǎn)單圈：

確定最小破圈邊集合：

可得：

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

5　結(jié)語(yǔ)

人們?cè)跊Q策前會(huì)進(jìn)行策略之間的比較，這種比較出來的策略集關(guān)系是一個(gè)二元關(guān)系。在對(duì)策略進(jìn)行排序時(shí)，合理的選擇是：將關(guān)系集中最接近的全序關(guān)系作為策略集的排序，這種全序關(guān)系不唯一，形成了一個(gè)最小全序解集合。本文給出最小全序解的表示及其生成算法，可用于指導(dǎo)決策。

[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.

[責(zé)任編輯尚晶]

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

湖北省自然科學(xué)基金資助項(xiàng)目(2013CFA131).

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

O225

A

1674-3644(2016)04-0317-04