Ination浅析1.ppt

1、CEOI 2008 竞赛题讨论Information,问题描述,情报网络： n个特工+m个联络员 网络中传递的完整的情报被一分为二 联络员负责在两个特定的特工之间单向传递情报的一部分 特工最终要获得完整的情报信息。 试为给定的情报网络建立一个传输方法。,问题抽象与归纳1,问题的基本结构是一个有重边的有向图G=V,E G对应于传输方案（Transmission scheme) V是图的结点集合，其中元素表示特工（agent）； E是图的边集合，其中元素表示联络员（contact） E的另一特点，它是有序集（有向边的集合）。,问题抽象归纳2,问题的目标是将E分为两个交集为空的子集E1、E2， 使G

2、1 V, E1 与 G2 V, E2 G1、 G2分别是原图的连通子图 这里E1与E2也是有序集。 元素顺序与其在E中的顺序一致。,问题抽象归纳3,给定n个结点，m条边的一个有重复边的有向图G（允许两个结点间的边数多于一条）。 图G有一个根结点，即入度为零的结点 问题是在图G中寻找两条从根结点出发的没有公共边的遍历途径。,输入输出格式,输入文件 第一行：特工人数N，联络员总数M 其后M行：各联络员对应的特工编号 输出 无解：NONE 有解：输出两行，每行对应情报一个部分的有效传输方案。在每行中给出使用的联络员的编号。,朴素的想法,分别选取基数为n-1的两个边子集E1，E2 选择方法为Krusk

3、al算法的变形 1. E1= , G1 = V, E1 2. E1=E1+e （ eE） 3. 重复2中操作，直到|V|=n-1 也可使用Prim算法,朴素的想法,基本思路是，先从边集E中按一定规则选取n-1个元素构成E1，E1与V构成子图G1 在E-E1中选取n-1条边构成E2，E2与V构成子图G2。 若G1与G2都是连通的，则分行依序输出E1与E2中的元素。 若G1或G2有一个是不连通的，则按规则选择另一组E1及其后的E2，直到构成解或重复选择的次数超过了预先的限制。,算法实现思路,该过程可以用一个类似Kruskal的算法实现，即： 对G = V, E , 先构造一个只有 n 个顶点, 没

4、有边的非连通图 G1 = V, 这时G1中每个顶点自成一个连通分量。 然后在 E 中选一条边（从边集E中选择边的顺序可以依E集合本身的顺序，随机选取等）, 若该边的两个顶点在不同的连通分量中，则将此边加入到 G1 中，否则重新选择一条边。 如此重复下去, 直到所有顶点在同一个连通分量上为止。 边数总共有n-1条，G1为生成树。G2同理。,算法实现思路,在构造生成树G1、G2过程中, 可利用并查集的运算检查一条边上的两顶点是否在同一连通分量 (即并查集的同一个子集合) 上 是则舍去这条边；否则将此边加入G1或G2, 同时将这两个顶点并入同一个连通分量。 用BFS或DFS遍历的方法判断图的连通性，

5、如果对生成的子图遍历到全部n个结点，则说明子图是连通的；否则是非连通的。,参考算法,首先使用Prim算法生成一个以第一个结点为根的生成树，即将图G的结点集V分为两个子集V1，V2，其中V1是生成树的顶点集合。 假设G是连通图，那么在V1与V2之间必有至少一条边相连。于是，按一定规则（在Prim算法中是选取权值最小的边，对应于本题则可以根据eE的次序）选取一条边e （u, v）（uV1，vV2）， 将其加入G1V1, E1，直到|V1|n-1。然后使用剩余的边生成G2。,总之，可以先任意构造一棵生成树G1； 然后使用剩余的边，尽可能的尝试构造第二棵生成树G2。,算法讨论,关键步骤 如何选择合适的

6、边进行并查集的运算 回溯的存在是算法性能的最大负担,算法初探一,通过试探回溯，先找到一条遍历途径， 然后再找到另一条遍历途径。 实现非常简单！,问题：时间复杂度O(n!*m) 实际运行时，只能使用于n=10的情况,算法改进,在找到第一条路时，如果第二条行不通，回溯造成很大的时间浪费。 如果考虑两条遍历路径一起寻找，约束条件更强。 问题：只适用于一些特殊的情况。比如联络员数刚好够用。 但仍然是朴素的试探回溯。,启发：必须两条路径同时考虑,寻找突破,寻找突破的关键是避免回溯。寻找一种直接能够找到遍历途径的方法。 考虑到使用M1, M2特工之间的联络员并不会影响到其他特工间情报的传递。只有可能影响到

