ITeye博客

茅屋

evasiu · 共 64 篇文章

我对KM算法的理解

一般对KM算法的描述,基本上可以概括成以下几个步骤: (1) 初始化可行标杆 (2) 用匈牙利算法寻找完备匹配 (3) 若未找到完备匹配则修改可行标杆 (4) 重复(2)(3)直到找到相等子图的完备匹配 关于该算法的流程及实施,网上有很多介绍,基本上都是围绕可行标杆如何修改而进行的讨论,至于原理并没有给出深入的探讨。 KM算法是用于寻找带权二分图最佳匹配的算法。 二分图是这样一种图:所有顶点可以分成两个集:X和Y,其中X和Y中的任意两个在同一个集中的点都不相连,而来自X集的顶点与来自Y集的顶点有连线。当这些连线被赋于一定的权重时,这样的二分图便是带权二分图。 二分图匹配是指求出一组边,其中的…

2012-12-26 15:47 · 编程 · 评论(0)

一个小题目(单词统计)

今天休息的时候看到一个关于单词统计的小题目: 统计一段由字符和和空格组成的字符串中有多少个单词 题目一看觉得很简单,无非是遍历字符串,然后根据字母是不是空格之类的来统计单词的个数。博主用了一个状态机来做这件事,我觉得颇有新意,所以就记下心来了。后面的留言有人觉得博主这是把简单问题复杂化,其实我觉得不然。最近在看《设计模式精解》,开篇作者提出的观点我就觉得非常好:需求总是在发生变化的,我们必须让我们写出的代码能够适应变化,而不是为预防变化而费尽必力。一语中的,想起大三的时候刚参与实习的时候,那个时候认为需求一旦定下来了就没有理由变,从而把责任怪罪到定义需求的人上面去,其实是多么狭隘。同样,我觉…

2012-08-14 23:12 · 编程 · 实践 · 评论(0)

数独人工解法的一些技巧及其python实现

这段日子实现了十几种数独的解题技巧,说实话,花费的时间比我想象的要长得多。本来说了要看论文的,结果心里痒痒,看着论文,心里想着实现这些解法的基础数据结构等等,于是忍不住小试了一下,一发不可收拾,就这样做了两个星期。中间生了一场病,在宿舍里躺了几天,顺便看了几本书,从《万寿寺》到《红拂夜奔》到《寻找无双》,也不知道是感冒药吃多了比较敏感,还是真的感触太大,有一天晚上看完《红拂夜奔》后,竟失声痛哭起来。我体会着那种无尽的绝望,甚至已经无力悲愤了。昨夜又看了《三十而立》,逻辑上的“人人都要死,皇帝是人,所以皇帝必死”与为生存目的而喊出的“皇上万岁万岁万万岁”相对立,可是人都能接受,人是多么复杂的生…

2012-06-13 16:31 · 编程 · 实践 · 评论(8)

Eva'Sudoku-0.1新鲜出炉啦~~

呵呵,经过将近一个星期的对pygame的了解与熟悉,我终于磕磕绊绊地把数独的基础界面做出来啦。当然啦,完全不出意思的是,很丑,所有的东西都是自己一笔一画画出来的,没有对话框,没有菜单栏,更别提什么精美的画面了。不过我却因此更了解界面编程的实质了。再复杂的界面,底层应该也是这样子画出来的吧?就跟android里面的canvas那样。同时也了解到了一个概念,叫FPS,frame per second,就是说一秒钟里面对画面进行多少次重画。pygame程序的框架大概是这样: pygame.init() #初始化pygame,为使用硬件做准备 clock = pygame.time.Clock() …

2012-05-27 21:06 · 编程 · 实践 · 评论(0)

产生数独迷题

