第3期 毛华，等：利用二元拟阵K。图的一种建格方法 ·339. b1b3bg)、(C5,b2b3bg)、(C6,b1b2b1o)。 中的一些属性条件的限制，在K。图模型中，根据三 4)把第1层和第4层概念(0，{})和({}，P),根 角形圈的一种特殊性，寻找规律，结果发现，对K图 据定义6和引理2的偏序关系(C,b,)≤(C2,b2)台 拟阵的标准矩阵的形式背景产生4层。根据此规律 C,二C,(台b,二b,),对满足概念格子概念-父概念的 进行建格，提出利用二元拟阵的K图的概念格的建 关系)，把第1层的概念(0，{})与第2层的概念 格方法。相比最基本的建格方法，此方法的计算量 建立连线，第4层的概念({}，P)与第3层概念建立 要少很多。通过实例发现，针对这种特殊的形式背 连线加入到步骤2)和3)组成的二部图中，得到概 景，出行者在提取有用的方案时，会更加快速、方 念格的Hasse示图，如图4。 便。由于研究背景和素材来源于实践，这类事件很 (C.C.C.C.C.C) 多，因此提出的方法具有很好的推广意义和应用前 景。在接下来的研究中，将会在K,图中加人权值， (CC C2.b.) 进行距离和时间等多种属性的研究。 (CC Cb)O D(C.C.C.b) (Csbbb) 参考文献： (C,b,b,b○ OCbbb) (C:.bbb)(C:.b.b b)(C.Bb,b) [1]左锋.经济学视野中大城市经济圈的形成与发展一论中 国三大城市经济圈的现状及其发展[].华东师范大学 学报：哲学社会科学版，2002,34(5)：89-95 ZUO Feng.The formation and development of a metropolitan (13.b b bbb bbbbb) economic circle in the perspec-tive of economics [J]. 图4K,图的概念格 Journal of east cluna normal university:philosophy and Fig.4 Concept lattice of Ks diagram social sciences,2002,34(5):89-95. 从图4中可以看出，满足b,这段距离油耗的货 [2]胡一竑.基于复杂网络的交通网络复杂性研究[D].上 车有且仅有C1、C4、C6方案，满足b2这段距离油耗 海：复旦大学，2008：1-121. 的货车有且仅有C2、C5、C6方案，满足b这段距离 HU Yihong.Analysis of complex transportation networks 油耗的货车有且仅有C3、C4、C,方案，满足b。这段 [D].Shanghai:Fudan University,2008:1-121. 距离油耗的货车有且仅有C,、C2、C,方案，还可以快 [3]刘佳.复杂网络中最短路径问题的优化算法研究[D] 太原：太原科技大学，2007：1-30. 速地计算出每个方案需要走的距离里程。若采用 LIU Jia.Research on the algorithm for shortest path problem 方案C,需走的距离里程为b,+b,+b,=85km;若采 in complicated network[D].Taiyuan:Taiyuan University of 用方案C2,需走的距离里程为b,+b,+b。=103km:若 Science and Technology,2007:1-30. 采用方案C3,需走的距离里程为b,+b。+b,=140km [4]严寒冰，刘迎春.基于GS的城市道路网最短路径算法 若采用方案C4,需走的距离里程为b,+b+bg= 探讨[J].计算机学报，2000,23(2)：210-215. 86km;若采用方案C5,需走的距离里程为b2+b3+ YAN Hanbing,LIU Yingchun.A new algorithm for finding b,=113km;采用方案C6,需要走的距离里程为b,+ shortcut in a city's road net based on GIS technology[J] b2+b1o=64km。从中比较可知，若运送货物途经距 Chinese journal of computers,2000,23(2):210-215. 离最短，可以选择方案C6。 [5]谢政，李建平.网络算法与复杂性理论[.北京：国防 从图4中可快速地筛选出运输最短路径的运输 科技大学出版社，1995：120-140. 方案和最长路径的运输方案，方便出行者对出行方 [6]LAM W H K,LI Zhichun,HUANG Haijun,et al.Modeling 案的选择。在其他复杂网络中，两个顶点之间会出 time-dependent travel choice problems in road networks with 现两条边，比如重边的情况，在寻找哪种方案最优 multiple user classes and multiple parking facilities[J]. 时，可能出现多种方案，而本文开始时就已经删除 Transportation research part B:methodological,2006,40 (5):368-395. 了那些对选择方案无用的边，因此从概念格的 [7]GAO Song,Chabini I.Optimal routing policy problems in Hasse图中很容易看出哪个方案最优，不需要出行 stochastic time-dependent networks J].Transportation 者进行2次或更多次的重新比较。 research parB:methodological,2006,40(2):93-122. 4 结束语 [8]于德新，杨薇，杨兆升.重大灾害条件下基于GS的最 短路径改进算法[J].交通运输工程学报，2011,11(4)： 根据京津冀紧密对接的一体化交通网络。基 123-126. 于出行者对于交通网络路径的选择，根据实际生活 YU Dexin,YANG Wei,YANG Zhaosheng.Shortest pathｂ１ ｂ３ ｂ８ ）、（Ｃ５ ，ｂ２ ｂ３ ｂ９ ）、（Ｃ６ ，ｂ１ ｂ２ ｂ１０ ）。 ４）把第 １ 层和第 ４ 层概念（Ｏ，｛｝）和（｛｝，Ｐ），根 据定义 ６ 和引理 ２ 的偏序关系（Ｃ１ ，ｂ１ ）≤（Ｃ２ ，ｂ２ ）⇔ Ｃ１⊆Ｃ２（⇔ｂ２⊆ｂ１ ），对满足概念格子概念－父概念的 关系［２３］ ，把第 １ 层的概念（Ｏ，｛ ｝）与第 ２ 层的概念 建立连线，第 ４ 层的概念（｛｝，Ｐ）与第 ３ 层概念建立 连线加入到步骤 ２）和 ３）组成的二部图中，得到概 念格的 Ｈａｓｓｅ 示图，如图 ４。 图 ４ Ｋ５ 图的概念格 Ｆｉｇ．４ Ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｏｆ Ｋ５ ｄｉａｇｒａｍ 从图 ４ 中可以看出，满足 ｂ１ 这段距离油耗的货 车有且仅有 Ｃ１ 、Ｃ４ 、Ｃ６ 方案，满足 ｂ２ 这段距离油耗 的货车有且仅有 Ｃ２ 、Ｃ５ 、Ｃ６ 方案，满足 ｂ３ 这段距离 油耗的货车有且仅有 Ｃ３ 、Ｃ４ 、Ｃ５ 方案，满足 ｂ４ 这段 距离油耗的货车有且仅有 Ｃ１ 、Ｃ２ 、Ｃ３ 方案，还可以快 速地计算出每个方案需要走的距离里程。 若采用 方案 Ｃ１ ，需走的距离里程为 ｂ１ ＋ｂ４ ＋ｂ５ ＝ ８５ ｋｍ；若采 用方案 Ｃ２ ，需走的距离里程为 ｂ２ ＋ｂ４ ＋ｂ６ ＝ １０３ ｋｍ；若 采用方案 Ｃ３ ，需走的距离里程为 ｂ４ ＋ｂ６ ＋ｂ７ ＝ １４０ ｋｍ； 若采用方案 Ｃ４ ， 需走的距离里程为 ｂ１ ＋ ｂ３ ＋ ｂ８ ＝ ８６ ｋｍ；若采用方案 Ｃ５ ，需走的距离里程为 ｂ２ ＋ｂ３ ＋ ｂ９ ＝ １１３ ｋｍ；采用方案 Ｃ６ ，需要走的距离里程为 ｂ１ ＋ ｂ２ ＋ｂ１０ ＝ ６４ ｋｍ。 从中比较可知，若运送货物途经距 离最短，可以选择方案 Ｃ６ 。 从图 ４ 中可快速地筛选出运输最短路径的运输 方案和最长路径的运输方案，方便出行者对出行方 案的选择。 在其他复杂网络中，两个顶点之间会出 现两条边，比如重边的情况，在寻找哪种方案最优 时，可能出现多种方案，而本文开始时就已经删除 了那些 对 选 择 方 案 无 用 的 边， 因 此 从 概 念 格 的 Ｈａｓｓｅ 图中很容易看出哪个方案最优，不需要出行 者进行 ２ 次或更多次的重新比较。 ４ 结束语 根据京津冀紧密对接的一体化交通网络。 基 于出行者对于交通网络路径的选择，根据实际生活 中的一些属性条件的限制，在 Ｋｎ 图模型中，根据三 角形圈的一种特殊性，寻找规律，结果发现，对 Ｋｎ 图 拟阵的标准矩阵的形式背景产生 ４ 层。 根据此规律 进行建格，提出利用二元拟阵的 Ｋｎ 图的概念格的建 格方法。 相比最基本的建格方法，此方法的计算量 要少很多。 通过实例发现，针对这种特殊的形式背 景，出行者在提取有用的方案时，会更加快速、方 便。 由于研究背景和素材来源于实践，这类事件很 多，因此提出的方法具有很好的推广意义和应用前 景。 在接下来的研究中，将会在 Ｋｎ 图中加入权值， 进行距离和时间等多种属性的研究。 参考文献： ［１］左锋． 经济学视野中大城市经济圈的形成与发展—论中 国三大城市经济圈的现状及其发展［ Ｊ］． 华东师范大学 学报：哲学社会科学版， ２００２， ３４（５）： ８９－９５． ＺＵＯ Ｆｅｎｇ． Ｔｈｅ ｆｏｒｍａｔｉｏｎ ａｎｄ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ａ ｍｅｔｒｏｐｏｌｉｔａｎ ｅｃｏｎｏｍｉｃ ｃｉｒｃｌｅ ｉｎ ｔｈｅ ｐｅｒｓｐｅｃ⁃ｔｉｖｅ ｏｆ ｅｃｏｎｏｍｉｃｓ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ ｅａｓｔ ｃｌｕｎａ ｎｏｒｍａｌ ｕｎｉｖｅｒｓｉｔｙ： ｐｈｉｌｏｓｏｐｈｙ ａｎｄ ｓｏｃｉａｌ ｓｃｉｅｎｃｅｓ， ２００２， ３４（５）： ８９－９５． ［２］胡一竑． 基于复杂网络的交通网络复杂性研究［Ｄ］． 上 海：复旦大学， ２００８： １－１２１． ＨＵ Ｙｉｈｏｎｇ． Ａｎａｌｙｓｉｓ ｏｆ ｃｏｍｐｌｅｘ ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｎｅｔｗｏｒｋｓ ［Ｄ］．Ｓｈａｎｇｈａｉ： Ｆｕｄａｎ Ｕｎｉｖｅｒｓｉｔｙ， ２００８： １－１２１． ［３］刘佳． 复杂网络中最短路径问题的优化算法研究［Ｄ］． 太原： 太原科技大学， ２００７： １－３０． ＬＩＵ Ｊｉａ． Ｒｅｓｅａｒｃｈ ｏｎ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｐｒｏｂｌｅｍ ｉｎ ｃｏｍｐｌｉｃａｔｅｄ ｎｅｔｗｏｒｋ［Ｄ］． Ｔａｉｙｕａｎ： Ｔａｉｙｕａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， ２００７： １－３０． ［４］严寒冰， 刘迎春． 基于 ＧＩＳ 的城市道路网最短路径算法 探讨［Ｊ］． 计算机学报， ２０００， ２３（２）： ２１０－２１５． ＹＡＮ Ｈａｎｂｉｎｇ， ＬＩＵ Ｙｉｎｇｃｈｕｎ． Ａ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｆｉｎｄｉｎｇ ｓｈｏｒｔｃｕｔ ｉｎ ａ ｃｉｔｙ’ ｓ ｒｏａｄ ｎｅｔ ｂａｓｅｄ ｏｎ ＧＩＳ ｔｅｃｈｎｏｌｏｇｙ［ Ｊ］． Ｃｈｉｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒｓ， ２０００， ２３（２）： ２１０－２１５． ［５］谢政， 李建平． 网络算法与复杂性理论［Ｍ］． 北京：国防 科技大学出版社， １９９５： １２０－１４０． ［６］ＬＡＭ Ｗ Ｈ Ｋ， ＬＩ Ｚｈｉｃｈｕｎ， ＨＵＡＮＧ Ｈａｉｊｕｎ， ｅｔ ａｌ． Ｍｏｄｅｌｉｎｇ ｔｉｍｅ⁃ｄｅｐｅｎｄｅｎｔ ｔｒａｖｅｌ ｃｈｏｉｃｅ ｐｒｏｂｌｅｍｓ ｉｎ ｒｏａｄ ｎｅｔｗｏｒｋｓ ｗｉｔｈ ｍｕｌｔｉｐｌｅ ｕｓｅｒ ｃｌａｓｓｅｓ ａｎｄ ｍｕｌｔｉｐｌｅ ｐａｒｋｉｎｇ ｆａｃｉｌｉｔｉｅｓ ［ Ｊ ］． Ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｒｅｓｅａｒｃｈ ｐａｒｔ Ｂ： ｍｅｔｈｏｄｏｌｏｇｉｃａｌ， ２００６， ４０ （５）： ３６８－３９５． ［７］ＧＡＯ Ｓｏｎｇ， Ｃｈａｂｉｎｉ Ｉ． Ｏｐｔｉｍａｌ ｒｏｕｔｉｎｇ ｐｏｌｉｃｙ ｐｒｏｂｌｅｍｓ ｉｎ ｓｔｏｃｈａｓｔｉｃ ｔｉｍｅ⁃ｄｅｐｅｎｄｅｎｔ ｎｅｔｗｏｒｋｓ ［ Ｊ ］． Ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｒｅｓｅａｒｃｈ ｐａｒＢ： ｍｅｔｈｏｄｏｌｏｇｉｃａｌ， ２００６， ４０（２）： ９３－１２２． ［８］于德新， 杨薇， 杨兆升． 重大灾害条件下基于 ＧＩＳ 的最 短路径改进算法［Ｊ］． 交通运输工程学报， ２０１１， １１（４）： １２３－１２６． ＹＵ Ｄｅｘｉｎ， ＹＡＮＧ Ｗｅｉ， ＹＡＮＧ Ｚｈａｏｓｈｅｎｇ． Ｓｈｏｒｔｅｓｔ ｐａｔｈ 第 ３ 期 毛华，等：利用二元拟阵 Ｋｎ 图的一种建格方法 ·３３９·