商空间读书笔记

商空间合成方法的研究——郎咸吉1.商空间理论提出：商空间理论，张钹和张玲提出，基于复杂问题求解。创新：将不同的粒度世界与数学上的商集概念统一起来。本质：三元组：论域，属性函数，结构来描述问题。目的：研究不同上空间之间的关系及上空间的分解，合成和推理规律。应用：启发式搜索，路径规划等。2.合成方法，研究商空间与原空间之间的关系。3.粒度计算，三部分：粒子，粒层，粒结构。1.粒子：构成粒度计算模型的最基本元素。粒度来描述粒子的大小，反映了粒子的粒化程度。2.粒层：是对粒化所得全部粒子的描述。也是用来描述问题空间。3.粒结构：是一种关系结构，体现的是不同粒层之间的相互关联。4.等价与划分1.等价类集合{[]|}RxxX等价于商集X\R。2.X上的等价关系可以诱导出X的划分，且唯一。X的划分也可以诱导出X上的等价关系。即等价关系和划分可以相互诱导。3.[()]xRyBBxRyR4.R1,R2为等价关系，则12RR和12()RR也是等价关系5.R为R的传递闭包，R为等价关系，则R也是等价关系。5.拓扑1.定义：设X是一个集合，T是X上的一个子集族。如果T满足如下条件：(1)X,∅∈T；(2)若A,B∈T，则ABT；(3)若,LlATTTT;则称T是X的一个拓扑。偶对(X,T)是一个拓扑空间。或者称集合X是一个相对与拓扑T而言的拓扑空间。2.平庸拓扑：只含空集和集合本身的拓扑：{∅，X}离散拓扑：包含集合所有子集的拓扑3.拓扑的比较：只有存在包含关系的时候才能比较两个拓扑，若21TT,则称T2细于T1（T1粗于T2）.若21TT是真包含关系，则称T2严格细于T1（T1严格粗于T2）。4.拓扑的交运算1）设T1和T2是集合X上的两个拓扑，12TT也是集合X上的拓扑。2）12TT是粗于T1和T2的最细拓扑。4.基设（X,T）是一个拓扑空间，B是T的一个子族。如果T中的每个元素（即拓扑空间X中的每一个开集）是B中的某些元素的并。对于每一个AT，存在1BB使得1BBAB,则称B是拓扑T的一个基。一个基只能生成一个拓扑，而拓扑可以有很多不同的基。6.商空间理论商空间单纯从等价或者划分的角度来讲，就是对一个集合和其某个划分建立的一种对应关系。{1,2}{3,4,5}{6}{7}1234567问题求解理论及应用——张玲，张钹一.粒度模型1.问题描述——三元组(X,f,T)X表示问题的论域。f(.)表示论域的属性。:fXY，对论域中的任意元素，有一个相应的f(x)，表示元素x的某些属性，所以又称为属性函数。T是论域的结构，指的是论域X中个元素的相互关系。图1.1三元组模型的结构图示定义1.1设X是一个集合，R是X上的一个关系，并满足(1)自反性，xRx；(2)对称性，若xRy，则yRx；(3)传递性，若xRy，yRz，则xRz；则称R是X上的一个等价关系，对等价关系R，通常将xRy记为xy。定义1.2xX，令[x]={y|xy}，称[x]是X关于R的商集。故商集是将等价类[x]看成元素而构成的新空间。上述将不同粒度的世界与数学上的商集概念统一起来。商空间理论就是讨论论域，属性，结构在不同粒度下的表示与性质，以及这些表示，性质之间的相互依存，相互转换的关系。不同粒度世界模型：对问题(X,f,T),称从不同粒度（角度，层次）考擦问题(X,f,T)，是指给定X的一个等价关系R，并由R产生商集[X]，然后研究相应问题([X],[f],[T])，XX1X2X3X4X5f1f2f3f2f4f3其中[f]，[T]分别表示商集[X]上对应的商属性函数和商结构。称([X],[f],[T])为(X,f,T)的商空间。所有的不同商集及其对应的商空间，就构成了问题(X,f,T)的不同粒度世界。2.商空间的定义[x]：定义[x]为对应于等价关系R的商集。[T]：设T是拓扑，则定义商拓扑[T]：1[]:{|(),[]},:[]TupuTuXpxX是自然投影。[f]：设属性函数:fXY，定义[]:[]fXY3.不同粒度世界的获得1).对论域进行颗粒化1，结构，功能，例：机器按功能不同划分，国家按行政管辖关系划分。2，按约束划分。3，合成法，利用现有的商空间，对商集X1，X2求交运算，并运算可得新的粒度空间。2).利用属性进行颗粒化对属性取不同的粒度，即对属性的值域进行适当的划分，然后再转换成对论域的划分。1，设:fXY，若f是单值的（即映射），这可利用f来定义划分。一般来讲，若Y的结构比较清楚，可以利用Y的分类（即对属性取不同的粒度）来定义X中的对应的分类：设{}iY是Y的一个划分，定义={x|f(x)}iiXY，则{}iX是X的一个划分。X:考生的集合Y：[0,750]f(x)=分数Y1:[0,420]划分X1:上不了学={x|f(x)}iiXY图1.2利用属性进行划分示例2，投影划分，按属性划分的几何描述，或者，“取部分约束法”定义：设元素x的属性函数是多维的，如有n个属性函数分量f1,f2,f3,…,fn。若暂不考虑其中i个属性f1,f2,…,fi，将fi+1,fi+2,…,fn属性相同的归为一类，则称为投影分类法。3).结构的颗粒化定义1.3给定(,,)XfT及T1，且1TT。设在X上定义等价关系R：()xRyux，有()yux且(),()uyxuy，其中u(x)是x在T1中的开邻域。这样的通过结构的粗颗粒化，也能得到粗粒度的商空间。这样的空间一般未必能从论域或属性的颗粒化中得到。文中举例：将元素之间的关系由多种合并到少量。这样就构成了新的结构。4.多粒度世界的关系1).结构是X上一切等价关系的全体。定义1.4设1212,,,,RRxyXxRyxRy，则称R1比R2细，记为21RR个人理解：越细表示包含的信息越多。命题1.1在上面定义的关系下形成一个完备半序格。（有上下确界）显然，当12RR时，1[]RX是2[]RX的商集。命题说明，在给定论域X后，其全体商集安包含关系构成一个完备半序格，这样就可以自由的在这个格上求上下确界运算。2).完备性上述定理可以扩展到商空间上，即：给定拓扑空间(,,)XfT，是X上一切等价关系的集合。定义1.4设1212,,,,RRxyXxRyxRy，则称R1比R2细，记为21RR个人理解：越细表示包含的信息越多。命题1.1在上面定义的关系下形成一个完备半序格。（有上下确界）5.性质的保持性1).结构与商结构分析1.(,,)XfT是拓扑空间定义1.5：设X是一个集合，T是X上的一个子集族。如果T满足如下条件：(1)X,∅∈T；(2)若A,B∈T，则ABT；(3)若,LlATTTT;则称T是X的一个拓扑。偶对(X,T)是一个拓扑空间。或者称集合X是一个相对与拓扑T而言的拓扑空间。A是开集AT例1.1令={a,b,c,d},T={,{a,b,c},{c,d},{c},{a,b,c,d}}X，则T是X上的一个拓扑。证明：TT{a,b,c}{c,d}={a,b,c,d}=XT{a,b,c}{c,d}={c}T{a,b,c}{}{,,}T{a,b,c}{}{}Tcabccc{a,b,c}{,,}T{a,b,c}TXabcXX{c,d}{}{,}T{c,d}{}{}Tccdcc{c,d}T{c,d}{,}TXXXcd{c}{}T{c}TXcXX及T中所有的开集的并和交都在T中，即对开集的并和交运算是封闭的。需要指出的是X上的拓扑不唯一。定义1.6设(,)XT是一个拓扑空间，B是X中的一个集族，若满足(1),uBuT(2),T，则存在B的子集1BB，使得1aauBu则称B是(,,)XfT的一个基。(1)说明B由开集组成，条件(2)说明X中的任意开集都能由B中集合的并表示。对于论域X，当其基确定之后，则其对应的拓扑也就唯一的确定了。但是一个拓扑却有不同的基。例1.2，得到商拓扑。{1,2,3,4,5}X{,,{2,3},{4,5},{1,2,3},{2,3,4,5}}TX显然T是X上的一个拓扑。现有X上的等价关系R:123{1,2},{3},{4,5}aaa这可由下得到商拓扑1123123,{,}{1,2,3},{},{,,},aTaaTaTaaaXTT故312123[]{,{},{,},{,,}}{,{4,5},{1,2,3},}TaaaaaaX2.(,)XT是半序空间设(,)XT是半序空间，即在X的部分元素上建立如下的关系，满足(1),,xyyxxy(2),,xyyzxz(不满足(1)，则称为拟半序空间。)我们要希望在[X]的商拓扑[T]上也引入半序关系。步骤1），将(,)XT转化为某种拓扑。2），再引入商拓扑空间([],[])XT。3），由([],[])XT导出相应的半序关系。定义1.7设(,)XT是半序集，xX，定义集合(){|,}uxyxyyX这样，令{()|}BuxxX，称以B为拓扑基的拓扑rT为X的右序拓扑，记为(,)rXT。这样就将一个半序集变为相对应的拓扑空间。定义1.8设(,)XT是一个拓扑空间，用T定义如下的“”关系。对,,(),xyXxyux有yu(x)，其中u(x)是x的开邻域，在X上得到的“”关系，对应的结构记为sT，称它由拓扑T诱导的（拟）半序。定义1.9设(,)XT是拓扑空间，由上面定义的“”关系满足,xyyxxy，则称拓扑T与“”相容的。若拓扑T与“”相容的，则是半序，且X在“”关系下构成一个半序集，记为(,)SXT，它是拓扑(,)XT对应的半序集。设商拓扑空间([],[])rXT中的[]rT与“”关系是相容的，简称R是相容的，则([],[])rSXT在“”关系下是半序集。2).保假（真）原理定理1（保假原理，falsitypreserving）若问题[][]AB在([],[],[])XfT上无解，则问题AB在(,,)XfT上一定也无解。或者描述为：问题AB在(,,)XfT上有解，则问题[][]AB在([],[],[])XfT上一定有解。定理2.1（保真原理I）问题[][]AB在([],[],[])XfT上有解，而且对于任意[x]，1([])px在X上是联通集，则问题AB在(,,)XfT上一定也有解。定理2.2（保真原理II）设111(,,)XfT，222(,,)XfT是(,,)XfT的两个商空间，而且,1,2iTi是半序。令333(,,)XfT是111(,,)XfT，222(,,)XfT的上确界空间，若问题11AB，22AB分别在111(,,)XfT，222(,,)XfT中有解，则对应的问题33AB在333(,,)XfT上也有解。（312312,AAABBB）二.合成技术1.论域的合成设111(,,)XfT，222(,,)XfT是(,,)XfT的两个商空间，12,XX对应的等价关系分别是12,RR，定义1X和2X的合成空间为3X，其对应的等价关系是3R，且312xRyxRyxRy且定义2.1设12,RR是X上任意两等价关系，令3X是12,RR的最小上界，则3R是12,RR的合成。若用划分来表示：设12{},{}iiXaXb，则1X和2X的合成3X可表示为312{|,}iiiiXabaXbX合成商空间3X是满足合成原则的最粗的商空间，即最小上界，具有某种意义下的最优性。2.拓扑结构的合成设111(,,)XfT，222(,,)XfT是(,,)XfT的两个商空间，定义1T和2T的合成为3T，定义2.21T和2T的合成是X上所有拓扑构成的半序格中1T和2T的最小上界3T。3T具体的构成如下：12{|,,}iiiiBwwuvuTvT，然后以B为拓扑基的拓扑就是3T。例2.1设X={1,2,3,4,}，1{,{1},{1,2