2021-05-20

算法学习(四)

  • 迭代加深搜索(Iterative Deepening DFS,IDDFS)

迭代加深搜索结合了BFS和DFS的思想。当我们遇到一个搜索问题是,它的搜索树非常特别,深度极深,宽度极广,使用DFS递归过长,使用BFS会使得队列爆炸。因此我们可以使用IDDFS解决这个问题。它的思想是:先假定一个搜索深度为1,然后用DFS搜索到第一层停止,在这个过程中,每一层的广度上采用BFS搜索。如果没有找到,则向深度为2的第二层搜索,依次递归。逐步扩大搜索的深度,直到找到答案。

下面用埃及分数的例子加以说明。

(*埃及分数:例如19/45 = 1/3+1/12+1/180,也可以写成19/45 = 1/5+1/6+1/18,即把一个分数拆分成数个1/n的和,且加数中全不相同,要求:加数的个数尽可能小,同时最小的分数越大越好。)

这个问题有几个难点:

  1. 在埃及分数计算时,如何不让分数被化为小数从而损失精度?
  2. DFS搜索时如何剪枝?
  3. 如何保证最优解?

4.找到下一个最大的埃及分数后该如何处理?

对于第一个问题,我们可以这样解决:

2021-05-20

 

这样我们就解决了第一个问题。这个过程用GCD( )求取最大公约数。注意在b/a-1/k后需要约分。

接下来解决关于剪枝的问题。下图很好的解释了这个问题:

2021-05-20

 

以及代码的复现:

    2021-05-20

2021-05-20

 

二、并查集(Disjoint Set)

 

   并查集是指:将编号1-n的n个对象划分为不相交集合,在每个集合中,选择某个元素代表所在的集合。并查集主要用于处理一些不相交集合的合并问题。

并查集操作的简单原理用一个简单的例子加以说明。假设:有n个人一起吃饭,有人相互认识。认识的人想跟认识的人坐在一张桌子上,那么给出认识的人的关系,求解桌子的数量。现在我们先用图来表示一下我们的思路:

假设有1,2,3,4,5分别代表五个集合,A,B,C,D,E分别代表五个人。先假设他们有如下关系:

1 2 3 4 5

A B C D E

即对应的人是对应集合中的元素。若A认识B,那么可以把A并入到集合2中,即把节点1的集合1改成节点2的集合2。示意图如下:

2021-05-20

 

注意初始化是用元素表示它的集合s[i],例如元素1的集合s[1] = 1。

附上代码的复现:

2021-05-20

当然这个算法可以继续优化,简单说一下路径压缩。在查询元素i所属集合需要搜索路径找到根节点,若在返回时把所属的集合改成根节点,下次搜索该元素的时候就能一常数时间内得到结果。

 

三、二叉树

用深度优先搜索二叉树,有以下方式:

  1. 先序遍历,即按照父节点,左儿子,右儿子的顺序进行遍历。
  2. 中序遍历,即按照左,父,右的顺序遍历。
  3. 后序遍历,按照左,右,父的顺序遍历。

需要注意的是,如果某刻二叉树已知“中序遍历+先序”或者“中序+后序”,都能确定唯一的一棵二叉树。但如果只知道“先序+后序”,则不能唯一确定一棵树。

二叉树的第n层最多有2^(n-1)个节点,如果每一层的节点数都是满的,称为满二叉树。如果满二叉树只在最后一层有缺失,那么称为完全二叉树。

 

  • 二叉搜索树(Binary Search Tree,BST)

BST有如下特征:

  1. 每个元素有唯一的键值。通常把键值存放在BST的节点上。
  2. 任意一个节点的值,比它左子树的所有节点的键值大,比它右子树的所有节点键值小。
  3. BST排序和快速排序十分类似,它们实质上是做了相同的比较,只是比较的顺序不同。对于一个随机化的BST来说,它的树结点的平均深度是log n的。利用Jenson不等式证明,即F[E(x)] ≤ E[F(x)]。

一般而言,我们更希望一个数是平衡二叉树,而非链表一样的二叉树。这里补充说明一下平衡二叉树(AVL):

平衡二叉树满足:

1. 是「二叉排序树」(即所有左子树的值小于根节点,右子树的值大于根节点)

2. 任何一个节点的左子树或者右子树都是「平衡二叉树」(左右高度差小于等于 1)

这样就避免了二叉树成为一个链表一样的排列,这个时候查找的效率是最差情况(the worst case),它是O(n)的复杂度。

这个问题需要动态的调整使得二叉树保持平衡。BST的算法有AVL树,红黑树,Splay树等,可以优化树的结构。

 

总结:

这个星期阅读了有关搜索技术和一些高级数据结构内容。个人感觉有关二叉树的问题比较难,在网上也找了一些相关的网课,如MIT的算法导论,里面讲解的有关平衡二叉树的数学性质感觉没怎么听明白。然后有关红黑树,Treap树也看了一些,感觉关于树的动态调整还是理解不够。下个星期在进行详细的学习。

上一篇:leetcode230 Kth Smallest Element in a BST


下一篇:实现对二叉树的操作---插入,删除,最大(小)值,遍历,查找