[Udacity CS 215] Algorithms (Week #5)

  
previously:
第四个unit  http://www.1point3acres.com/bbs/thread-37651-1-1.html
第三个unit  http://www.1point3acres.com/bbs/thread-37565-1-1.html
第二个unit  http://www.1point3acres.com/bbs/thread-37403-1-1.html
第一个unit  http://www.1point3acres.com/bbs/thread-37390-1-1.html


这章的标题是 Strong and Weak Bonds

1. Matrix Multiplication
既然图可以用邻接矩阵M来表示了，那么每一个在M^2的元素(i, j)就表示了从i点开始经过2条边到达j点的路径的个数。计算矩阵乘法需要O(N^3)。

2. 单源最短路径
dijistra算法。CLRS第24章。

Dijkstra算法是一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。

适用条件与限制：

• 有向图和无向图都可以使用本算法，无向图中的每条边可以看成相反的两条边。
• 用来求最短路的图中不能存在负权边。(可以利用拓扑排序检测)
  

最简单的实现方法就是，在每次循环中，再用一个循环找距离最短的点，然后用任意的方法更新与其相邻的边，时间复杂度显然为O(N^2)

1. def dijkstra(G,v):
   
2.        dist_so_far = {}
   
3.        dist_so_far[v] = 0
   
4.        final_dist = {}
   
5.        while len(final_dist) < len(G):
   
6.                w = shortest_dist_node(dist_so_far)
   
7.                # lock it down!                                                                                                                                                                                    
   
8.                final_dist[w] = dist_so_far[w]
   
9.                del dist_so_far[w]
   
10.                for x in G[w]:
    
11.             if x not in final_dist:
    
12.                                if x not in dist_so_far:
    
13.                                         dist_so_far[x] = final_dist[w] + G[w][x]
    
14.                                elif final_dist[w] + G[w][x] < dist_so_far[x]:
    
15.                                         dist_so_far[x] = final_dist[w] + G[w][x]
    
16.         return final_dist

复制代码

然后老师接着讲了用使用堆来优化。就是使用堆来保存没有扩展过的点的距离并维护其最小值，并在访问每条边的时候更新，可以把时间复杂度变成O((N+E)*logN)

当边数远小于点数的平方时，这种算法相对来说有很好的效果。但是当E=O(N^2)时（有时候表现为不限制边的条数），用二叉堆的优化反倒会更慢。因为此时的复杂度是O(N+N^2*logN)，大于不用堆的实现的O(N^2)的复杂度。

3. all pairs shortest paths

Floyd-Warshall 算法用来找出每对点之间的最短距离。这个算法通过考虑最佳子路径来得到最佳路径。(DP)该算法的基本思想是： 对于每一对顶点 i 和 j，看看是否存在一个顶点 k 使得从 i 到 k 再到 j 比己知的路径更短。如果是更新它。

1. // dist(i,j) 为从节点i到节点j的最短距离
   
2. For i←1 to n do
   
3.        For j←1 to n do
   
4.               dist(i,j) = weight(i,j)
   
5. 
   
6. For k←1 to n do // k为“媒介节点”
   
7.       For i←1 to n do
   
8.             if (i<>k) then
   
9.                   For j←1 to n do
   
10.                         if (i<>j) and(k<>j)then
    
11.                               if (dist(i,k) + dist(k,j) < dist(i,j)) then // 是否是更短的路径？
    
12.                                        dist(i,j) = dist(i,k) + dist(k,j)
    
13. 
    

复制代码

这个算法的效率是O(E^3)。

4. 利用随机选点计算给定结点的Clustering Coefficient

在上一个unit中，计算cc是使用公式 cc(V) = 2 * (V的邻居们互相之间的边数) / (V的邻居数 * (V的邻居数-1))
在这个unit最后，老师讲了另一种方法： 在V的邻居中随机选两个点，看他们之间有没有边相连，重复1000次，最后乘上概率，得到的结果趋近于真实的clustring coefficient。

1. total = 0
   
2. for i in range(1,1000):
   
3.         if 如果结点v的度数大于 > 1:
   
4.                 在v的邻居中随机选两个点v1,v2
   
5.                 if v2 in G[v1]: total += 1
   
6.         print i, (total+0.0)/i
   
7. 
   
8. 随着重复次数越来越多，可以观察到接近于理论上的clustring coefficient

复制代码

编程作业题：

---

Implementing Dijkstra with Heaps

使用二叉堆来实现dijkstra算法。具体的思想，讲义里已经讲了。 可以自己写一套堆的操作函数，也可以使用python自带的heapq。


Least Obscure Path

# Another way of thinking of a path
# is not about finding *short* paths, but by finding paths
# that don’t use obscure movies.  We will give you a
# list of movies along with their obscureness score.  
#
# Use the the imdb-1.tsv and imdb-weights.tsv files to find
# the obscurity of the “least obscure”
# path from a given actor to another.  
# The obscurity of a path is the maximum obscurity of
# any of the movies used along the path.

#
# Hint:
# modified dijkstra to minimize
# the obsucurity instead of distance

到了第五周了，感觉好吃力。。感觉算法的过程能理解，但自己就是不太会用代码去实现，该怎么做呢？