7、另一部分情报的传递。 只要保证在任何情况下的传递两部分情报都是等价的，就不用回溯。,一种实现方法,1） 从得到情报的特工拥有的联络员中选出一个可用的将第一部分情报传递出去。初始便是这种情况。 2）执行完（1）操作之后，得到第一部分情报的特工将比得到第二部分情报的特工人数多1。 然后将第二部分情报传递给多余的这个特工。执行完后，要么回到第一种情况，要么得到第二部分情报的特工比得到第一部分情报的特工人多。如果是前一种情况，执行1操作。否则，执行（2）操作。,实现操作的基本类,图类Graph 图的存储表示可使用邻接表；也可使用邻接矩阵，但要考虑其稀疏性 稀疏矩阵类Matrix的元素为四元组： 两个整

8、型变量分别为边的首末结点号， 第三个整型变量中存放其间存在的联络员的总数 第四个元素是队列类Queue的对象指针，指向一个队列，其中依次存放两个特工之间的联络员编号。,实现操作的基本类,队列类Queue 用于BFS遍历时记录同层结点，对图中的边进行操作，方便对图的遍历 并查集类UFSets 处理结点与连通分量之间的关系（通过Find与Union操作）,样例演示：,朴素的试探回溯,最终算法,1,3,5,2,4,6,操作,1,2,1,3,4,2,.,.,深度优先遍历,层次遍历,可以证明，如果该步骤如果不能够执行下去，那么将找不到符合条件的两条遍历路径。,算法的细节优化,可以在遍历之前对一些最坏的情

9、况进行判断。比如有结点的入度小于2，那么直接可以判断得出，没有满足条件的遍历途径。 存储及实现：图采用邻接表的存储结构可以降低访问时间。同时，层次遍历借助本身存储的数组作为队列即可,时间和空间的协调：可以增加一些判断 如邻接表存储可以使用双向链表方便使用过的联络员和一些无用联络员的删除 这样对于大的数据来说，时间会节省很多，但是对于小的数据，则额外增加了很多存储空间对时间贡献不大。,再探问题的本质,核心概念：拟阵M = (E,T) 集合E为有限集 集合T：由E的幂集的子集构成，即T是由若干特定的E的子集组成的集合。这些子集被称做独立集 性质1：对AT, BA, 有BT； 性质2：如果A，BT并

10、且|A|B|，那么存在一个元素 zAB，使得 B+zT 形象化的说明 性质1：A 的子集B“继承”了A的身份 性质2：B可以被“扩大”,相关概念,拟阵 M = (E,T)中 T的元素被称作独立集 其它E的不属于T的子集被称作非独立集 实例： 在一个图中，T中基数最大的元素（含有最多边数的独立集）对应于G的生成树！,拟阵的交,拟阵的交 对于定义在同一个集合E上的两个拟阵 M1=(S,T1), M2=(S,T2) 求T1与T2共有的最大独立集I 重要定理：对于 有 Edmonds 1973年曾证明： 以首结点为根且边不相交的生成树的最大数目等于任意以首结点为割点的割集的最小基数。在Informat

11、ion这道题中，这一基数为。,惠特尼与拟阵(matroid)理论,惠特尼（美国数学家，1907-1989）在组合论方面的最大成就是他引进拟阵(matroid)理论一种抽象的线性相关性理论，它不仅包含图论为其特例，而且还包括网络理论、综合几何以及横截(transversal)理论等 基本出发点大致为，考虑矩阵M的列C1，C2，Cn，这些列的子集或者线性独立或者线性相关，从而所有子集可划分为两类，这些类并非任意，它必须满足下面两个条件： (1)一个独立集的任何子集也是独立的； (2)如果Np及Np+1分别是p个列及p+1个列的独立集，则 Np加上Np+1中的某个列构成一个独立的p+1集,思考,图论问题往往与代数问题、组合优化问题等密切相关或可互相转化。 对题目的深刻认识与高效率的解题需要对图论问题所涉及的结构有代数层面上的理解 朴素直观的想法在寻找可行解时可能有一定的用处，但难以保证性能,参考文献,参考资料 1. /OcwWeb/web/courses/courses/index.htm, MIT OpenCourseWare 18.997,Topics in Combinatorial Op