推荐系统是个做了很久的领域了，这个范畴内的基本可以归入数据挖掘，文章也有不少都是发在KDD上的。在这个方面，主要的方法大概基于两类，Content Filtering(内容过滤)和Collaborative Filtering(协同过滤)。[1]
Content Filtering方法需要特定领域的知识，也就是需要人为的规定标准来描述物品，但是对于大规模数据来说，人工量太大，不可行，而且也不通用。
Collaborative Filtering方法则具有Domain Free的特性，通用，它的决策只基于user-item matrix(有时也会加入一些其他的，比如时间等)。
在Collaborative Filtering下面则有很多方法，分类方法不一，按照[2]种说法，分为memory-based和model-based。 Read more »
在一个动态网络中求最短路，在边权没有什么性质时会非常悲剧的成为一个NP-hard问题。但是当考虑一个特定的实际问题，比如交通网络的时候，情况会大幅好转，因为这种网络的边都满足一个非常良好的性质——FIFO，举个例子来说，对于某辆恒速车，先进入某边必然不会比后进入完离开此边。当满足此性质后，整个问题就可以用Dijkstra来解了，配上堆，时间复杂度骤降至nlogn级别。
对于交通等网络中的交通灯导致的turn等待问题的处理，可以采用分点的策略将每一个turn转成一条边，等待时间为边权即可。
多项式时间内可解决的问题 is simple prolem, 否则 not simple
@多项式时间简化：
对于任意问题X的一个特例，可通过构造(多项式时间内)并解决问题Y的某个特例来解决X的这个特例，说X <= Y。
@独立集问题(Independent Set) 给一个无向图G，如果一个点集合保证任意两点之间没有边，称其为独立集。
问题1：给定整数k，是否存在独立集，其点数>=k?
问题2：求最大独立集 Read more »
强连通分量的三种算法和四种实现
常见的（我见过的）强连通分量的三种算法有：1. Kosaraju算法（双DFS）2.Tarjan算法 3.Gabow
一.Kosaraju算法
算法的核心实现是，首先DFS一遍，得到一个DFS森林，在此过程中得到所有点的拓扑序列（按结束时间由高到低），之后我们建一个反向图，按反拓扑序（结束时间由高到低）进行第二次DFS，则此时得到的每一棵树都是一个强连通分量，这个画个图演示一下比较好理解，严格证明还是参考算法导论340页较好，感性的认识是，假定我们有C1，C2两个强连通分量，而在反拓扑序中C1是在C2前面的，此时说明G中第一遍DFS时先结束了C2，C1才结束的，假设C2中的点是从C1可达的，也就是在第一遍DFS时C2中点的全部时间戳的区间位于C1的区间内，则反向时，这时当将所有边反转时C1就没有边能到C2了（前提是他俩确实是SCC），按照先C1在C2的顺序DFS就行了，这里用到了一些DFS的性质，看算法导论为好。如果它们本来就是两棵树那么饭拓扑序靠前的那棵也不可能有边到后面的。虽然本算法慢，但是它得到了一个连通分量的拓扑序，有时用的上。 Read more »