随着数独解题算法DLX的完成,产生一个数独迷题的任务就顺理成章地完成了。当然,基本的思想还是先生成终盘,然后对填好的数独题进行挖洞,每挖一个洞,就要考虑一下挖去这个洞会不会导致迷题将有多个解。假如会,这个洞就是不能挖的。事实上当一个洞被证实挖去之后会导致多解后,这个洞就注定不能被挖了。也就是说,这个算法的复杂度应该是81*O(f(n)),其中f(n)是用于解一个数独的时间复杂度。 《编程之美》里面提供了一种生成终盘的方法,即在数独中间的块(B5)上随机填入1~9,然后利用这个块行列变换到旁边的块(B4跟B6、B2跟B8)上,同样的做法将在B4、B6上填充B1跟B7,B3跟B9,从而得到一个合…

2012-05-24 18:13 · 编程 · 实践 · 评论(0)

解数独——dancing link X

折腾了一个星期,发现自己的大脑真的是短路了,智力水平下降到历史最低点,竟然折腾了那么久才理解了dancing link。所幸经过几天的反思,终于列出了接下来应该做的几件事: 产生数独题: 1.1 实现解数独的算法dlx 1.2 从数独终盘中随机选择一个cell,判断该cell是否可以挖掉而不会造成解不唯一 用pygame实现基本界面 今天完成了1.1的编码,借此总结一下。 老实说,我也不明白为什么dancing link X会花了我那么多时间去理解,尤其是当我最后理解了它并用三种方法把它实现了之后。也许是Donald 26页的论文把我吓到了,也许是我真的变笨了,或者老了。。 在那篇26页的论…

2012-05-21 22:59 · 编程 · 实践 · 评论(0)

总共有多少个数独?

憋屈地看了一个星期的论文,实在是没一点意思。为了娱乐一下自己,兼受同学启发,我决定用python写一个数独游戏。从大二开始装了个ubuntu系统后,就发现了这个有趣的游戏。之后每次进入这个系统,非得先来几局数独;再到后来,为了玩数独,特意进了这个系统。喜欢这个自带的游戏的特点,界面简单,只做必要的错误提示,可以回溯,是我用过的最理想的数独游戏了,呵呵。至于我自己打算做一个数独游戏,纯粹是为了现学现用。自从开始学python以来,从来没有真正用它写过一段带有自己设计思想的代码,实是不该。何不就为自己做一个windows下也能玩的称心如意的数独呢?好了,取名就叫Eva's Sudoku~!不过话…

2012-05-12 15:31 · 阅读 · 实践 · 评论(0)

《算法引论》之算法分析

上次写博客,已经是半个月之前了。我也不知道我这段日子在干嘛了,没有具体的目标与计划,比较随性,看了几本原本束之高阁的书,包括那本室友推荐,买来后一直搁在床头,不少著名的书里提到的《怎样解题》,以及那本曾经感觉不能理解的《孤独及其所创造的》,还看了一部《中国近代史》,因为还未买到港版,至今还在看小小的手机屏幕。昨夜清风习习,凉意袭人,没有负担,没有烦恼,可以看书看到自然睡,睡觉睡到自然醒,何其的幸福呵。然后又想起被搁置很久的《算法引论》,于是今天又开始阅读了。 第三章《算法分析》主要用于计算算法的复杂度,记得以前《算法导论》也有仔细介绍过,不过没有仔细去了解。关于上界、下界等标记也没有仔细去理…

2012-04-26 14:01 · 阅读 · 算法引论阅读笔记 · 评论(0)

编程之美续

