算法工程师必知必会的10大基础算法与python示例（二）

算法八：狄克斯特拉算法（Dijkstra）

bfs可以解决无权图最短路径问题。可是，在实际工程过程中，边带权重的图才更加广泛。嗯，带权图的最短路径算法狄克斯特拉算法应运而生。该算法由荷兰计算机科学家狄克斯特拉提出。

Dijkstra算法使用广度优先搜索思路来解决非负有权有向的单源最短路径问题，算法最终得到一个最短路径树。该算法的输入包含了一个有权重的有向图$G$以及$G$中的一个来源顶点$S$，我们用$V$标识$G$中的所有顶点的集合。

图都是加权有向的，所以表示起来稍微麻烦些。用有序数对$(u,v)$表示从顶点$U$到顶点$V$有路径连接，我们用$E$表示$G$中的所有边的集合，而边的权重则有权重函数$w:E\to [0,\infty )$定义，即用数组$w(u,v)$表示有向路径$(u,v)$的非负权重。

狄克斯特拉算法用于在单源有向图中寻找源点到其他顶点的最短路径。对于不含负权的有向图，狄克斯特拉算法是目前已知的最快的单源最短路径算法。

狄克斯特拉算法如下：

1.初始时，令 S = v 0 , T = o t h e r v e r t e x S={v_0}, T={other vertex} S=v0​,T=othervertex，$T$中顶点对应的距离值，若存在 ( v 0 , v i ) (v_0, v_i) (v0​,vi​)，则令 d ( v 0 , v i ) = w ( v 0 , v i ) d(v_0, v_i)=w(v_0, v_i) d(v0​,vi​)=w(v0​,vi​)；若不存在，令 d ( v 0 , v i ) = ∞ d(v_0, v_i)=\infty d(v0​,vi​)=∞。

2.在$T$中选取一个其距离值为最小的顶点$W$且不在$S$中，加入$S$。

3.在$W$有连接的顶点，更新其距离值。

4不断重复2， 3两步，直至$S$中包含所有顶点为止。

算法例子

我们这里举一个特别简单的例子，图如代码示例中所示。
假设$0,1,2,3$是四个公交站，他们都是单程的，每条边上边$⟨i,j⟩$标出了从站$i$到站$j$所需时间。从图中我们可以得到如下数据

w = ( 0 6 2 ∞ ∞ 0 ∞ 1 ∞ 3 0 5 ∞ ∞ ∞ 0 ) v = [ 0 , 1 , 2 , 3 ] d i r = { 0 : [ 1 , 2 ] , 2 : [ 1 , 2 ] , 1 : [ 3 ] } w = \begin{pmatrix}0&6&2&\infty\\ \infty&0&\infty&1\\ \infty&3&0&5\\ \infty&\infty&\infty&0\end{pmatrix}\\ v = [0, 1, 2, 3]\\ dir = \{0:[1, 2], 2:[1, 2], 1:[3]\} w=⎝⎜⎜⎛​0∞∞∞​603∞​2∞0∞​∞150​⎠⎟⎟⎞​v=[0,1,2,3]dir={0:[1,2],2:[1,2],1:[3]}
式中$v$表示顶点，$dir$是邻接表，$w$是路径的权重。

'''#####->  # 1 #6 /     #####   \ 1/        ^       \
#####         |         ->###### 0 #        | 3         # 3 #
#####         |         ->#####\  2      |       / 5\     #####  /->   # 2 ######'''
import sys
class Dijkstra:def __init__(self, v, w, dire):self.w = w #距离矩阵self.v = v #vertex集合self.dir = dire #邻接表self.visit = set([0]) #用于记录是否被访问过self.path = {} #用于记录每个被访问到的点的路径self.dis = [sys.maxsize]*len(v) #用于记录每个点到源点的距离def dijkstra(self):for i, v in enumerate(self.v):self.dis[i] = self.w[0][i]self.path[i] = [0, i]while len(self.visit) self.dis[tmp_ind]+self.w[tmp_ind][v]:self.dis[v] = self.dis[tmp_ind]+self.w[tmp_ind][v]self.path[v] = self.path[tmp_ind] + [v] #跟新路径class Solution:def dijkstra(self, v, w, dire):self.dij = Dijkstra(v, w, dire)self.dij.dijkstra()if __name__ == "__main__":v = [0,1,2,3]dire = {0:[1,2],2:[1,2],1:[3]}w = [[0, 6, 2, sys.maxsize], [sys.maxsize, 0, sys.maxsize, 1], [sys.maxsize, 3, 0, 5], [sys.maxsize, sys.maxsize, sys.maxsize, 0]]solution = Solution()solution.dijkstra(v, w, dire)print(solution.dij.dis[3], solution.dij.path[3])

