2012/08/30
欧拉回路的回朔算法
首先算法不会给出所有的回路，当算法结束的时候，得到的仅仅是一个回路，算法检查边的顺序不同会造成结果的回路不同。把所有的边编号，其中的变量的含义g[node][i]是从node出发第i条边到达的节点。
search可以看成是检查当前节点node有没有未用过的边，如果没有就会返回，调用堆栈往上一层，search( g[node][i] )返回说明，边i到达节点g[node][i]，但是这个节点无边可用了，我们把i记下来(回朔)，然后看看从node出发的其他边能不能前进，如果假设node出来就一条边，那么算法会再往上返回，上面一层会认为node无边可用了，把探索的时候通向node的边也记下来。
分析算法的运行过程，算法一开始从一个节点开始，只要发现没用过的边就往前走，称这时候为探索模式，一直到没有边可用，注意这时候并不代表所有的边都用过了，还可能是当前节点的连接的边都用过了。没有边可用的时候算法开始回朔，回朔的同时记录边，回朔到某个节点，又有没用过的边，算法又开始往前，直到又没有边可用，开始回朔。最后所有的边都用完的时候，算法会一直到回朔到起点，最后记录的是从起点出来的边。
任何边在算法运行过程中只会被用一次，回朔开始的时候必然是到达了一个以前访问过的节点，因为如果到达一个节点，没被访问过，并且又无边可用，这个节点的度为1，不存在欧拉回路。
第一次回朔是什么时候开始的呢？回朔发生以前，站在任何一个节点看，算法必然是进去出来交替发生，对任何一个非起点节点，一进一出我们把节点的度减掉2，可以看出对于非起点节点是不可能发生进去出不来的情况，因为他们的度都是偶数，所以回朔第一次发生必然是在起点，因为起点是直接出来，度只需要减1。
还有一点就是，虽然第一次回朔发生在起点，在回朔的过程中还是会发现有的节点的degree没用完，算法可能再次进入探索模式。也就是当前节点有边可用进入探索模式，无边可用进入回朔模式。
2012/08/25
Matching
图里的match是边的集合M，要求M里没有两个边是有公共顶点的。这个名字可能是起源于婚姻问题，如果有公共顶点就是重婚了，所以是不允许的。
Marriage Problem: $m$个男孩，每个男孩认识一些女孩，现在开始match，要求每个男孩必须和他认识的女孩结婚，求这种方法存在的充分必要条件。
Hall's Theorem: Marriage Problem有解的充要条件是，任取$k$个男孩，他们必须认识至少$k$个女孩，其中$1\leq k\leq m$
二分图的最大match可以用网络流里面的Augmenting path来解决，先回顾一下网络流里的一些概念。
Residual network：对于一个网络上的flow来说，Residual network记录了这个flow在不违反网络每个路径的流量限制的条件下的所有变化的自由度。而且Residual network上的flow和原来的flow叠加还是原网络的一个合法的flow，满足flow的三个约束。
Augmenting path：是Residual network上的一个从源头到终点的简单路径。
augmenting path的residual capacity：是这个augmenting path上在Residual network里允许的最大流量。
所以Augmenting path不过是有向图的一个简单路径，所以用BFS或DFS查找均可。
二分图的最大match是这样转换为最大流问题的，首先男孩那边加一个节点$s$作为源头，并且和所有的男孩相连，女孩这边加一个节点作为终点$t$，同样和所有女孩相连，男孩到女孩的所有边都是男孩指向女孩。每条边的容量都设置为1。
很显然最后的flow不会有两个男孩连接到一个女孩，否则从这个女孩到$t$的流量就为2，这是不可能的。假设起始的时候flow的流量为0，每找到一个Augmenting path，这个path的容量只能是1。
用DFS找Augmenting path的时候，可以直接遍历所有男孩，因为这就相当于遍历所有$s$的邻居。
考虑两种Augmenting path，最简单的情况是，从某男出发，第一步就发现一个没被match的女孩，得一条边的Augmenting path；如果从某男开始DFS遇到的第一个女孩已经match了，这时候DFS不能停，因为按Residual network的容量看，这女孩到和她match的男孩的路径有一个反向的容量，所以继续，坏的情况，这男孩只认识这一个女孩，这时候DFS要开始返回了，这条path不是Augmenting path，好的情况，这男孩还认识其他没match的女孩，DFS会访问到这个新没match的女孩，这时候我们就得到了一条Augmenting path。
第二种情况实际上是劝说一个已经match的男孩换女朋友。
程序是这样的，bpm(u)可以理解为给u找女朋友，如果发现的女孩已有男朋友，劝说其男朋友换女朋友，而且不能换DFS已经见过的女孩，既然让人家换就得给人家找所有要再调bpm。
算法最终返回的条件是发现一个新的没match的女孩，而且这时候所有Augmenting path的男孩都得换女朋友。
Marriage Problem: $m$个男孩，每个男孩认识一些女孩，现在开始match，要求每个男孩必须和他认识的女孩结婚，求这种方法存在的充分必要条件。
Hall's Theorem: Marriage Problem有解的充要条件是，任取$k$个男孩，他们必须认识至少$k$个女孩，其中$1\leq k\leq m$
二分图的最大match可以用网络流里面的Augmenting path来解决，先回顾一下网络流里的一些概念。
Residual network：对于一个网络上的flow来说，Residual network记录了这个flow在不违反网络每个路径的流量限制的条件下的所有变化的自由度。而且Residual network上的flow和原来的flow叠加还是原网络的一个合法的flow，满足flow的三个约束。
Augmenting path：是Residual network上的一个从源头到终点的简单路径。
augmenting path的residual capacity：是这个augmenting path上在Residual network里允许的最大流量。
二分图的最大match
所以Augmenting path不过是有向图的一个简单路径，所以用BFS或DFS查找均可。
二分图的最大match是这样转换为最大流问题的，首先男孩那边加一个节点$s$作为源头，并且和所有的男孩相连，女孩这边加一个节点作为终点$t$，同样和所有女孩相连，男孩到女孩的所有边都是男孩指向女孩。每条边的容量都设置为1。
很显然最后的flow不会有两个男孩连接到一个女孩，否则从这个女孩到$t$的流量就为2，这是不可能的。假设起始的时候flow的流量为0，每找到一个Augmenting path，这个path的容量只能是1。
用DFS找Augmenting path的时候，可以直接遍历所有男孩，因为这就相当于遍历所有$s$的邻居。
考虑两种Augmenting path，最简单的情况是，从某男出发，第一步就发现一个没被match的女孩，得一条边的Augmenting path；如果从某男开始DFS遇到的第一个女孩已经match了，这时候DFS不能停，因为按Residual network的容量看，这女孩到和她match的男孩的路径有一个反向的容量，所以继续，坏的情况，这男孩只认识这一个女孩，这时候DFS要开始返回了，这条path不是Augmenting path，好的情况，这男孩还认识其他没match的女孩，DFS会访问到这个新没match的女孩，这时候我们就得到了一条Augmenting path。
第二种情况实际上是劝说一个已经match的男孩换女朋友。
程序是这样的，bpm(u)可以理解为给u找女朋友，如果发现的女孩已有男朋友，劝说其男朋友换女朋友，而且不能换DFS已经见过的女孩，既然让人家换就得给人家找所有要再调bpm。
算法最终返回的条件是发现一个新的没match的女孩，而且这时候所有Augmenting path的男孩都得换女朋友。
2012/08/10
2012/08/05
设计模式概论
代码复用是类的属性，通信是运行时对象的属性。利用继承实现协作是用类描述的，利用通信实现的协作是用对象描述的。
类和类型的区别，类定义了对象内部状态和操作的实现，类型则是和接口的概念对应的。
创建型模式强制你采用针对接口的编程习惯，而不是针对实现的编程。
继承和组合的比较，继承多是静态代码复用，子类了解父类的实现，某种意义上破坏了封装。组合是更好的封装，更依赖于接口的定义，更依赖于运行时对象之间的关系来实现程序的逻辑。
用创建模式产生对象实例而不指定类名。
用Command或者Chain of Responsibility避免把请求操作的代码写死。
利用abstract factory和Bridge分离设计和实现以应付平台和API的变化。
利用Adapter，Decorator和Visitor改变已有对象的行为。
类厂语法特点是产生实例的时候并没有指定要产生的实例的类名。 程序会维护一个全局的基类类厂指针，使得可以在运行时替换类厂实例。
类厂分类的方法可能是按风格，可能是按平台。程序的逻辑决定什么时候信息足够，可以实例化什么类厂。类厂的类型可以是编译期决定的，比如跨平台的应用，类厂实现必须是按平台分的。也可以是运行期才有足够的信息决定类厂的类型，比如用户对程序的风格设置。
更高级的方法，把类厂和一个字符串(类厂的名字)对应起来，客户程序传入一个字符串，程序逻辑返回一个类厂实例。
一旦类厂的实例确定了，程序的一个方面就确定了，也就是一般来说使用一个类厂，必须使用全部的这个类厂产生的实例。
Window类是系统定义的抽象的window系统，决定了系统定义的可以做事情。Window类把实际的操作委托给WindowImp的继承类。WindowSystemFactory是产生WindowImp继承类的实例的类厂接口，不同的类厂实现对应不同的Imp类例如WindowImp，FontImp。
Imp类例如WindowImp，FontImp像是给抽象系统Window提供的API，这API隐藏了实际OS相关的实现，一旦系统决定了类厂的实例，API就定了。
对一个系统来说，request来自各个方面，例如OS，鼠标，键盘，网络，一但request产生，用户希望某个operation被运行。但是operation的实现可能分布在代码的各个地方，各种不同的类。
最直接的办法是把operation的代码封装在request的来源里，例如MenuItemChangeColor::Click(){}。但是这种方法的使得代码结合的太紧密。
识别request的来源的实质是需要参数化request的来源，比如MenuItemChangeColor，设计模式里用一个object来参数化，这个object是command。
command有一个方法Execute，里面封装了operation的代码，也可以在这些代码里把operation委托给程序的其他的办法。
Iterator Pattern封装了这些机制，使用Iterator，客户程序不需要知道需要遍历的结构的内部细节，而且遍历的状态被保存在iterator里，所以可以同时有多个遍历同时运行。而且可以有不同类型的Iterator实现，比如如果结构是一个tree，可以PreIterator， PostIterator，MidIterator几个继承类。
遍历的算法经常需要积累信息，比如遍历一段文本，计数word，不同的算法可能需要积累不同的信息，不好的做法是把积累信息的code集成到Iterator里，这样会造成紧密结合，所以最好能把遍历里的action和Iterator分开。
引入Visitor
一般的遍历的所做的事情，例如分析问题的代码如下，把action封装在类SpellingChecker里，这个类的一个方法接受被遍历的对象的指针。 上面code不好的地方是一堆if，而且随着系统的进化，这个方法会不停的被改变。更好一点的实现方法是
上面的机制抽象出来就得到了Visitor模式，首先遍历时候的action不一定是check，我们称抽象出来的封装action的类为Visitor。同样的，被访问的对象的抽象方法(CheckMe)称为Accept(Visitor&)。不同的遍历action被封装在Visitor的不同的method里。
类和类型的区别，类定义了对象内部状态和操作的实现，类型则是和接口的概念对应的。
创建型模式强制你采用针对接口的编程习惯，而不是针对实现的编程。
继承和组合的比较，继承多是静态代码复用，子类了解父类的实现，某种意义上破坏了封装。组合是更好的封装，更依赖于接口的定义，更依赖于运行时对象之间的关系来实现程序的逻辑。
用设计模式应付未来的变化
用创建模式产生对象实例而不指定类名。
用Command或者Chain of Responsibility避免把请求操作的代码写死。
利用abstract factory和Bridge分离设计和实现以应付平台和API的变化。
利用Adapter，Decorator和Visitor改变已有对象的行为。
类厂
类厂语法特点是产生实例的时候并没有指定要产生的实例的类名。 程序会维护一个全局的基类类厂指针，使得可以在运行时替换类厂实例。
类厂分类的方法可能是按风格，可能是按平台。程序的逻辑决定什么时候信息足够，可以实例化什么类厂。类厂的类型可以是编译期决定的，比如跨平台的应用，类厂实现必须是按平台分的。也可以是运行期才有足够的信息决定类厂的类型，比如用户对程序的风格设置。
更高级的方法，把类厂和一个字符串(类厂的名字)对应起来，客户程序传入一个字符串，程序逻辑返回一个类厂实例。
一旦类厂的实例确定了，程序的一个方面就确定了，也就是一般来说使用一个类厂，必须使用全部的这个类厂产生的实例。
Window System
Window类是系统定义的抽象的window系统，决定了系统定义的可以做事情。Window类把实际的操作委托给WindowImp的继承类。WindowSystemFactory是产生WindowImp继承类的实例的类厂接口，不同的类厂实现对应不同的Imp类例如WindowImp，FontImp。
Imp类例如WindowImp，FontImp像是给抽象系统Window提供的API，这API隐藏了实际OS相关的实现，一旦系统决定了类厂的实例，API就定了。
Operation和request的封装
对一个系统来说，request来自各个方面，例如OS，鼠标，键盘，网络，一但request产生，用户希望某个operation被运行。但是operation的实现可能分布在代码的各个地方，各种不同的类。
最直接的办法是把operation的代码封装在request的来源里，例如MenuItemChangeColor::Click(){}。但是这种方法的使得代码结合的太紧密。
识别request的来源的实质是需要参数化request的来源，比如MenuItemChangeColor，设计模式里用一个object来参数化，这个object是command。
command有一个方法Execute，里面封装了operation的代码，也可以在这些代码里把operation委托给程序的其他的办法。
access 和traversal mechanisms的封装
Iterator Pattern封装了这些机制，使用Iterator，客户程序不需要知道需要遍历的结构的内部细节，而且遍历的状态被保存在iterator里，所以可以同时有多个遍历同时运行。而且可以有不同类型的Iterator实现，比如如果结构是一个tree，可以PreIterator， PostIterator，MidIterator几个继承类。
遍历的算法经常需要积累信息，比如遍历一段文本，计数word，不同的算法可能需要积累不同的信息，不好的做法是把积累信息的code集成到Iterator里，这样会造成紧密结合，所以最好能把遍历里的action和Iterator分开。
引入Visitor
一般的遍历的所做的事情，例如分析问题的代码如下，把action封装在类SpellingChecker里，这个类的一个方法接受被遍历的对象的指针。 上面code不好的地方是一堆if，而且随着系统的进化，这个方法会不停的被改变。更好一点的实现方法是
上面的机制抽象出来就得到了Visitor模式，首先遍历时候的action不一定是check，我们称抽象出来的封装action的类为Visitor。同样的，被访问的对象的抽象方法(CheckMe)称为Accept(Visitor&)。不同的遍历action被封装在Visitor的不同的method里。
2012/08/04
Cut-Set
cut-set也叫cocycle。任取一个支撑树，树上的边称为branch，图里其他的边称为chord。
任何一个cut-set必然包含任何一个支撑树的至少一条边。反过来，连通图$G$里的任何一个最小集合，如果这个集合包含所有支撑树的至少一条边，这个最小集合是一个cut-set。
任何一个cut-set必然包含任何一个cycle的偶数个边。
任取一个支撑树$T$，$b$为$T$的任何一个边，显然$\{b\}$是$T$的cut-set，$\{b\}$把图的顶点分为两部分，考虑整个图的一个cut-set，把图的顶点分成同样的两部分，而且这个cut-set只包含$T$的一个branch，其他的都是chord，这个cut-set称为fundamental cut-set respect to $T$。
支撑树$T$的任意一个边对应了唯一的一个fundamental cut-set。
对偶性，Fundamental cut-set和Fundamental cycle的关系，我们知道任选一个chord对应了一个Fundamental cycle，这个cycle上的边除了一个chord其他的是branch。进一步的每个branch对应了一个Fundamental cut-set，这个cut-set包含一个branch，其他都是chord。
一个cut-set respect两个顶点$v_1, v_2$意思是这个cut-set吧两个顶点分在两个不同的集合里。
一个weighted无向图，上面的cut-set的capacity是这个cut-set里的所有边的weight的和。
定理：$v_1, v_2$之间的最大可能flow等于所有的respect这两个顶点的cut-set里capacity最小的。
任何一个cut-set必然包含任何一个支撑树的至少一条边。反过来，连通图$G$里的任何一个最小集合，如果这个集合包含所有支撑树的至少一条边，这个最小集合是一个cut-set。
任何一个cut-set必然包含任何一个cycle的偶数个边。
任取一个支撑树$T$，$b$为$T$的任何一个边，显然$\{b\}$是$T$的cut-set，$\{b\}$把图的顶点分为两部分，考虑整个图的一个cut-set，把图的顶点分成同样的两部分，而且这个cut-set只包含$T$的一个branch，其他的都是chord，这个cut-set称为fundamental cut-set respect to $T$。
支撑树$T$的任意一个边对应了唯一的一个fundamental cut-set。
对偶性，Fundamental cut-set和Fundamental cycle的关系，我们知道任选一个chord对应了一个Fundamental cycle，这个cycle上的边除了一个chord其他的是branch。进一步的每个branch对应了一个Fundamental cut-set，这个cut-set包含一个branch，其他都是chord。
一个cut-set respect两个顶点$v_1, v_2$意思是这个cut-set吧两个顶点分在两个不同的集合里。
Network Flows
一个weighted无向图，上面的cut-set的capacity是这个cut-set里的所有边的weight的和。
定理：$v_1, v_2$之间的最大可能flow等于所有的respect这两个顶点的cut-set里capacity最小的。
Subscribe to:
Posts (Atom)