看完编程之美后看很多题,都会发现原来只是里面一些题目的变种(也大概因为看的是微软的笔试题吧。。),把原先的算法稍微一改,就变成了题目的解法,还是挺带劲的。 1. 反转单向链表:给出单向链表的头指针,要求把链表反转过来。 struct ListItem { int value; struct ListItem* next; }; ListItem* reverse( ListItem* pHead ) { //如果链表为空或只有一个元素,直接返回 if( pHead==NULL || pHead->next == NULL ) return pHead; ListItem* pNext=pHe…

2012-04-06 15:37 · 阅读 · 编程 · 评论(0)

编程之美

前段日子又看了编程之美,后来闲着无聊学python去了,想着书将要送人,还是先总结一下,不然怕又要忘了,呵呵。 主要看的章节是第二、第三章,因为对数独有特别的感情,所以还顺带看了一四章关于数独的那两节。 1. 对于一个字节的无符号整形变量,求其二进制表示中“1”的个数。 最简单的莫过于用/跟%一个位一个位地测试: int count( unsigned char n ) { int num = 0; while( n ) { if ( n%2 == 1 ) num++; n >>= 1; } return num; } 算法的复杂度为O(n),但是操作符/跟%的代价都比较高。我比较喜欢的解法…

2012-04-02 16:54 · 阅读 · 编程 · 评论(0)

stl中的几个精美算法

关于STL中的算法,我印象比较深刻的主要有用于list的sort、power以及用于random_access_iterator的qsort,list是一种bidirectional_iterator,因此设计了自己的一个sort算法,主要思想是mergesort。 首先看一下list中的sort: template<class T, class Alloc> void list<T, Alloc>::sort(){ //这一段主要用于判断列表是否为空,或者只有一个节点 if( node->next == node || link_type(node->next)->next == node…

2012-03-17 18:35 · 阅读 · 评论(0)

STL和内存管理技术

前段日子读了STL的源码,大师级的作品真是精致到让人喟叹。当然,有时候你在网上还是可以看到很多对STL的批评,例如,对编译器要求很高,很多时候出错了的话,打印出来的错误信息总是让人摸不着头脑的。这确实是比较头疼的一个问题,因为模板编程,编译的过程总是分为两个部分的,是先要找到相应的模板,然后才对模板进行具现化,有时候单纯从模板来看,似乎很完整,没有什么问题呀,可是一旦投入使用了,才发现找不到合适的具现化版本,于是又要搞特化了。某日在路上行走,突然想起爱情这个难题,突然想起具现化,突然觉得爱情就像是一个模板类,是想象,没有实现的时候,它看起来很完美,很丰富,可是爱情一旦具现化,它便成了独此一家…

2012-03-17 16:46 · 阅读 · 评论(0)

effective c++ -- 定制new和delete

这一章讲述了C++中的new和delete背后的一些机制,以及重写new和delete需要遵守的一些规则,以及什么时候适合重写new和delete以提高效率。 Item 49: 了解new-handler的行为 当operator new无法满足某一内存分配需求时,它会调用一个客户指定的错误处理函数,及new-handler,new-handler可能会为operator new找到足够的内存或者其他怎样以处理内存不足的情况,如果new-handler为空,operator new抛出异常。 通过set_new_handler来设置内存不足时调用的操作,它是声明于 的一个标准程序库函数: n…

2012-02-17 15:23 · effective c++ 阅读笔记 · 评论(0)

effective c++ -- 模板与泛型编程

面向对象提供了运行期的多态,而模板则提供了编译期的多态。模板的编译期多态机制使得函数匹配机制相对于非模板的函数匹配发生了一些变化,也影响了继承体系下的一些声明与设计。本章讲解了模板的编译期多态对我们原先所熟悉的没有模板的世界的一些区别,最后介绍了traits class以及template元编程。 Item 41: 了解隐式接口和编译期多态 通常显式接口由函数的签名式(函数名称、参数类型、返回类型)构成。例如Widget class: class Widget{ public: Widget(); virtual ~Widget(); virtual std::size_t size() c…

2012-02-16 16:21 · effective c++ 阅读笔记 · 评论(0)

effective c++ -- 继承与面向对象设计

继承与面向对象设计中,涉及了继承方式,即public、private及protected继承方式,继承体系中的屏蔽问题,成员函数virtual、non-virtual的选择以及多重继承等。 Item 32: 确定你的public继承塑模出is-a关系 以C++进行面向对象编程,最重要的一个规则是:public inheritance意味is-a的关系,于是,基类对象B可以派上用场的地方,继承类对象D一样可以派上用场。 类之间除了存在is-a关系外,还可能存在has-a和is-implementated-in-terms-of的关系。 **Item 33: 避免遮掩继承而来的名称 在继承体系下…

2012-02-15 18:01 · effective c++ 阅读笔记 · 评论(0)