算法九：动态规划算法（dynamic programming）

DP问题是一个超大课题，可以写很多专题来讲解，这里放在必知必会的第九个，也算合理吧。我感觉leetcode的系列文章不错，可以参考下
dp的问题跨度太大，不过总体有一个共同特点，如果状态设计合理的话，可以四两拨千斤，用最快的速度，最小的内存来解决最难的问题。
dp类似于数学归纳法，从小规模的问题推到出大规模的解法，并且存储这些中间过程。最直观的dp是菲波那切数列的求解。菲波那切数列定义中所周知
f 0 = 1 f 1 = 1 f n = f n − 1 + f n − 2 f_0 = 1\\ f_1 = 1\\ f_n = f_{n-1} + f_{n-2} f0​=1f1​=1fn​=fn−1​+fn−2​
如果递归解的话，指数发散会。这个用dp接， d p [ n ] = f n dp[n]=f_n dp[n]=fn​，这样转移方程即是$dp[n]=dp[n-1]+dp[n-2]$。

嗯，总结下动态规划，其实就两部分，一是DP的状态，二是状态的转移方程。DP的状态学问比较大，好的状态事半功倍，坏的状态~~~~，嗯坏的状态解题解题解到撞墙也应该解不出来。状态的确定有两大原则，即最优子结构和无后效性。

1.最优子结构：
动态规划就是将大问题化为一个一个的小问题，然后求解，这个子问题就是子结构，对于每个子问题，其最优值均由更小规模的子问题的最优值推到而出，即为最优子结构。

2.无后效性：
对于无后效性，就是我们只关心子问题的最优解，不关心子问题的最优解是怎么得到的。即子问题的最优解求解过程不会对后续有影响。这一点很重要，坏的状态一般都是有后效性的，这个用dp求解，好像就是暴力求解了。

我们将最优子结构的最优值都存储下来，状态转移方程给出了我们如何从最优子结构的最优值得到更大的结构的最优值，即我们从存储的这些值里面，既能推到出当下结构的最优值。

其余关于dp的一些总结与问题，可以参看其他资料了（以后可能也会总结到这里），我们这里只说最基本的。

leetcode 例子

dp算法leetcode题的经典解法，例题太多，我们这里找个简单明了的说一下。其实dp最经典的是背包问题，大神们都说看懂了背包问题，dp问题就不是问题了。有点想绕口令哈。直接上题吧。

'''
硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)示例1:输入: n = 5输出：2解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1
示例2:输入: n = 10输出：4解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1
'''
class Solution:def waysToChange(self, n: int) -> int:dp = [1] + [0]*ncoins = [1, 5, 10, 25]for coin in coins:for i in range(coin, n+1):dp[i] += dp[i-coin]return dp[n]%1000000007if __name__=='__main__':solution = Solution()n=10print(solution.waysToChange(n))

算法十：朴素贝叶斯分类算法

朴素贝叶斯分类算法十一中基于贝叶斯定理的简单概率分类算法，贝叶斯分类的基础是概率推理。就是在各种条件的存在不确定，仅知其出现概率的情况下，如何完成推理和决策任务。
朴素贝叶斯分类器是基于独立假设的，即假设样本每个特征与其他特征都不相关，概率上是相互独立的。
这个leetcode上面貌似没有例题了，这属于machine learning中的基础算法了。我们用《machine learning in action》中的例子来说明这个问题吧，这本书中分类章节专门讲的朴素贝叶斯分类，讲的清晰明了，核心就两个问题，一是特征概率独立，二是贝叶斯推断方程，即
p ( x 1 , x 2 , . . . , x n ) = p ( x 1 ) p ( x 2 ) . . . p ( x n ) p ( y / x ) = p ( x / y ) p ( y ) p ( x ) p(x_1, x_2, ..., x_n) = p(x_1)p(x_2)...p(x_n)\\ p(y/x)=\frac{p(x/y)p(y)}{p(x)} p(x1​,x2​,...,xn​)=p(x1​)p(x2​)...p(xn​)p(y/x)=p(x)p(x/y)p(y)​
书中给的例子是分类垃圾邮件，代码较长，我就不贴这里了，有兴趣的同学可以自行查看。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！