2014-04-06阅读(6390)评论(5)

POJ 3268 Silver Cow Party 奶牛派对：有分别来自 N 个农场的 N 头牛去农场 X 嗨皮，农场间由 M 条有向路径连接。每头牛来回都挑最短的路走，求它们走的路的最大长度？ 2.5 它们其实都是“图” 最短路 ...

2014-04-05阅读(7754)评论(1)

春暖花开，踏青时节，我看完了形式语言与自动机这一章这一章提到字符串编辑距离，于是动手实现了几个。编辑距离主要用于拼写纠错，貌似Google 2013的校招笔试题里就有这个。 常见的编辑距离定义 通过插入删除或替换使得一个字符串变为另一个字符...

2014-04-03阅读(6345)评论(3)

POJ 3259 Wormholes 虫洞：农夫约翰有F个农场，每个农场有N块地，其间有M条路，W条时光隧道（时间倒流）。问是否可能回到过去？ 2.5 它们其实都是“图” 最短路 依然很水很基础的 Bellman-Ford 判定负...

2014-03-30阅读(4500)评论(0)

AOJ 0189 Convenient Location 上班族：A桑的实习办公室有多个，公司允许睡办公室，求找出一个办公室使得跑路最短。 2.5 它们其实都是“图” 最短路 基础的任意两点之间的距离Floyd-Warshall算法就行了。...

2014-03-30阅读(6275)评论(2)

最小生成树Prim算法 与Dijkstra算法类似，任意挑一个顶点，添加最短边，直至所有顶点都在树中，此时就得到一颗最小生成树了。 证明： 令V为顶点集合，已求得顶点集合为X，V上的最小生成树为T。 假设连接X和V\X的最短边为e，现在需要...

2014-03-30阅读(5641)评论(1)

对图的几种初级算法做个总结，温故知新。 最短路问题 Bellman-Ford和Dijkstra的递推公式都是d[i] = min{d[j] + cost[i to j]}。 单源最短路之Bellman-Ford算法 适用于无原点s可达负圈的...

2014-03-22阅读(17784)评论(5)

维特比算法说白了就是动态规划实现最短路径，只要知道“动态规划可以降低复杂度”这一点就能轻松理解维特比算法 维特比算法是一个特殊但应用最广的动态规划算法，利用动态规划，可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图——篱笆...

2014-03-18阅读(39318)评论(65)

双数组Trie树(DoubleArrayTrie)是一种空间复杂度低的Trie树，应用于字符区间大的语言（如中文、日文等）分词领域。 双数组Trie (Double-Array Trie)结构由日本人JUN-ICHI AOE于1989年提出...

2014-03-12阅读(16974)评论(21)

最近在看Ansj中文分词的源码，以前没有涉足过这个领域，所以需要做一些笔记。 2015年4月13日更新 经过研究与试验，我觉得trie树分词是一种很落后的技术。 最完美的分词、停用词过滤的技术是Aho Corasick自动机结合Double...

2014-03-11阅读(5071)评论(3)

AOJ 2170: Marked Ancestor 染色祖先：距离某节点最近的染色节点称为祖先，求染色过程中各节点祖先。 2.4 加工并储存数据的数据结构 并查集 稍有些复杂，需要bfs和两棵树。一棵树用来维护并查集，一棵树用来保存原来的树...